Ontology Developer Center
English
Search
⌃K
Comment on page

Anonymous Credentials

A zero knowledge proof signature algorithm
The anonymous credential scheme is a part of the Ontology Crypto library that provides several cryptography related utilities for the Ontology network. The main features provided by the crypto library basically revolve around digital signature. It provides general APIs for processing digital signatures and keys.

Abstract

There are three parties involved in an anonymous credential scheme, namely the issuer, the user (prover), and the verifier.
The issuer provides a certificate to the user. This certificate contains a list of the user's attributes and the issuer's signature (using BBS+signature). This protocol is formally called credential issuance protocol. The user who is in possession of the credentials can selectively disclose some parts to a verifier. This protocol is formally called credential presentation protocol.

Background

BBS + Signature

Setup: Groups
G1,G2G_1, G_2
 and
Gt .G_t\ .
 Pairing function
e:G1∗G2→Gt ,e: G_1*G_2 \rightarrow G_t \ ,
 where
G1G_1
 and
G2G_2
 are both of order
pp
. Common parameters:
  • ​
    g1g_1
     is the generator of
    G1G_1
  • ​
    g2g_2
     is the generator of
    G2G_2
  • ​
    Hrand ,h1,... ,hLH_{rand} \ , h_1, ... \ , h_L
     are elements from
    G1G_1
KeyGen: A sample
xx
 from uniform distribution on
ZpZ_p
, output
sk=x , pk=g2xs_k = x \ ,\ p_k = {g_2}^x
Sign
(sk,m1,... ,mL)(s_k, m_1, ... \ , m_L)
: Two random numbers
EE
 and
ss
are selected from
ZpZ_p
. First
B=g1∗HRands∗(h1m1∗...∗hLmL)B = g_1 * {H_{Rand}}^s * ({h_1}^{m_1} * ... * {h_L}^{m_L})
 is calculated, and then
A=B1/(E+x)A = B^{1/(E+x)}
 is computed. The signature is
(A,B,E,s)(A, B, E, s)
Verify
(pk,m1,... ,mL,sig)(p_k, m_1, ...\ ,m_L, sig)
: Decode
sigsig
 as
(A,B,E,s)(A, B, E, s)
 , and check if
e(A,g2E∗pk)==e(B,g2)e(A, {g_2}^E * p_k) == e(B, g_2)
 and whether
B==g1∗HRands∗(h1m1∗...∗hLmL)B == g_1 * {H_{Rand}}^s * ({h_1}^{m_1} * ... * {h_L}^{m_L})

Non-Interactive Proof of Knowledge (PoK) protocol

In this subsection, we will look at an example of the non-interactive proof of knowledge protocol which proves that the public key is generated as specified in the BBS + signature scheme. That is,
π=PoK{x:w=g2x && _g2=_g1x}\pi = PoK \{ x : w = {g_2}^x \ \&\& \ \_g_2 = \_{g_1}^x\}
. This means the prover proves the knowledge of
xx
 such that
g2x=w{g_2}^x = w
 and
_g2=_g1x\_g_2 = \_{g_1}^x
. It is assumed that
w,g2,_g1,_g2w, g_2, \_g_1, \_g_2
 are all public.
The protocol that we provide is a standard sigma protocol. It involves three steps, which are commit, challenge, and response. Sigma protocol is an interactive protocol and can be modified to be a non-interactive zero knowledge proof by using the well-known Fiat-Shamir heuristic. The proof
π={C,S}.\pi = \{ 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) mod 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)
​
// use C to compare with _C, which was calculated just now
if C == _C {
return true
} else {
return false
}

Setup of the Issuer's key pair

Given an array of the attribute names AttributeNames, the issuer's key pair is generated in the following manner:
  1. 1.
    Select a random element
    xx
     from
    ZpZ_p
    , and compute
    w=g2xw = {g_2}^x
    ​
  2. 2.
    Select a random element
    _g1\_g_1
    from
    G1G_1
    , and compute
    _g2=_g1x\_g_2 = \_{g_1}^x
    ​
  3. 3.
    Generate non-interactive proof of knowledge
    π=PoK{x:w=g2x && _g1x}=(C,S)\pi = PoK\{ x: w = {g_2}^x \ \&\& \ {\_g_1}^x \} = (C, S)
     Here,
  • r : A random element
    rr
     from
    ZpZ_p
  • t1 : Computed as
    t1=g2rt_1 = {g_2}^r
  • t2 : Computed as
    t2=_g1rt_2 = \_{g_1}^r
  • C :
    C=H(t1∣∣t2∣∣g2∣∣_g1∣∣w∣∣_g2)C = H(t_1 || t_2 || g_2 || \_g_1||w||\_g_2)
  • s :
    S=(r+C∗x) mod pS = (r + C *x) \bmod p
