NashMiao/anon_cred.md

## anon_cred.md

      
    Raw
  

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

  
## interface.md

      
    Raw
  

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


Bignum
Elliptic
Pairing
Rand
Hash
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.