Anonymous Credential

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). The user who is in possession of that credential can selectively disclose some parts to some verifier.

Background

BBS signature

Setup: generate a pairing-friendly curve G, and target group Gt, pairing func e: G x G -> Gt.
KeyGen: sk = (x), pk = (g^x).
Sign(m): sig = g^{1/(x+mprime)}, where mprime = H(m).
Verify(m, sig): check if e(pk * g^{H(m)}, g^sig) == e(g, g).

BBS+ signature

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

Example of SPK protocol

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}

commitment(prover):
```
r = rand{Zp}

t1 = g2^r

t2 = _g1^r
```

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

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

Issuance protocol

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

The issuer sends a random nonce to the user.
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
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
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.

The DAA Protocol(Direct anonymous attestation) with Extensions Πdaa+

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:

Issuer Setup
User Join
User(Prover) Sign
User(Verifier) Verify

Public Parameter:

τ : security parameter
G1 G2 GT : a bilinear group, eg: bn256
p : prime order of bilinear group
g1 h0 h1 ... hL : G1's generators
g2 : G2's generators
e : bilinear map
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

<1> Setup phase

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

<2> Issurance

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

Issuer --------nonce(BigNum)-------> User
Issuer <-------CredRequest---------- User
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
}

<3> Presentation

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   // ???
}

<4> Verify

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.

References

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

Doresimon/anon_cred.md

Anonymous Credential

Background

BBS signature

BBS+ signature

Example of SPK protocol

Issuance protocol

The DAA Protocol(Direct anonymous attestation) with Extensions Πdaa+

<1> Setup phase

<2> Issurance

<3> Presentation

<4> Verify

References

Anonymous Credential Interface Instruction

Process

Dependent Library

Elliptic

Issuer's Key Pair

Credential Request

User's Credential

User's Signature

Main Function

Utility Function