This is the first of a series of posts on the prospects for using
privacyenhancing technologies in the NSTIC Identity Ecosystem.
NSTIC calls for the use of
privacyfriendly credentials, and NSTIC documents
[1]
[2] refer to the existence of privacyenhancing
technologies that can be used to implement such credentials. Although
those technologies are not named, they are widely understood to be
UProve and Idemix.
There is confusion regarding the capabilities of privacyenhancing
technologies and the contributions that they can make to NSTIC. For
example, I sometimes hear the opinion that “UProve has been
oversold”, but without technical arguments to back it up. To help
clear some of the confusion, I’m starting a series of posts on the
prospects for using privacyenhancing technologies in the NSTIC
Identity Ecosystem. This first blog is on the pros and cons of
UProve, the second one will be on the pros and cons of Idemix, and
there will probably be two more after that.
UProve is described in the UProve Cryptographic Specification V1.1
[3] and the UProve Technology Overview
[4]. It is based on cryptographic techniques
described in Stefan Brands’s book
[5].
Privacy Feature Coverage
Three features of privacyfriendly credentials are informally
described in NSTIC documents:
 Issuance of a credential cannot be linked to a use, or “show,” of
the credential even if the issuer and the relying party share
information, except as permitted by the attributes certified by the
issuer and shown to the relying party.
 Two shows of the same credential to the same or different relying
parties cannot be linked together, even if the relying parties share
information.
 The user agent can disclose partial information about the
attributes asserted by a credential. For example, it can prove that
the user if over 21 years of age based on a birthdate attribute,
without disclosing the birthdate itself.
Here I will not discuss how desirable these features are; I
leave that for a later post in the series. In this post I will only
discuss the extent to which UProve provides these features.
UProve provides the first feature, which is
called untraceability in the UProve Technology Overview
[4]. A UProve credential consists of a private key,
a public key, a set of attributes, and a signature by the credential
issuer. The signature is jointly computed by the issuer and the user
agent in the course of a threeturn interactive protocol,
the issuance protocol, where the issuer sees the attributes but
not the public key nor the signature itself. Therefore the issue of a
credential can be linked to a show of the credential only on the basis
of the attribute information disclosed during the show.
UProve, on the other hand, does not provide the second
feature, because all relying parties see the same public key and the
same signature. Stefan Brands acknowledges this in Section 2.2 of
[6], where he compares the system of his book
[5] to the system of Camenisch and Lysianskaya,
i.e. UProve to Idemix, acknowledging that the latter provides
multishow unlinkability but the former does not.
Unfortunately, the UProve Technology Overview
[4] is less candid. It does discuss the fact that
multiple shows of the same UProve credential (UProve token) are
linkable, in Section 4.2, but the section is misleadingly
entitled Unlinkability. It starts as follows:
Similarly, the use of a UProve token cannot inherently
be correlated to uses by the same Prover of other UProve tokens, even
if the Issuer identified the Prover and issued all of the Prover’s
UProve tokens at the same time.
This is saying that different UProve tokens are not linkable!
Which is a vacuous feature: why would different tokens be
linkable? The section goes on to argue that that the issuer should
issue many tokens to the user agent (the Prover) with the same
attributes, one for each relying party (each Verifier). On the Web,
this is utterly impractical. There are millions of possible relying
parties: how many tokens should be issued? How can all those tokens
be stored on a smart card? What if the user agent runs out of tokens?
And how does the user agent know if two parties are different or the
same? (Is example.com the same relying party
as xyz.example.com?)
Update.
Stefan Brands has pointed out that a UProve token does not take up any storage in a smart card if the private key splitting technique featured by UProve (which I refer to below) is used.
As for the third feature of privacyfriendly credentials, partial
information disclosure, UProve provides it to a certain extent. When
showing a credential, the user agent can disclose only some of the
attributes in the credential, proving to the relying party that those
attributes were certified by the credential issuer without disclosing
the other attributes. However, UProve does not support the “age over
21” example found in several NSTIC documents. That would require the
ability to prove that a value is contained in an interval without
disclosing the value. Appendix 1 of the UProve Technology Overview
[4] lists the ability to perform such a proof as one
of the “UProve features” that have not been included in Version 1.1,
suggesting that it could be included in a future version. In Section
3.7 of his book
[5], Stefan Brands does suggest a method for proving
that a secret is contained in an interval. However, it dismisses it
as involving “a serious amount of overhead”, because it requires
executing many auxiliary proofs of knowledge. (I believe that proving
“age over 21” would require at least 30 auxiliary proofs, which is
clearly impractical.)
An interesting feature of UProve is the ability to split the private
key of a credential between the user agent and a device such as a
smart card. The device must then be present for the credential to be
usable, thus providing twofactor authentication; but the device only
has to perform a limited amount of cryptographic computations, most of
the cryptographic computations being carried out by the user agent.
This makes it possible to use slower, and hence cheaper, devices than
if all the cryptographic computations were carried out by the device
(as is the case, for example, in an Idemix smart card).
Update.
A nonMicrosoft implementation of UProve on a MULTOS smart card, where all the cryptographic computations are carried out by the card with impressive performance (close to 0.3 seconds in some cases), can be found in [8].
Revocation
The ability to revoke credentials is usually taken for granted. In
the case of privacyfriendly credentials, however, it is difficult to
achieve. An ordinary CRL (Certificate Revocation List) cannot be
used, since it would require some kind of credential identifier known
to both the issuer and the relying parties, which would defeat
unlinkability.
UProve credentials have a Token Identifier, which is a hash of the
public key and the signature. Because UProve does not provide
multishow unlinkability, the Token Identifier, like the public key
and the signature, is known to all the relying parties. The user
agent could therefore revoke the credential by including the Token
Identifier in a CRL. However, because UProve provides issueshow
unlinkability, the credential issuer does not know the Token
Identifier, nor the public key or the signature, and therefore cannot
use it to revoke the credential.
Section 5.2 of the UProve Technology Overview
[4] says that an identifier could be included in a
special attribute called the Token Information Field for the
purpose of revocation, and “blacklisted using the same methods that
are available for X.509 certificates”; this, however, would destroy
the only unlinkability feature of UProve credentials, viz.
issuanceshow unlinkability (which
[4] calls untraceability).
Section 5.2 of
[4] also suggests using ondemand credentials.
However that does not seem practical: the user agent would have to
authenticate somehow to the issuer, then conduct a threeturn
interactive issuance protocol with the issuer to obtain the token,
then conduct a presentation protocol with the relying party. The
latency of all these computations and interactions would too high; and
since the issuance computations would have to be carried out each time
the credential is used, the cost for the issuer would be staggering.
Furthermore, ondemand credentials may allow linking of issuance to
show by timing correlation.
A workaround to the revocation problem is suggested in Section 6.2 of
[4], for cases where the credential is protected by a
device such as a smart card by splitting the private key between the
user agent and the device. In those cases the Issuer could revoke the
device rather than a particular credential protected by the device, by
adding an identifier of the device to a revocation list. However this
would require downloading the revocation list to the device in a
Device Message when the credential is used, so that the device
can check if its own identifier is in the list. Since a revocation
list can have hundreds of thousands of entries (e.g. the state of West
Virginia revokes about 90,000 driver licenses per year
[7]), downloading it to a smart card each time the
smart card is used is not a viable option.
Update.
Stefan Brands has pointed out that only a revocation list increment needs to be downloaded to the card.
Appendix 1 of
[4] includes an “issuerdriven revocation” feature in
a list of UProve features not yet implemented:
An Issuer can revoke one or more tokens of a known Prover by
blacklisting a unique attribute encoded in these tokens (even if it is
never disclosed at token use time).
How this can be achieved is not explained in the
appendix, nor in Brands’s book
[5]. However it is explained in
[6],
where Brands proposes a new system and compares it to his previous
system of
[5], i.e. to UProve. He says that
[5] “allows an issuer to invisibly encode into all of
a user’s digital credentials a unique number that the issuer can
blacklist in order to revoke that user’s credentials” adding that the
blacklist technique “consists of repeating a NOTproof for each
blacklist element”. In other words, the idea is to prove a formula
stating that the unique number is NOT equal to the first element of
the blacklist, and NOT equal to the second element, and NOT equal to
the third element, etc., without revealing the unique number. That
can be done but, as Brands further says in
[6], it is “not practical for large blacklists”.
Indeed, based on Section 3.6 of
[5], proving a formula with multiple negated
subformulas requires proving separately each negated subformula. So
if the blacklist has 100,000 elements, 100,000 proofs would have to be
performed each time a credential is used.
By the way, the system of
[6] is substantially different from UProve
and not well suited for use on the Web, since it requires the set of
relying parties to be known at systemsetup time.
Update.
Stefan Brands has told me that the cryptosystem described in [6] is considered part of the UProve technology, and that the revocation technique of [6] could be integrated into the existing UProve implementation to provide issuerdriven revocation.
Conclusions
I will save my conclusions for the last post in the series, but of
course any comments are welcome now.
References
[1]

The White House.
National Strategy for Trusted Identities in Cyberspace.
April 2011.
Available at
http://www.whitehouse.gov/sites/default/files/rss_viewer/NSTICstrategy_041511.pdf.

[2]

Howard A. Schmidt.
The National Strategy for Trusted Identities in Cyberspace and Your Privacy.
April 26, 2011.
White House blog post, available at
http://www.whitehouse.gov/blog/2011/04/26/nationalstrategytrustedidentitiescyberspaceandyourprivacy.

[3]

Christian Paquin.
UProve Cryptographic Specification V1.1 Draft Revision 1.
February 2011.
No http URL seems to be available for this document, but it can be
downloaded from the Specifications and Documentation page,
which itself is available at http://www.microsoft.com/uprove.

[4]

Christian Paquin.
UProve Technology Overview V1.1 Draft Revision 1.
February 2011.
No http URL seems to be available for this document, but it can be
downloaded from the Specifications and Documentation page,
which itself is available
at http://www.microsoft.com/uprove.

[5]

Stefan Brands.
Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy
2000.
MIT Press, Cambridge, MA, USA, 2000.
ISBN 0262024918.
Available for free download at http://www.credentica.com/the_mit_pressbook.php

[6]

Stefan Brands, Liesje Demuynck and Bart De Decker.
A practical system for globally revoking the unlinkable pseudonyms of unknown users.
In Proceedings of the 12th Australasian Conference on Information Security and Privacy, ACISP’07.
SpringerVerlag, 2007.
ISBN 9783540734574.
Preconference technical report available at http://www.cs.kuleuven.be/publicat
ies/rapporten/cw/CW472.pdf.

[7]

West Virginia Department of Transportation, Division of Motor Vehicles.
Annual Report 2010.
Available at http://www.transportation.wv.gov
/businessmanager/Finance/Financial%20Reports/DMV_AR_2010.pdf.

[8]

Update.
W. Mostowski and P. Vullers.
Efficient UProve Implementation for Anonymous Credentials on Smart Cards.
Available at http://www.cs.ru.nl/~pim/publications/2011_securecomm.pdf.
