- 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: