This is the second of a series of posts on the prospects for using privacyenhancing technologies in the NSTIC Identity Ecosystem.
In the previous post I discussed the pros and cons of UProve , so naturally I should now discuss the pros and cons of Idemix, the other privacyenhancing technology thought to have inspired NSTIC. This post, like the previous one, is based on a review of the public literature. If I’ve missed or misinterpreted something, please let me know in a comment.
By the way, a link to the previous post that I posted to the Identity Commons mailing list triggered a wideranging discussion on NSTIC and privacy, which can be found in the mailing list archives .
Idemix is an opensource library implemented in Java. It is described in the Idemix Cryptographic Specification [1], and the academic paper [2]. It is mostly based on the cryptographic techniques of [3]. Curiously, although Idemix is provided by IBM, the main Idemix site is located at idemix.wordpress.com and disclaims to be an official IBM site.
There is also a smart card that implements a “lightweight variant of Idemix”. I discuss it at the end of this post.
Feature Coverage
Idemix provides all three privacy features alluded to in NSTIC documents [4] [5] and discussed in the previous post:
 Issuanceshow unlinkability,
 Multishow unlinkability, and
 Partial information disclosure.
The third feature includes both selective disclosure of attributes and the ability to prove inequalities such as the value of a birthdate attribute being less than today’s date minus 21 years without disclosing that birthdate attribute value.
Idemix also includes other features, such as the ability to prove that two attributes have the same value without disclosing that value, and the ability to prove that a certain attribute certified by the issuer has been encrypted under the public key of a third party, which may decrypt it under some circumstances. It could be argued that Idemix is overengineered for the purpose of Web authentication, including features that add complexity but are not useful for that purpose.
Performance
The richer feature set of Idemix may come at a cost in terms of performance. From the data in Table 1 of [2], it follows that it would take about 12 seconds for the user to submit a credential with one attribute to a relying party that checks for expiration, and about 28 seconds to submit a credential with 20 attributes. The paper dates back to 2002, and the processor used was a relatively slow 1.1GHz Pentium III. (The authors say 1.1MHz but I assume they mean 1.1GHz.) But on the other hand the modulus size was 1024 bits, and Idemix currently uses a 2048 modulus [2]. The paper also promises optimizations that have no doubt been implememted by now. Unfortunately, I haven’t been able to find performance data in the Idemix site. A search for the word performance restricted to the site produces no results. If you know of any recent performance data, please let me know in a comment.
Revocation
We saw in the previous post that unlinkability makes revocation difficult. UProve credentials can be revoked by users because they do not have multishow unlinkability, but cannot be revoked by issuers because they have issueshow unlinkability. Idemix credentials, which have both multishow unlinkability and issueshow unlinkability, are revocable neither by users nor by issuers. I am not saying that unlinkability makes revocation impossible. Cryptographic techniques have been devised to allow revocation of unlinkable credentials, which I will discuss later in this series of posts. But those techniques are not used by UProve or Idemix.
Idemix has a credential update feature that can be used to extend the validity period of a credential that has expired. This facilitates the use of shortterm credentials that may not need to be revoked. But the Idemix Cryptographic Specification [1] should not claim as it does that the credentialupdate feature can be used to implement credential revocation. Waiting for a credential to expire is not the same as revoking it. Short term credentials are an alternative to revocation. And, as an alternative, they have serious drawbacks: they are costly to implement for the issuer; they impose a logistic burden on the user agent; they may become unavailable if the issuer is down when the validity period needs to be extended; and the user agent may be overwhelmed by the need to renew many credentials at once if it has not been operational for an extended period of time. If a shortterm credential is renewed on demand, just before it is used, renewal and use of the credential may be linkable by timing correlation.
The Idemix Java Card
The Idemix Java Card was intended as a smart identity card. Its implementation on the Java Card Open Platform (JCOP) is described in [6].
The cryptographic system in an Idemix card is described in the Idemix site as a “lightweight variant of Identity Mixer” (i.e. Idemix). But it is very different from the original Idemix system. According to [6], an implementation of the original system in a Java card would be impractical because credential submission could take 70 to 100 seconds. To make it less impractical, the issuer of a credential to a Java card certifies only that it trusts the Java card. The card is then free to present any attributes it wants to the relying party. (A different way of handling attributes is possible but not recommended, presumably because of the time it takes; see Footnote 5 of [6].) Security for the relying party depends on the issuer downloading the correct attributes and software to the card, and the user not being able to modify those attributes and software. The card must therefore be tamper resistant against the user. (Or at least tamper responsive, i.e. able to detect tampering and respond by zeroing out storage.)
Whereas a UProve smart card performs only a small portion of the cryptographic computations, the Idemix Java card is an autonomous system that performs all the cryptographic computations by itself, without help from the user’s computer. This takes time: 10.453 seconds for a transaction, i.e. for submitting a credential to a relying party, according to Table 2 of [6]; or 11.665 seconds according to Table 3. (In both cases, with a 1536bit modulus, and not counting a 1.474 second revocation check; revocation is discussed below; the discrepancy between the two figures is not explained.) Some of the computations in Table 2 are labeled as precomputations, but no precomputations can take place if the card is not plugged in. The authors of [6] consider that a 10 second transaction time would be adequate. But I don’t think many Web users will be happy waiting 10 seconds each time they want to log in to a site.
Update. It is possible to implement fullblown privacyfriendly credentials systems very efficiently on a smart card. A nonMicrosoft implementation of UProve on a MULTOS smart card [8], where all the cryptographic computations are carried out by the card, achieves credentialshow times close to 0.3 seconds.
The Idemix card features a revocation mechanism. A card can be revoked by including its secret key in a revocation list. But the secret key is generated in the card when the card is “set up”, and it is not known to the party that sets up the card, nor to the issuers of credentials to the card, nor to the user who owns the card. The secret key can only be obtained by breaching the tamper pretection of the card, hence can only become known to an adversary. So the revocation feature seems useless.
Where does the peculiar idea of listing secret keys in a revocation list come from? It turns out that the cryptographic system of the Idemix card is derived from the cryptographic system of [7] which was designed for media copyright protection, e.g. to authenticate the Trusted Platform Module (TPM) in a DVD player before downloading a protected movie to the player. Apparently hackers extract secret keys of TPMs and publish them on the Web. Copyright owners find those secret keys and blacklist them. Blacklisting secret keys makes sense for copyright protection, but not as a revocation technique for smart cards.
Coming Next…
After reading this post and the previous post, you may be thinking whether privacyenhanced technologies are really a good idea. I will try to answer that question in the next post.
References
[1] 
IBM Research, Zurich.
Specification of the Identity Mixer Cryptographic Library Version 2.3.1.
December 7, 2010.
Available at
http://www.zurich.ibm.com/~pbi/identityMixer_gettingStarted/ProtocolSpecification_232.pdf
.

[2] 
Jan Camenisch and Els Van Herreweghen.
Design and Implementation of the Idemix Anonymous Credential System.
In Proceedings of the 9th ACM conference on Computer and Communications Security.
2002.

[3] 
J. Camenisch and A. Lysyanskaya.
Efficient NonTransferable Anonymous MultiShow Credential System with Optional Anonymity Revocation.
In Theory and Application of Cryptographic Techniques, EUROCRYPT,
2001.

[4] 
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.

[5] 
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.

[6] 
P. Bichsel, J. Camenisch, T. Groß and V. Shoup.
Anonymous Credentials on a Standard Java Card.
In ACM Conference on Computer and Communications Security,
2009.

[7] 
E. Brickell, J. Camenisch and L. Chen.
Direct anonymous attestation.
In Proceedings of the 11th ACM conference on Computer and Communications Security,
2004.

[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.

Although I do not have actual figures for the performance of Idemix, I can tell that running the test cases provided with the library have an acceptable running time, i.e. at most a few seconds whereas I guess that the simple cases (without any of the advanced features) take less than a second.
After our success with the MULTOS implementation of UProve we have now started working on an implementation of Idemix on a smart card. Here, again, we take a different approach then the original developers of the technology. We intend to implement the real Idemix protocols on the card instead of the DAA derivatives. However, we limit ourselves to the same functionality as our UProve implementation, that is selective disclosure. This means that we do not work on the advanced features of the technology, but we hope to get some decent performance by focusing on the core functionality,
Kind regards,
Pim Vullers
This post was also discussed on the Identity Commons Mailing List.
We’ve finished our Idemix smart card implementation, which provides a major improvement over the existing implementations. Issuance takes approximately 2.5 seconds and selective disclosure 1 to 1.5 seconds. This is slower than the UProve work, but it benefits from the multishow unlinkability feature of Idemix.
More information is available in our academic publication:
P. Vullers and G. Alpár. Efficient Selective Disclosure on Smart Cards using Idemix. Available at: http://www.cs.ru.nl/~pim/publications/2013_idman.pdf
Note: This implementation will be used in a pilot project, see https://irmacard.org/.
Congratulations, that’s great performance for Idemix on a smart card. And thanks for the info! I followed the link to the IRMA site and saw that you have an Android implementation available as free and opensource software. That’s nice. Do you know if there would be any IBM patent issues with using it?
Thank you for these posts which clarify the whole picture about ABC systems.
I have a few questions though:
1. Why Persiano and Visconti’s work is not cited or reviewed anywhere?
“An Efficient and Usable Multishow Nontransferable Anonymous Credential System” (Giuseppe Persiano and Ivan Visconti 2004)
2. Why in Uprove the predicate age>21 cannot be represented by two attributes in the credential: (x=age, y=age21). So to prove you are over 21 you must prove the relation:
x= 21 + y, without desclosing neither x nor y.
?
Does this not represent a circumvent solution to the problem?
Thank you in advance
1. According to http://bit.ly/YMAqiw the paper you mention by Persiano and Visconti had 15 citations up to 2010. I confess I haven’t read it. Maybe I should: the nontransferability claim in the abstract is interesting.
2. In UProve you can only prove conjunctions of equations of the form “attribute = constant”. (Chapter 3 of Stefan Brands’ book, which you can find at http://bit.ly/Cs3CQ, covers general boolean combinations of such equations, but that has not been implemented in UProve.) There is no way in UProve to prove formulas that include arithmetic operators or equations involving multiple attrbutes.
In UProve an attribute has an external representation and an internal representation. The external representation is an uninterpreted string. The internal representation is an exponent applicable to a generator of a group (where it is unfeasible to compute discrete logarithms). So the internal representation is an integer modulo q, where q is the order of the group. The external representation is mapped to the internal representation by hashing it. If the external representation is short enough, there is an option to interpret it directly as an integer modulo q without hashing it. But this is only for performance reasons; it does not add any arithmetic capabilities to the system.