Study Group: Anonymous Credentials

The study group on Oct 23th 2012 was done by Anna Lisa and Essam. The topic was anonymous credentials. Basically, the talk focused on the following papers.

• Jan Camenisch and Thomas Groß, "Efficient Attributes for Anonymous Credentials." (PDF)
• Jan Camenisch and Anna Lysyanskaya, "Signature Schemes and Anonymous Credentials from Bilinear Maps." (PDF) 
• Georg Fuchsbauer, "Commuting Signatures and Verifiable Encryption and an Application to Non-Interactively Delegatable Credentials." (PDF) 

Anonymous credentials aim to provide a similar functionality while at the same time not revealing information about the user’s identity when obtaining or showing a credential. In order to construct an anonymous credential system, it is sufficient to exhibit a commitment scheme, a signature scheme, and efficient protocols for (1) proving equality of two committed values; (2) getting a signature on a committed value (without revealing this value to the signer); and (3) proving knowledge of a signature on a committed value.

Chase and Lysyanskaya (in CRYPTO'06) give delegatable anonymous credentials. The functionality of the system can be sketched as follows: each user holds a secret key which she uses to produce multiple pseudonyms Nym. A user A can be known to user O as Nym_{A}^{(O)} and to B as Nym_{A}^{(B)}. Given a credential issued by O for Nym_{A}^{(O)}, A can transform it into a credential for Nym_{A}^{(B)}  and show it to B. Moreover A can delegate the credential to user C, known to A as Nym_{C}^{(A)}. C can then show a credential from O for Nym_{C}^{(D)}  to user D (without revealing neither Nym_{A}^{(C)} nor Nym_{C}^{(A)} ), or redelegate it, and so on.

Jan Camenisch and Thomas Groß (in CCS'08) extend the Camenisch-Lysyanskaya credential system (in SCN'02) with a finite-set encoding. It enables the efficient selective disclosure of binary and discrete-values attributes which are partially highly privacy-sensitive and require a selective disclosure of one attribute while hiding others completely. This method overcomes the severe limitations of existing schemes. We require a solution with two key properties: (1) It only uses at most one attribute base for all binary and finite-set attributes. (2) It only impacts the proof complexity by the number of used attributes instead of the total number.

The major building block of Camenisch-Groß anonymous credential system is Camenisch-Lysyanskaya signatures (in SCN'02). The CL Signatures are as follows:

CL Signatures

Let and L_m, L_e, L_n, L_r and  L be system parameters. is a security parameter.

Key generation: On input L_n, choose an L_n-bit RSA modulus n such that n = pq, p = 2p' + 1, q = 2q' + 1, where p, q, p', and q' are primes. Choose uniformly at random, R_0,...,R_{L-1},S in QR_n . Output the public key (n, R_0, ..., R_{L-1}, S, Z) and the secret key p.

Message space: is the set {(m_0,...,m_{L-1})}.

Signing algorithm: On input m_0,...,m_{L-1}, choose a random prime number e of length l_e>l_m +2 , a random number v of length l_v=l_n + l_m + l_r, where l_r  is a secure parameter. Compute

The signature consist of (e,A,v).
Verification algorithm: To verify that the tuple (e,A,v) is a signature on message ( m_0,...,m_{L-1}) , check that

Efficient Attributes for CL
Camenisch-Groß provide efficient attributes fo CL credential system. Assume that the prover has obtained a CL credential containing E, i.e., signature (A, e,v) on messages m_0 and m_1 with m_1=E. (The attribute typically encodes the user’s secret key).

Efficiently proving that a credential contains an attribute with a given value

The user can convince the verifier that E encodes a given attribute, e.g, she can prove that her identity card states that her hair color is blond. Assume that the attribute hair color blond is encoded by the prime e_j . Thus to convince the verifier that she got issues a credential with this attribute, i.e., that e_j divides E included in her credential, the user engages with the following proof with the verifier:

Showing that an attribute is not contained in E, i.e., how to prove a NOT-relation

Proving that a given e_j is not contained in her credential, the user can do so by showing that there exist two integers a and b such that aE+b e_j=1 . Note that a and b do not exist if  e_j|E . The protocol is as follows: After having computed a and b, the user chooses a sufficiently large random r (about 80 bits larger n) and computes a commitment D=g^{E}h^{r} mod n. The user sends D to the verifier and runs the following protocol with him (where a and b are the secret denoted by α and β, respectively). Finally, the user engages with the verifier in the proof: