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 pairing(A, h0^e * pk) == pairing(B, h0).

Suppose we have initialized the Issuer's key pair, now we need to generate a Non-interactive Signature Proof of Knowledge. And the public paramaters have been initialized, g1, g2 are generator of G1,G2 seperately. n is order.

g1, g2, n       //public parameters, g1, g2 are generator of G1,G2 seperately. n is order.
(G1, G2, GT)    //public parameters, paring groups

x = rand{Zp}    //issuer's secret key, an integer number
{               //issuer's public key, a turple with some public infomation
    w   = g2^x
    _g1 = randPoint{G1}     // randomly choose a point from G1*
    _g2 = _g1^x
    pC          // determined in proof step
    pS          // determined in proof step
}

For Issuer, Prove knowledge of the private key x by creating π <--$-- SPK{x: w = g2^x && _g2 = _g1^x}. In following steps, π = {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 bytes format
   
   C = hash(P) % n     //C is challenge
   
   S = (r + C * x) % n     //response to verifier

3. verify(verifier):

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

In Issuance(Join) Phase, there is also a SPK of User's private key sk π <--$-- SPK{(gsk): Q =h_sk^gsk}(nonce), π = {C, S}

In Sign & Verify Phase, the SPK of User's BBS+ signature (A,e,s) is

π <--$-- SPK{ (e, r2, r3, s'):

{

_A/d = A'^(-e) * h0^r2 &&

g1 * MulAll(h_i^mi) = d^r3 * h0^(-s')

}

// {mi} is turple of message, such like blocks.

r1 = rand(Zp)

r2 = rand(Zp)

r3 = 1/r1               // (mod n)

A' = A^r1

_A = A'^(-e) * B^(r1)   // = A'^x

d = B^r1 * h0^(-r2)

s' = s - r2*r3

// π = {C, S_e, S_r2, S_r3, S_s'}

// take random numbers from Zp for e, r2, r3, s' as r_e, r_r2, r_r3, r_s'

t1 = A'^r_e * h0^r_r2

t2 = d^r_r3 * h0^r_s' * E^(-1)

C = Hash(A' + _A + d + t1 + t2 + g1 + h_{0~max})

// then we get the proof π:

S_e = r_e - C*e
S_r2 = r_r2 - C*r2
S_r3 = r_r3 - C*r3
S_s' = r_s' - C*s'

// Verify:

t1' = A'^S_e * h0^S_r2 * (_A/d)^(-C)
t2' = d^S_r3 * h0^S_s' * (g1 * MulAll(h_i^mi))^(-C)

C' = Hash(A' + _A + d + t1' + t2' + g1 + h_{0~max})

C ?= C'

// done

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 g1^(ms) * g2^(credS) and a zk-PoK of Nym.

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

type IssuerSecretKey BigNum     // call it 'isk', a random number from Zp

type IssuerPublicKey struct {   // call it 'ipk'
   AttributeNames  []string
   HSk             ECPoint    // used to hide user's master secret, a random point from G1*
   HRand           ECPoint    // used to encode s, a random point from G1*
   HAttrs          []ECPoint  // used to encode attributes
   W               ECPoint2   // W equals to h0^x 
   
   // PoK that the public key is valid. 
   BarG1           ECPoint    // BarG1 is a random point from G1*
   BarG2           ECPoint    // BarG2 = BarG1^isk
   ProofC          BigNum     // challenge in Sigma-protocol
   ProofS          BigNum     // response in Sigma-protocol
}

type CredRequest  struct {
   Nym             ECPoint  //commitment to user's master secret
   IssuerNonce     BigNum   //nonce 
   
   //PoK that Nym is constructed as in the issuance protocol
   // i.e. PoK{(ms, credS): g1^ms * g2^credS = Nym }
   ProofC          BigNum   //challenge in Sigma-protocol
   
   //response in Sigma-protocol
   ProofS1         BigNum   
   ProofS2         BigNum   
}

type Credential struct { // (A, e, s) is BBS+ signature 
   A               ECPoint 
   B               ECPoint
   e               BigNum 
   s               BigNum
   Attrs           [][]byte 
   Attrnames       []string
}

Notice: This protocol is based on DAA+ protocol from [CDL16], some steps have been changed in order to satisfy our demands.

Roles:

• I - Issuer
• U - User
• V - Verifier(also an user)

Steps:

1. Issuer Setup
2. Issuance ( Issuer -> User )
3. Presentation ( Prover -> Verifier )

Public Parameter:

• τ : security parameter

• e: G1 x G2 -> GT : bilinear map defined on G1 and G2

• G1 G2 GT : groups with pairing function defined, eg: bn256

• p: prime order of bilinear group

• g1: G1's generators

• h0 h1 ... hL: elements from G1

• g2 : G2's generators

• H1:{0,1}* --> G1 : a hash function to map string to G1 element

• H: {0,1}* --> {0,1}τ : a hash function to map string to Zp number

Issuer

generate Issuer's key pair:

• x : random from Zp, as secret key, called isk
• ipk : Issuer's public key
  • w : w = g2^x, corresponding public key
  • _g1 : random element from G1*
  • _g2 : _g2 = _g1^x
  • π <--$-- SPK{x: w = g2^x && _g2 = _g1^x} - π = (C, S)
    • r : r = rand{Zp}
    • t1 : t1 = g2^r, to hide x
    • t2 : t2 = _g1^r, to hide x
    • C : C = H(t1 || t2 || g2 || _g1 || w || _g2) //join them together in bytes format, refer to [Fiat-Shamir heuristic]
    • S : S = (r + C * x) % p
  • AttributeName : @input, a string array of attributes.
  • HAttr : h[i] = random(G1), len(HAttr) = len(AttributeName), h1, h2, h3 ... hL
  • HRand : h0 = random(G1)
  • HSk : h_sk = random(G1)

reference data structure:

struct IssuerSecretKey{
    x BigNum
}

struct IssuerPublicKey{
    AttributeName []string
    HAttr []G1Point // h1, h2, h3 ... hL a G1 Point array corresponding to attributes array. 
                    // One attribute, One random G1 Point.
    HRand G1Point   // h0
    HSk G1Point     // h_sk ??? - a random G1 point to encode user's gsk

    w G2Point       // point of G2, issuer's public key ?
    _g1 G1Point     // point of G1
    _g2 G1Point     // point of G1
    C BigNum        // mod p first
    S BigNum        // mod p first, response to verifier
}

After issuer's setup, it makes ipk published, so public parameters has following addition content:

• ipk : Issuer's public key
  • w
  • _g1
  • _g2
  • π = (C, S)
    • C
    • S
  • AttributeName
  • HAttr
  • HRand
  • HSk

Join phase has 3 steps. So it is an interactive phase. This step is totally same as Issuance Protocol.

1. Issuer --------nonce(BigNum)-------> User
2. Issuer <-------CredRequest---------- User
3. Issuer --------Credential----------> User

Issuer

Issuer generates a nonce, which is a random big number with τ bits and sends it to user.

• n : nonce, n = rand{BigNum(τ)}

User

With nonce number n, user generates its key pair, same as CredRequest.

• gsk : gsk = rand{Zp}, secret key
• Q : Q = h_sk^gsk, public key
• π <--$-- SPK{gsk: Q = h_sk^gsk} : π = (C, S)
  • r : r = rand{Zp}
  • t1 : t1 = h_sk^r , to hide gsk
  • C : C = H(t1 || h_sk || Q || n)
  • S : S = (r + C * gsk) % p
• attrs = (a1,...,aL) : []BigNum, random from Zp, corresponding to user's attributes. User sends (Q, π) to Issuer.

Issuer

With (Q, π) from user, Issuer verify π <--$-- SPK{gsk: Q = h_sk^gsk} and generates credential for user. Issuer needs an array input attrs (TBD).

• attrs = (a1,...,aL) : @input, from user
• b : b = g1 · h0^s · Q · MulAll(hi^ai)
• BBS+ signature
  • e : random from Zp
  • s : random from Zp
  • A : A = ( g1 · h0^s · Q · MulAll(hi^ai) )^( 1/(e+x) ) = b^( 1/(e+x) )

reference data structure:

type CredRequest  struct {
   Nym             G1Point  //commitment to user's master secret, gsk
   IssuerNonce     BigNum   //nonce 
   ProofC          BigNum   //challenge in Sigma-protocol
   ProofS          BigNum   //response in Sigma-protocol
}

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

Signer's information:

• gsk
• Q
• attrs = (a1,...,aL)
• BBS+ signature
  • A
  • e
  • s
• b
• extra input
  • m : message to sign
  • (D, I) : attribute predicate, describe what attributes will be disclosed, if D[j]==1, I[j]=attrs[j]=aj, else I[j]=null
  • bsn : basename, a string to make signature different everytime

Start to sign:

• nym : nym = H1(bsn)^gsk

• r1 : random from Zp*

• A' : A' = A^r1

• r3 : r3 = 1/r1

• _A : _A = A'^(−e) · b^r1 = A'^x

• r2 : random from Zp

• d : d = b^r1 · h0^(-r2)

• s' : s' = s - r2·r3

• π <--$-- SPK{(gsk, {ai}_fasle, e, r2, r3, s'):

  {

  _A/d = A'^(-e) · h0^r2

  &&

  g1 · MulAll(hi^ai_true) = d^r3 · h0^(-s') · h_sk^(-gsk) · MulAll(hi^(-ai_false))

  &&

  nym = H1(bsn)^gsk

  }

• 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 = h_sk^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.