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.

Good analysis. I made the same points to Craig before UProve was sent to stand in the R&D corner at Microsoft.
I do in some cases UProve & Idemix have benefits, though they tend to be oversold by there advocates.
Having worked on IMI (InfoCard) my concern is deploying and synchronizing clients across devices. We are moving to a post PC world having a single desktop we access the net from is no longer the only problem to solve for.
NSTIC needs to consider that having a choice of verifiably trustworthy Identity and attribute providers may be more practical than trying to solve the issue of IdP knowing where you use your credential through technology.
Regards
John B.
Francisco,
Very interesting discussion, I’m looking forward to read the following posts. I’d like to provide highlevel comments.
First, regarding multishow unlinkability, note that we define a UProve “credential” as a batch of (renewable, as needed) UProve tokens. Given the efficiency of the UProve protocols (especially when using the ECC variant), this _has_ proven quite practical in web scenarios (as demonstrated by our last two technology previews, http://www.microsoft.com/uprove).
Our current public specification describes a subset of fundamental features of the technology, carefully chosen to facilitate integration into existing identity systems (which are not equipped to make use of the more powerful minimal disclosure and revocation techniques). We are pursuing many initiatives to build the right feature set for the target scenarios. In particular, I’ll point you to the ABC4Trust project (https://abc4trust.eu/) where we are working (with IBM and other partners) to provide in a unified framework the missing features you mentioned.
Best regards,
Christian Paquin, Microsoft
I can confirm that “proving that a secret is contained in an interval” has a large overhead. A Master student I supervised, Pieter Rogaar, implemented this functionality based on the C# UProve SDK. His thesis entitled “Attributes and tokens in UProve: Interval proofs and use cases” describes the underlying mathematics [1] as well as a usability study for UProve for several scenarios (focussing on ITprojects in The Netherlands).
Improvements to the actual implementation [2] can be made depending on the encoding of the attribute and the definition of the interval, but an interval prove will still consume considerably more time than just showing the attribute.
Kind regards,
Pim Vullers
[1] http://www.jbisa.nl/download/?id=17674007&download=1
[2] http://rogaar.org/thesis/UProve10WithIntervalProofs.tar.gz
The correct link for [2] is http://rogaar.org/thesis/UProve10WithIntervalProofs.zip i.e. the link given in the thesis is wrong.
You could tell Pieter to make a .tar.gz file in addition to the .zip file and put it online so that the link works 🙂
Thank you for the info and for the link to Rogaar’s thesis.
Best regards,
Francisco Corella
Regarding overhead of interval proof: it was suggested in the thesis to prove (0,1) bits of powersof2, while a better protocol was designed from Lagrange theorem. That is, representing any natural number with 4 squares. Well, one generally needs a group of an order not known to Prover to prove statements about integers.
It would be fair to note powersof2 approach is only reasonable with current UProve implementing groups of a known prime order q.
Overhead would go away with groups of a hidden order, if ever available in UProve.
Due to the SchoofElkiesAtkin algorithm one cannot get reasonable ECC curves with unknown order. Therefore, it is no hope getting efficient interval proofs in the style of Idemix.