4. Select an array of elements from
G1G_1
 from AttributeNames. Next, calculate HAttrs[i] = random(G1) for each attribute in AttributeNames
5. Select two random elements HRand And HSk from
G1G_1
 6. The issuer's public key is set to ipk = (w, _g1, _g2, π, HAttrs, AttributeNames, HRand, HSk), and the private key is set to isk = x 7. Return isk and ipk
The following are the reference data structures for the 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
}

Issuance Protocol

Issuance protocol is an interactive protocol that consists of the following steps:
  1. 1.
    The issuer sends a random nonce to the user
  2. 2.
    The user creates a credential request using the public key, the secret, and the nonce. This request consists of a commitment to the user secret (can be seen as a public key), and a zero-knowledge proof of the knowledge of the user secret key. The user sends this credential request to the issuer
  3. 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 along with the attribute values and then sends the credential back to the user
  4. 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
The following diagram represents the interaction between the user and the issuer:
  • The credential request CredRequest contains a commitment
    NymN_{ym}
     to user's secret key which is of the form
    HSksk{H_{Sk}}^{sk}
     and a zk-PoK of the
    NymN_{ym}
  • Credential contains the BBS+signature on the attributes and the Nym

Generating credential request

The user generates the credential request using the attribute values and the nonce as input. The process is as follows:
  1. 1.
    Select a random element sk from
    ZpZ_p
     as the user's master secret key
  2. 2.
    Calculate
    Nym=HSkskN_{ym} = {H_{Sk}}^{sk}
     , which represents the commitment to the user's master secret
  3. 3.
    Generate the zero knowledge proof
    π=PoK{sk:Nym=HSksk}=(C,S)\pi = PoK \{ sk : N_{ym} = {H_{Sk}}^{sk} \} = (C, S)
     in the following manner-
  • Select a random element
    sksk
     from
    ZpZ_p
     which acts as the user's master secret
  • Calculate
    t1=HSkrt_1 = {H_{Sk}}^r
  • Compute the challenge
    C=H(t1∣∣HSk∣∣Nym∣∣nonce)C = H(t_1 || H_{Sk}||N_{ym}||nonce)
  • Compute the response
    S=(r+C∗sk) mod pS = (r+C*sk) \bmod p
The data structure of the credential request is of the following manner:
type CredRequest struct {
Nym G1Point //commitment to user's master secret
IssuerNonce BigNum //nonce
Attrs []BigNum //user's attributes
​
//PoK that Nym is constructed as in the issuance protocol
// i.e. PoK{(sk): HSk^sk = Nym }
C BigNum //challenge in Sigma-protocol
S BigNum //response in Sigma-protocol
}

Issuing Credential

After receiving the credential request from the user, the issuer verifies
π=(C,S)\pi = (C, S)
 and generates credentials for the user. The credential is generated using the issuer's private key
iski_{sk}
 as follows:
  1. 1.
    Select two random elements
    e,se, s
     from
    ZpZ_p
  2. 2.
    Calculate B = g1 · HRand^s · Nym · MulAll(HAttrs[i]^(Attrs[i]))
  3. 3.
    Compute A = B^(1/(e+x))
  4. 4.
    Return the credential
    (A,B,e,s,Attrs)(A, B, e, s, Attrs)
The data structure of a credential looks something like:
type Credential struct {
A G1Point
B G1Point
e BigNum
s BigNum
Attrs []BigNum
}

Presentation Protocol

In the presentation protocol, the prover tries to convince the verifier that they are aware of some secret input, such that some hypothetical predicate is true. A typical example of a predicate is that the prover is in possession of an anonymous credential, and they can selectively disclose certain attributes while hiding the other attributes.
The information that is available to the user is:
  • User's secret key
    sksk
     and its commitment
    NymN_{ym}
  • Attribute values
    attrs=(a1,... ,aL)attrs = (a_1, ...\ , a_L)
  • BBS +signature (A, B, e, s)
  • Extra input
    • (D, I) : Attribute predicate, describes what attributes will be disclosed. If D[j] == 1, I[j] = attrs[j] = aj, else I[j] = null

Proving Algorithm

The selective disclosure proof can be generated in the following manner:
  1. 1.
    Randomize A : Select a random element
    r1r_1
     from
    Zp∗{Z_p}^*
    , and compute
    A′=Ar1A' = A^{r_1}
  2. 2.
    Calculate
    _A=A′(−e) ⋅Br1, r3=1/r1\_A = A'^{(−e)} \ · B^{r_1},\ r_3 = 1/r_1
  3. 3.
    Select an element
    r2r_2
     from
    ZpZ_p
  4. 4.
    Calculate
    B′=Br1⋅HRand−r2B' = B^{r_1} · {H_{Rand}}^{-r_2}
     ,
    s′=s−r2⋅r3s' = s - r_2 · r_3
  5. 5.
    Generate zero knowledge proof
    π=PoK{(sk,ai_hidden,e,r2,r3,s′)}\pi = PoK\{ (s_k, {a_i}\_{hidden}, e, r_2, r_3, s') \}
     such that-
  • _A/B' = A'^(-e) · HRand^r2
  • g1 · MulAll(hi^ai_reveal) = (B')^r3 · HRand^(-s') · HSk^(-sk) ·MulAll(hi^(-ai_hidden)), where hi stands for HAttrs[i]
The proof can be generated as follows:
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_sk : random from Zp
E : E = HSk^r_sk
t1 : t1 = A'^r_e · HRand^r_r2
t2 : t2 = (B')^r_r3 · HRand^r_s' · E^(-1) · MulAll(hi^r_ai)
c' : c' = H(A', _A, B', nym, t1, t2, g1, HRand, h1, ... , hL, w)
nonce : nonce, with τ bit length, randomly generated again
c : c = H(nonce, c', (D, I))
s_sk : s_sk = r_sk + c · sk
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_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce}, i belong to _D
The output is
(A′,_A,d,nym,π)(A', \_A, d, n_{ym}, \pi)
 where
π={c,ssk,sai,se,sr2,sr3,ss′,nonce}\pi = \{c, s_{sk}, s_{ai}, s_e, s_{r_2}, s_{r_3}, {s_s}', nonce\}
Here is the reference data structure for the zero knowledge proof:
type Proof 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 // nonce used to avoid replay attack
Nym G1Point
}

Verification

The verifier has the following input information available:
  • (A′,_A,B′,nym,π)(A', \_A, B', n_{ym}, \pi)
     : from the signer
  • {c,ssk,sai,se,sr2,sr3,ss′,nonce}\{c, s_{sk}, {s_{a_i}}, s_e, s_{r_2}, s_{r_3}, {s_s}', nonce\}
     : obtained by parsing
    π\pi
The verification algorithm proceeds as in the following manner:
  1. 1.
    Check if A' != 1 in G1; if false, return false.
  2. 2.
    Check if e(A', w) == e(_A, g2); if false, return false. This is
    zk−PoKz_k-PoK
     for A.
  3. 3.
    Parse
    π\pi
     : {c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce} <- π; if failed, return false.
  4. 4.
    ~
    t1t_1
     : ~t1 = A'^s_e · HRand^s_r2 · (_A/B')^(-c) . This is
    zk−PoKz_k-PoK
     for e, r2.
  5. 5.
    ~
    t2t_2
     : (B')^s_r3 · HRand^s_s' · HSk^(-s_sk) · 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
    Zk−PoKZ_k - PoK
     for r3, s', gsk, ai of _D.
  6. 6.
    c′c'
     : c' = H(nonce, H(A', _A, B', nym, ~t1, ~t2, g1, HRand, h1, ... , hL, w), (D, I))
  7. 7.
    Check if c == c' : if false, return false. Otherwise return true.
​
Last modified 3yr ago