Skip to content

Instantly share code, notes, and snippets.

@Doresimon
Forked from kunxian-xia/anon_cred.md
Created July 5, 2018 08:20
Show Gist options
  • Save Doresimon/444fad23cd944d2b3e289f3c18bb608e to your computer and use it in GitHub Desktop.
Save Doresimon/444fad23cd944d2b3e289f3c18bb608e to your computer and use it in GitHub Desktop.

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}

  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

Issuance protocol

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.

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:

  1. Issuer Setup
  2. User Join
  3. User(Prover) Sign
  4. 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.

  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
}

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

Anonymous Credential Interface Instruction

Process

# Setup
Issuer --------IssuerPublicKey-----> Everyone

# Issurance
Issuer --------nonce(BigNum)-------> User
Issuer <-------CredRequest---------- User
Issuer --------Credential----------> User

# Proof
Prover <-------predicate, nonce----- Verifier
Prover --------proof, predicate----> Verifier
Prover <-------result--------------- Verifier

Dependent Library

  1. Bignum
  2. Elliptic
  3. Pairing
  4. Rand
  5. Hash
  6. Protobuf / Json

Elliptic

Use BN256 as Pairing Based Curve

// G1 Point
class G1Point {
    BigNum X;
    BigNum Y;
}
// G2 Point
class G2Point {
    BigNum Xa;
    BigNum Xb;
    BigNum Ya;
    BigNum Yb;
}

Issuer's Key Pair

class IssuerPublicKey {
    string AttributeNames[];

    G1Point HSk;
    G1Point HRand;
    G1Point HAttrs[];

    G2Point W;

    G1Point _g1;
    G1Point _g2;

    BigNum ProofC;
    BigNum ProofS;

}
class IssuerSecretKey { // for IssuerSecretKey, class is not a must, BigNum is ok.
    BigNum isk;
}
class IssuerKey {
    IssuerSecretKey Isk;
    IssuerPublicKey Ipk;
}

Credential Request

class CredRequest {
    G1Point Nym;
    BigNum IssuerNonce;
    BigNum ProofC;
    BigNum ProofS;
}

User's Credential

class Credential {
    G1Point A;
    G1Point B;
    BigNum E;
    BigNum S;
    BigNum Attrs[];
}

User's Signature

class Signature {
    G1Point APrime
    G1Point ABar  
    G1Point BPrime

    BigNum ProofC

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

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

Main Function

IssuerKey IssuerSetup(string AttributeName[]) // Issuer generates key pair

bool CheckIssuerKey(IssuerPublicKey ipk) // check correctness of Issuer's public key, Zero Knowledge Verification
CredRequest GenerateCredRequest(BigNum usk, IssuerNonce nonce, IssuerPublicKey ipk) // User generate credential request with nonce from Issuer
Credential GenerateCredential(IssuerKey key, CredRequest cr, BigNum Attrs[]) // Issuer generates Credential for user with credential request
Signature Sign(Credential c, BigNum usk, BigNum bsn, G1Point nym, bool Disclosure[], string message, IssuerPublicKey ipk) // User signs a message with its Credential
bool Verify(bool Disclosure[], BigNum Attrs[], Signature sig, string message, IssuerPublicKey ipk) // Another user verifies a signature.

Utility Function

string/char* Marshal(any*); // Marshal a class(IssuerPublicKey, CredRequest, Credential...) for communication and transfer.

any* UnMarshal(string/char*); // Unmarshal data.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment