April 29, 2010
We established an anonymous credential system on a standard Java Card in our Smart Identities Project.
At 30th September 2009, the German society for computer science (GI) awarded the project with the Innovation Award 2009.
September 29, 2009
The team has also published a number of papers that describe how the different cryptographic protocols can be used to realize privacy-enhancing identity management in practise. While still being research papers, they not primarily solve long standing open problems but rather show how different use scenarios can be addressed.
- Endre Bangerter, Jan Camenisch, Anna Lysyanskaya: A Cryptographic Framework for the Controlled Release of Certified Data. Security Protocols Workshop 2004
- Abhilasha Bhargav-Spantzel, Jan Camenisch, Thomas Groß, Dieter Sommer: User centricity: A taxonomy and open issues. Journal of Computer Security 15(5) 2007
- Jan Camenisch, Dieter Sommer, Simone Fischer-Hübner et al. Privacy and identity management for everyone
- Marit Hansen, Peter Berlich, Jan Camenisch, Sebastian Clauß, Andreas Pfitzmann, and Michael Waidner:Privacy-enhancing identity management
- Jan Camenisch, Abhi Shelat, Dieter Sommer, Simone Fischer-Hübner, Marit Hansen, Henry Krasemann, Gérard Lacoste, Ronald Leenes, Jimmy C. Tseng: Privacy and identity management for everyone. Digital Identity Management 2005
- Jan Camenisch, Dieter Sommer, Roger Zimmermann: A General Certification Framework with Applications to Privacy-Enhancing Certificate Infrastructures 2006
- Michael Backes, Jan Camenisch, Dieter Sommer: Anonymous yet accountable access control. WPES 2005: 40-46
- Jan Camenisch, Thomas Groß, Dieter Sommer: Enhancing privacy of federated identity management protocols: anonymous credentials in WS-security. WPES 2006: 67-72
- Jan Camenisch, Abhi Shelat, Dieter Sommer, Roger Zimmermann: Securing user inputs for the web. Digital Identity Management 2006: 33-44
- Jan Camenisch, Thomas Groß, Thomas S. Heydt-Benjamin: Rethinking accountable privacy supporting services: extended abstract. Digital Identity Management 2008: 1-8
Considering the use of anonymous credentials for government issued identities, one finds that the number of attributes certified is quite large. The original scheme, however, would loose efficiency with the number of attributes becoming larger. Also, consider the case of a certificate stating the date of birth. If one now would want to prove that one is between 12 and 16 years old, the known method to do so is not practical on computationally challenged devices such as smart cards which would be the target platform for electronic identity cards.
- Jan Camenisch, Thomas Groß: Efficient attributes for anonymous credentials. ACM CCS 2008, got invited as a selected paper for the TISSEC journal.
- Jan Camenisch, Rafik Chaabouni, Abhi Shelat: Efficient Protocols for Set Membership and Range Proofs. ASIACRYPT 2008
When using anonymous authentication in the real world, there are additional requirements that have to be met. One of these requirements is the one to revoke
certificates. The typical approach of publishing a list of serial numbers of revoked certificates does unfortunately not work as this would compromise privacy.
In 2002 Camenisch and Lysyanskaya solved the problem of revocation for anonymous credentials for the first time, although the concept of anonymous credentials
was first proposed about ten years earlier.
- Jan Camenisch, Anna Lysyanskaya: Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. CRYPTO 2002. [PDF]
- Jan Camenisch, Markulf Kohlweiss, Claudio Soriente: An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. PKC 2009
The core research challenge for getting privacy preserving authentication is to find a signature scheme to issue certificates such that later-on one can efficiently prove by some sort of zero-knowledge protocols that one got issued a signature by some party on a message which, e.g., contains a birth date proving that one is indeed between 12 and 16 years old. In theory, this can be done with any signature scheme as any (mathematical) statement can be proven to be true in zero-knowledge. If, however, one is looking for a system that is practical, standard digital signatures cannot be used as then the proof would be far to inefficient.
A core innovation was a new signature scheme and zero-knowledge protocol that allow one to do this very efficiently. The first seed of this technology laid in 1998, and then over the years, the schemes were improved until they became really practical (2001). Later on the team also came up with alternatives that are based on different cryptographic assumptions and settings (2004 – bi-linear maps/elliptic curves). Depending on the implementation requirements, these alternative are preferable to the earlier proposals.
- Jan Camenisch, Markus Stadler: Efficient Group Signatures Schemes for Large Groups, CRYPTO 1997. [PDF]
- Jan Camenisch, Markus Michels: Separability and Efficiency for Generic Group Signature Schemes. CRYPTO 1999. [PDF]
- Giuseppe Ateniese, Jan Camenisch, Marc Joye, Gene Tsudik: A Practical and Provably Secure Coalition-Resistant Group Signature Scheme. CRYPTO 2000. [PDF]
- Jan Camenisch, Anna Lysyanskaya: An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. EUROCRYPT 2001. [Full Paper]
- Jan Camenisch, Anna Lysyanskaya: A Signature Scheme with Efficient Protocols. SCN 2002. [PDF]
- Jan Camenisch, Jens Groth: Group Signatures: Better Efficiency and New Theoretical Aspects. SCN 2004. [PDF]
- Jan Camenisch, Anna Lysyanskaya: Signature Schemes and Anonymous Credentials from Bilinear Maps. CRYPTO 2004. [PDF]
August 18, 2009
contributed by Gregory Neven, IBM Zürich, September 2008
This document is intended as a quick introduction to anonymous credentials for a technically, but not cryptographically trained audience. We avoid all mathematical and cryptographic detail here; rather, we try to sketch a black-box API that captures the main functionalities and security features of anonymous credentials, allowing the reader to quickly gain an intuition into what anonymous credentials can and cannot do.
1. Communication model
In the typical “wine-shop” use case, the User is the customer, the Verifier is the merchant, and the Issuer is the government, or any other instance that is trusted to issue age certificates. The User engages in an Issue protocol with an Issuer to obtain a valid credential on a certain set of attributes. The credential is valid under the Issuer’s public key pk, of which only the Issuer knows the corresponding secret key sk. In its simplest form, the Issue protocol is a two-round interaction where the User submits a request containing her attributes, and the Issuer certifies the fact that the User has the claimed attributes by returning the credential; more generally, the credentials can be generated through a multi-round interaction.The User convinces a verifier that she has a certain set of attributes by engaging in a Show protocol. Again, this can be a simple two-round protocol or a more complex interaction.
Intuitively, an anonymous credential can be thought of as a digital signature by the Issuer on a list of attribute-value pairs, e.g. the list
(fname=”Alice”, lname=”Anderson”, bdate=”1977/05/10”, nation=”DE”).
The most straightforward way for the User to convince a Verifier of her list of attributes would be to simply transmit her credential to the Verifier. This approach has a number of disadvantages, most notably
- that the User has to reveal all of her attributes so that the Verifier can check the signature;
- that the Verifier can reuse the credential to impersonate Alice wrt other Verifiers.
With anonymous credentials, the User never transmits the credential itself, but rather uses it to convince the Verifier that her attributes satisfy certain properties – without leaking anything about the credential other than the shown properties. This has the obvious advantage that the Verifier can no longer reuse the credential to impersonate Alice. Another advantage is that anonymous credentials allow the User to reveal a selected subset of her attributes. In the example above, Alice could for example reveal her first name and last name, but keep her birth date hidden. Stronger even, apart from showing the exact value of an attribute, the User can even convince the Verifier that some complex predicate over the attributes holds. In particular, she can demonstrate any predicate consisting of the following operations:
- Integer arithmetic: att+c , att+att , att•c : sum of attributes and/or constants, product of attributes with constants
- Comparative: exp1 = exp2 , exp1 < exp2 , exp1 > exp2 , exp1 ≤ exp2 , exp1 ≥ exp2 : compare arithmetic expressions over attributes/constants
- Logical: pred1 AND pred2 , pred1 OR pred2
Note that revealing a subset of attributes comes down to the special of showing that the predicate att1 = val1 AND att2 = val2 AND … holds. In the example above, Alice could show that she’s an overage national of an EU country by showing that he has a credential satisfying bdate ≤ today – 18y AND ( nation=”DE” OR nation=”FR” OR … ) . The Show protocol does not leak any information other than the truth of the statement. So in the example above, not only does Alice’s name remain hidden from the Verifier, but so do her exact birth date and nationality; the only information leaked is that her birth date is more than 18 years ago, and that her nationality is one of the EU countries. The Show protocol also allows to prove statements about multiple credentials. For example, when Alice’s passport and credit card are anonymous credentials issued by her government and her bank, respectively, then she can show to a Verifier that she has a valid passport certifying that she is over 18 years of age and a valid credit card issued to the same name: pass.bdate ≤ today – 18y AND pass.fname = ccard.fname AND pass.lname = ccard.lname .
3. Verifiable encryption
There are situations where multiple parties are involved in the same transaction, and each of these parties need different information from the User. For example, in the wine shop use case, the merchant needs to know whether Alice is overage, and the shipping company needs to know her address. The merchant should not learn her address, but wants to be sure that she gives her real address to the shipping company, and not that of an underage friend. Another example is that the merchant may require Alice to submit her real identity to a trusted third party (TTP), so that in case of dispute or fraud the TTP can be contacted to reveal Alice’s identity. The merchant wants to be sure that Alice submitted her real identity to the TTP, and not some bogus identity. The TTP in this case plays the role of an identity escrow agent. More generally, there are situations where the Verifier wants to be sure that the User submitted a certain piece of personal data to an External Recipient, but the content of these data should remain hidden from the Verifier. A “low-tech” solution to this problem is to have the User send this data directly to the External Recipient, who either returns a receipt to the User that the User can show to the Verifier, or who contacts the Verifier directly to acknowledge that it received the correct data. This situation is depicted in the upper picture below.
A more “high-tech” setting is depicted in the lower picture. Here, the User sends the required data to the Verifier, but encrypted under the public key of the External Recipient. When she uses a verifiable encryption scheme, the User can prove predicates about the content of the encrypted data of the same form as those in the Show protocol to the Verifier, to assure the Verifier that the ciphertext C actually contains the correct data. (Without such a proof, the User could easily encrypt bogus data, since the Verifier does not know the decryption key skER anyway.) The External Recipient does not need to be online at the time of the transaction; rather, the Verifier can forward the ciphertext only when it is actually needed, e.g. when the item is being shipped, or when a dispute actually occurs.
4. Limited spending
4.1 One-time spending
Because of the anonymity of anonymous credentials, a Verifier cannot tell whether two successful logins were initiated by the same user or by different users. This is good for privacy, but becomes a problem in situations where one wants to place a bound on the number of times that a single credential can be used. We first sketch a simple solution for the special case where a credential can only be used (or “spent”) once, and then present a more advanced solution that works for arbitrary bounds.
When a credential is only to be used once (a so-called “one-time credential”), the issuer includes an additional attribute credentialID in the credential that is set to a random value. To log into the system, the User has to reveal the value of credentialID to the Verifier. The Verifier simply maintains the list of credentialIDs that it has seen, and denies access when the revealed credentialID already occurs in the list.
This solution works fine as long as there is only a single Verifier, or as long as all Verifiers have access to a common database that keeps track of spent credentialIDs. It is impossible to prevent a User from overspending a one-time credential by using it at multiple Verifiers that are not in constant communication with each other, but there are ways to detect such behavior after the fact. Namely, as part of the showing protocol, the Verifier can choose a random challenge chall, which the User has to respond to with a value resp that computed as a function of chall and some attribute that uniquely identifies the User, e.g. name, together with a proof that resp was correctly computed. The protocol is such that a single challenge-response pair (chall, resp) does not reveal anything about name, but name is easily computable from two pairs (chall, resp) and (chall’, resp’) whenever chall ≠ chall’ (which happens with overwhelming probability if the challenges are long enough). By storing triples of the form (credentialID, chall, resp) for each login, Verifiers can later on compare their lists to detect overspent credentials and reveal the identity of fraudulent users.
4.2 Multi-time spending
The above technique is easily extended to allow spending up to n times as follows: include n different random attributes credentialID1,…,credentialIDn in the credential, and let the User reveal one of them each time she logs in. This quickly becomes inefficient however, as the number of attributes in the credential grows linearly with the spending bound. Also, the Issuer has to fix a single bound once and for all; it would be nice if different Verifiers could impose their own bounds on-the-fly.
A more powerful approach is the following. As an extra attribute, each credential includes a random hash key HK for a keyed hash function H. The hash function is such that it allows the User to prove statements of the form
HHK(somestring) = somevalue
as part of the showing protocol, whereby the hash input and output are revealed, but HK remains hidden. When the User logs in for the i-th time, she reveals HHK(i) and proves that the value was correctly computed from HK as included in her credential. The Verifier checks that 1 ≤ i ≤ n and that the hash value does not yet occur in its database.
Since the hash function takes any bit string as input, different web sites can easily impose their own spending limits by collecting hash values of the form
HHK(websiteID, i )
from users. The system is also easily extended to interactive challenge-response protocols that allow after-the-fact detection of abuse.
In some situations it may desirable to create permanent pseudonymous user accounts. This could be for efficiency reasons, because the user does not want to re-prove that it satisfies all access requirements at each login, or for functionality reasons, for example to store the user’s preferences or a list of previous transactions across several sessions. The actions that a user performs under the same pseudonym thereby unavoidably become linkable, but otherwise no new information should be leaked to the server. In particular, it should be impossible to link different pseudonyms of the same user together, whether it be at the same server or across different servers.
So far, the requirements can be satisfied simply by letting each user set up a random username-password pair. The problem with this solution is that the user can set up an account, prove that she satisfies some requirements, and then sell her password to users who do not satisfy these requirements. Since there is no connection between the user and the pseudonym, the user has no incentive not to share her credentials with others.
Anonymous credentials provide a better solution. Namely, each of the user’s credentials contains a master secret as a special attribute. Each user has her own master secret, and the same master secret is present in all of a user’s credentials. The issuing of credentials is done in a special way so that the same master secret must be used in all of the user’s credentials, without revealing its value to the issuer however. The idea is that the master secret is the one secret that the user holds very dearly, as it is essentially the cornerstone of her entire electronic identity.
The user’s “pseudonym” is not a self-chosen name or a random bit string, but rather a special cryptographic token that is non-deterministically derived from the master secret. (Meaning, you can generate many different pseudonyms from the same master secret.) The corresponding “password” is the master secret itself. Rather than simply sending the master secret to the server to log in, the user proves in a cryptographic way that she knows the master secret underlying her pseudonym, but without revealing its value.
The cryptographic pseudonyms thus derived have the property that (1) no one can tell whether two pseudonyms were derived from the same master secret or not, and (2) it is impossible to successfully log in under a pseudonym without knowing the underlying master secret.
If the user now wants to share her account at a server with other users, then she has to give away her master secret, which immediately gives access to all other servers where she ever registered. It is hoped that this all-or-nothing situation (either you share nothing, or you share your entire identity) forms enough of a disincentive to prevent users from sharing their credentials.
August 5, 2009
We were the first to establish an autonomous anonymous credential system on a standard Java Card. This prototype implementation of an Identity Mixer variant that combines strong authentication and privacy properties. It allows a user to proving possession of the card as well as selectively disclose identity attributes, while keeping all her other personal data perfectly confidential. We see this technology as potential complement to electronic identity cards.
See the Smart Identity Card portal page.
In particular the card has the following properties.
- Autonomous credential system – the anonymous credential system completely resides on card and does not depend on joint computation with the PC or terminal. It is secure in face of a untrusted terminal.
- Secure keylength – in our prototype we used 1536-bit Strong RSA keys, yet the card is also capable of longer keylength such as 1984 bits.
- Transaction times on the order of seconds – an standard proof of possession with 1536-bit keys takes 7.5 sec pre-computation time while the user makes her policy consent decision and 2.5 actual response time after the user entered the policy.
We used the following Java Card:
- NXP JCOP 41 v2.2, mask 36. This card is in the midfield of available smart cards, not top of the line.
This project received the 2009 Innovation Award of the German society for computer science (comparable to the ACM in Germany).
August 2, 2009
We offer the IDEMIX Library for download for free via the PrimeLife project: