In an anonymous credential scheme there are three participants: issuer, user(prover), verifier.

Issuer creates a certificate to user which contains a list of user's attributes and issuer's signature(use BBS+ signature). This protocol is formally called credential issuance protocol.

The user who is in possession of that credential can selectively disclose some parts to some verifier. This protocol is formally called presentation protocol.

• Setup: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.

  common params:

  • g0, g1, (g2, ..., g_{L+1}) are elements from G1.

  • h0 is a generator of G2.

• KeyGen: sample x from uniform dist on Zp, output sk = x, pk = h0^x.

• Sign(sk, m1, ..., mL): choose two random numbers E and s from Zp. Compute B = g0 * g1^s * (g2^m1 ... * g_{L+1}^mL), then let A = B^{1/(E+x)}. The sig is (A, E, s).

• Verify(pk, m1, ..., mL, sig): decode sig as (A, E, s), and check if e(A, h0^E * pk) == e(B, h0).

In this subsection, we give an example of non-interactive statistical proof of knowledge protocol which proves that the public key is generated as specfied in the BBS+ signature scheme. That is, π = SPoK{x: w = g2^x && _g2 = _g1^x} which can be translated as the prover proves knowledge of x such that g2^x = w and _g2 = _g1^x. And w, g2, _g1, _g2 are assumed to be public.

The protocol we give is a standard sigma protocol. It consists three steps, namely, commit-challenge-response. And the proof π = {C, S}

1. commitment(prover):

   r = rand{Zp}
   
   t1 = g2^r
   
   t2 = _g1^r

2. proof(prover):

   P = t1 || t2 || g2 || _g1 || w || _g2    //join them together in binary format
   
   C = hash_to_int(P)    //C is challenge
   
   S = (r + C * x) % p     //response to verifier

3. verify(verifier):

   _t1 = g2^S * w^((-c))
   
   _t2 = _g1^S * _g2^((-c))
   
   _P = _t1 || _t2 || g2 || _g1 || w || _g2
   
   _C = hash_to_int(_P)      //do the same thing like prover, everything is public
   
   check if C == _C     // use C to compare with _C, which was calculated just now

In the presentation protocol specified in section 3, the core part is to prove knowledge of BBS+ signature (A,e,s), namely,

π = SPoK{ (e, r2, r3, s', {mi}): _A/d = A'^(-e) * h0^r2 && g1 * MulAll(h_i^mi) = d^r3 * h0^(-s') }

Given an array of attribute's names AttributeNames, the issuer's key pair is generated as follows:

1. Sample a random element x from Zp.

2. Compute w = g2^x.

3. Sample a random element _g1 from G1. And compute _g2 = _g1^x.

4. Generate non-interactive proof of knowledge π = PoK{x: w = g2^x && _g2 = _g1^x} = {C, S} according to section 1.2 which we reproduce here.

   • r : sample a random element r from Zp
   • t1 : compute t1 = g2^r.
   • t2 : compute t2 = _g1^r.
   • C : C = H(t1 || t2 || g2 || _g1 || w || _g2)
   • S : S = (r + C * x) mod p

5. Sample an array of elements from G1 for AttributeNames. For each attribute in AttributeNames, compute HAttrs[i] = random(G1)

6. Sample two random elements from G1: HRand and HSk.

7. Set issuer's public key ipk = (w, _g1, _g2, π, HAttrs, AttributeNames, HRand, HSk), and private key isk = x.

8. Return ipk and isk.

The following snippets in golang gives the reference data structures for issuer's key pair.

type IssuerSecretKey struct {
    x BigNum
}

type IssuerPublicKey struct {
    AttributeNames []string
    HAttrs         []G1Point // one G1-element for one attribute
    HRand          G1Point   // a random G1 point 
    HSk            G1Point   // a random G1 point to encode user's secret key 

    w              G2Point   // element from G2  
    _g1            G1Point   // point of G1
    _g2            G1Point   // point of G1

    //PoK{x: w = g2^x && _g2 = _g1^x}
    C              BigNum    // challenge
    S              BigNum    // response
}

The issuance protocol is an interactive protocol which consists of the following steps:

1. The issuer sends a random nonce to the user.

2. The user creates a Credential Request using the public key of the issuer, user secret, and the nonce as input.

   The request consists of a commitment to the user secret (can be seen as a public key) and a zero-knowledge proof of knowledge of the user secret key.

   The user sends the credential request to the issuer.

3. The issuer verifies the credential request by verifying the zero-knowledge proof

   If the request is valid, the issuer issues a credential to the user by signing the commitment to the secret key together with the attribute values and sends the credential back to the user

4. The user verifies the issuer's signature and stores the credential that consists of the signature value, a randomness used to create the signature, the user secret, and the attribute values.

In short, this can be summarized in the following diagram:

   Issuer  ------------------------  Prover 
    
             -- nonce(BigNum) --> 
        
             <-- CredRequest ---
        
             --- Credential ---> 

• CredRequest contains a commitment Nym to user's master secret which is of the form HSk^(sk) and a zk-PoK of Nym.

• Credential contains the BBS+ signature on attributes and Nym.

User will generate the credential request with attribute values and nonce as input. This is done as follows:

1. Sample a random element sk from Zp as user's master secret.
2. Compute Nym = HSk^(sk) as a commitment to user's master secret.
3. Generate zero knowledge proof π = PoK{sk: Nym = HSk^sk} = (C, S) as illustrated in section 1.2 which we reproduce here.
   • Sample a random element r from Zp.
   • Compute t1 = HSk^r.
   • Compute challenge C = H(t1 || HSk || Nym || nonce).
   • Compute response S = (r + C * sk) mod p.

The following snippets in golang gives the reference data structures for credential request.

type CredRequest struct {
   Nym             G1Point  //commitment to user's master secret
   IssuerNonce     BigNum   //nonce 

   //PoK that Nym is constructed as in the issuance protocol
   // i.e. PoK{(sk): g1^sk = Nym }
   C               BigNum   //challenge in Sigma-protocol
   S               BigNum   //response in Sigma-protocol
   Attrs           []BigNum //user's attributes
}

After receiving credential request from user, issuer verify π = (C, S) and generates credential for user. Issuer needs an array input attrs (TBD). The credential is generated using issuer's private key isk as follows:

1. Sample two random elements e, s from Zp.
2. Compute b = g1 · HRand^s · Nym · MulAll(HAttrs[i]^(Attrs[i]))
3. Compute A = b^(1/(e+x)).
4. Return credential (A, b, e, s, Attrs)

The following snippets in golang gives the reference data structures for credential.

type Credential struct {
   A               G1Point
   b               G1Point
   e               BigNum
   s               BigNum
   Attrs           []BigNum
}

In the presentation protocol, the prover tries to convince the verifier that he knows some secret input such that some predicate is true. A typical example of predicate is that the prover is in possession of an anonymous credential, and he can selectively disclose some attributes while hiding the other attributes.

Before we give the proving algorithm, we list the information that the prover has.

• User's secret key sk and its commitment Nym.
• Attribute values attrs = (a1,...,aL)
• BBS+ signature (A, b, e, s)
• extra input
  • (D, I): attribute predicate, describe what attributes will be disclosed. If D[j]==1, I[j]=attrs[j]=aj, else I[j]=null

Start to sign:

1. Randomize A: sample a random element r1 from Zp*, and compute A' = A^r1.

2. Compute _A = A'^(−e) · b^r1, r3 = 1/r1.

3. Sample an element r2 from Zp.

4. Compute d = b^r1 · HRand^(-r2), s' = s - r2·r3.

5. Generate zero knowledge proof π = PoK{ (sk, {ai}_hidden, e, r2, r3, s') } such that

   • _A/d = A'^(-e) · HRand^r2 and
   • g1 · MulAll(hi^ai_reveal) = d^r3 · HRand^(-s') · HSk^(-sk) · MulAll(hi^(-ai_hidden)).

   This proof can be generated as illustrated in section 1.2 which we reproduce here.

   • r_ai : for i belongs to _D(attributes not disclosed), means D[i]==0
   • r_e : random from Zp
   • r_r2 : random from Zp
   • r_r3 : random from Zp
   • r_s' : random from Zp
   • r_gsk : random from Zp
   • E : E = HSk^r_gsk
   • L : L = H1(bsn)^r_gsk, to hide gsk
   • t1 : t1 = A'^r_e · h0^r_r2, to hide e and r2
   • t2 : t2 = d^r_r3 · h0^r_s' · E^(-1) · MulAll(hi)^r_ai, to hide r3, s and ai to be hide
   • c' : c' = H(A', _A, d, nym, t1, t2, L, g1, h0, ... , hL, w)
   • n : nonce, with τ bit length, randomly generated again
   • m : message to sign
   • c : c = H(n, c', m, bsn, (D, I), SRL)
   • s_gsk : s_gsk = r_gsk + c · gsk
   • s_ai : s_ai = r_ai - c · ai, for i belongs to _D(attributes not disclosed)
   • s_e : s_e = r_e - c · e
   • s_r2 : s_r2 = r_r2 - c · r2
   • s_r3 : s_r3 = r_r3 - c · r3
   • s_s' : s_s' = r_s' - c · s'
   • π : {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}, i belong to _D
   • (A', _A, d, nym, π) : signature done.

Output is (A', _A, d, nym, π), where π = {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}

Suggested data structure:

// Signature specifies a signature object that consists of
// a_prime, a_bar, b_prime, proof_* - randomized credential signature values
// and a zero-knowledge proof of knowledge of a credential
// and the corresponding user secret together with the attribute values
// nonce - a fresh nonce used for the signature
// nym - a fresh pseudonym (a commitment to to the user secret)
type Signature struct {
    APrime             G1Point  // randomized credential signature values
    ABar               G1Point  // randomized credential signature values
    BPrime             G1Point  // randomized credential signature values

    /* challenge in sigma-protocol */
    ProofC             BigNum
    /* response in sigma-protocol */
    ProofSSk           BigNum
    ProofSE            BigNum
    ProofSR2           BigNum
    ProofSR3           BigNum
    ProofSSPrime       BigNum
    ProofSAttrs        []BigNum

    Nonce              BigNum   // a fresh nonce used for the signature
    Nym                G1Point  // a fresh pseudonym (a commitment to to the user secret)
    ProofSRNym         BigNum   // ???
}

Verifier's information:

• (A', _A, d, nym, π) : from signer
• {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s', n} : parse π

Start to verify:

• A' ?= 1 of G1 : false: verify failed. true: continue.
• e(A', w) ?= e(_A, g2) : false: verify failed. true: continue. This is ZKPoK for A.
• π ---> {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s', n} : parse π
• ~L : ~L = H1(bsn)^s_gsk · nym^(-c) . This is ZKPoK for gsk.
• ~t1 : ~t1 = A'^s_e · h0^s_r2 · (_A/d)^(-c) . This is ZKPoK for e, r2.
• ~t2 : d^s_r3 · h0^s_s' · h_sk^(-s_gsk) · MulAll(hi^(-s_ai)) · (g1·MulAll(hi^ai))^(-c)
  • the i above, first MulAll( ) belongs to _D, where D[i]==0(false)
  • the i above, second MulAll( ) belongs to D, where D[i]==1(true)
  • This is ZKPoK for r3, s'(s), gsk, ai of _D.
• c' : c' = H(n, H(A', _A, d, nym, ~t1, ~t2, ~L, g1, h0,... , hL, w), m, bsn, (D, I))
• c ?= c' : false: verify failed. true: verify success.

[CL02]. J. Camenisch and A. Lysyanskaya. A Signature Scheme with Efficient Protocols. SCN 2002.

[CL04]. J. Camenisch and A. Lysyanskaya. Signature Schemes and Anonymous Credentials from Bilinear Maps. Crypto 2004.

[BBS04]. D. Boneh, X. Boyen, and H. Shacham. Short Group Signatures. Crypto 2004.

[BBS+]. Man Ho Au, Willy Susilo, and Yi Mu. Constant-Size Dynamic k-TAA. SCN 2006.

[CDL16]. Camenisch, Jan, Manu Drijvers and Anja Lehmann. Attestation Using the Strong Diffie Hellman Assumption Revisited, ECCV 2016.