September 29, 2009

Extensions – Building Blocks for an Identity Management Framework

Posted in Publications tagged , , , , at 17:13 by Thomas Groß

Anonymous authentication is just the basic feature provided by our technologies. Indeed, it is often not enough to learn that a person has the right to access a certain resource or service as anonymity can be abused. Therefore, the research challenge here is to design methods limit the abuse that dishonest parties and/or to be able to investigate cases of abuse after the fact. We were able to designed a number of way for this (A-C below). Apart from these extensions the team was also investigating better proof protocols for anonymous authentication, i.e., protocols that allow one to prove possession of a certificate and properties about the certificate (D below)

A) Controlling information release

We invented the primitive of verifiable encryption which allows one to encrypt additional information under a third party’s public key and to define a condition under which the party is allows to decrypt this. The third party is only involved at the time of decryption. So for instance, this primitive could be used as follows: to access a document I prove that I was authorized by my company to do so (i.e., I own a certificate issued by my company that states this) and in addition provide an encryption of my identity for a trusted third party. Thus, the document provider does not learn who I am, but in case of misuse can ask the trusted third party for help in investigation.

  1. Jan Camenisch, Victor Shoup: Practical Verifiable Encryption and Decryption of Discrete Logarithms. CRYPTO 2003
  2. Jan Camenisch, Ivan Damgård: Verifiable Encryption, Group Encryption, and Their Applications to Separable Group Signatures and Signature Sharing Schemes. ASIACRYPT 2000

B) Limiting the use of anonymous credentials

While some certificates or credentials such as a driver’s license have no limitation on how many times they can be used, other such as electronic money should not be usable more than once. Also, in order to prevent misuse of, e.g., a subscription credentials, one might want to limit the number of times a credential can be used be given time period. With non-anonymous certificates or access control enforcing such limitations is trivial: one just keep track of the use of the individual certificates and then rejects request with certificates that have been over-used. With anonymous certificates, this is not possible as each individual use shall not be linkable to any other use. Nevertheless, we were able to design cryptographic protocols that implement such controls. Sounding paradoxical, the cryptography ensures that transactions are completely anonymous as long at the credential is not over-used and as soon as the credential is used once to much the identity of the abuser is revealed. The research papers listed below present different methods for different means to define what “over-use” means, e.g., in Compact E-Cash a credential can be used up to n times, while other paper consider more general rules that take into account different time periods or different communication partners (e.g, a credential can be used n times per hour with this group of service providers and k times with that group).

  1. Jan Camenisch, Susan Hohenberger, Anna Lysyanskaya: Compact E-Cash. EUROCRYPT 2005
  2. Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya, Mira Meyerovich: How to win the clonewars: efficient periodic n-times anonymous authentication. ACM Conference on Computer and Communications Security 2006
  3. Jan Camenisch, Susan Hohenberger, Anna Lysyanskaya: Balancing Accountability and Privacy Using E-Cash (Extended Abstract). SCN 2006
  4. Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya, Mira Meyerovich: How to win the clonewars: efficient periodic n-times anonymous authentication. ACM CCS 2006
  5. Jan Camenisch, Anna Lysyanskaya, Mira Meyerovich: Endorsed E-Cash. IEEE Symposium on Security and Privacy 2007

C) Securing Certificate with Hardware

Being digital object, certificates can easily be shared among different users. With non-anonymous certificates such sharing might be detected if the certificate gets used too frequent and thus the certificate can be revoked based on this. In fact, the approach we describe about under point B) implements the same control for anonymous certificates. Another possibility is to use secure hardware devices such as Java Cards to store the certificates and to execute the proof protocols. We invented a method that allows one to bind anonymous certificate to the TPM chip such that a certificate can only be used together with given TPM chips. This not only prevents users from sharing their certificates put also protects the certificates from viruses and fishing attacks as they are just by themselves useless. Another means to protect certificates is by using a Java Card as in the smarter identity project.

  1. Jan Camenisch: Protecting (Anonymous) Credentials with the Trusted Computing Group’s TPM V1.2. SEC 2006: 135-147
  2. Patrik Bichsel, Jan Camenisch, Thomas Gross, Victor Shoup: Anonymous Credentials on a Standard Java Card. ACM Conference on Computer and Communications Security 2009

D) Proof Protocols

As described above, efficient zero-knowledge proofs of knowledge are a main building block of anonymous credentials and making them as efficient as possible is key for practical solutions. In these area the team has made significant contributions as well.

  1. Endre Bangerter, Jan Camenisch, Ueli M. Maurer: Efficient Proofs of Knowledge of Discrete Logarithms and Representations in Groups with Hidden Order. Public Key Cryptography 2005
  2. Jan Camenisch, Aggelos Kiayias, Moti Yung: On the Portability of Generalized Schnorr Proofs. EUROCRYPT 2009

In an other line of work, the team developed protocol that allow one set-up the infrastructure of anonymous credential in a secure way.

  1. Jan Camenisch, Markus Michels: Proving in Zero-Knowledge that a Number Is the Product of Two Safe Primes. EUROCRYPT 1999
  2. Joy Algesheimer, Jan Camenisch, Victor Shoup: Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products. CRYPTO 2002

August 18, 2009

A quick introduction to anonymous credentials

Posted in Concepts, Cryptography, Tutorials tagged , , , , , , at 20:21 by Thomas Groß

contributed by Gregory Neven, IBM Zürich, September 2008

Also available as PDF.

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

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

2. Anonymous credentials and selective showing of attributes

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.

Model Comparison

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 challchall’ (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 ≤ in 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.

5. Cryptographic pseudonyms

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.