Skip to content

Instantly share code, notes, and snippets.

@kunxian-xia

kunxian-xia/anon_cred.md

Last active July 23, 2018 08:54
Show Gist options
  • Save kunxian-xia/a926ec4969c7bcc0aa5b684b189bca25 to your computer and use it in GitHub Desktop.
Save kunxian-xia/a926ec4969c7bcc0aa5b684b189bca25 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. kunxian-xia revised this gist Jul 23, 2018. 1 changed file with 41 additions and 67 deletions.
    108 changes: 41 additions & 67 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -76,10 +76,9 @@ The protocol we give is a standard sigma protocol. It consists three steps, name
    Given an array of attribute's names `AttributeNames`, the issuer's key pair is generated as follows:
    1. Sample a random element `x` from Zp.
    2. Compute `w = g2^x`.
    3. Sample a random element `_g1` from G1. And compute `_g2 = _g1^x`.
    4. Generate non-interactive proof of knowledge `π = PoK{x: w = g2^x && _g2 = _g1^x} = (C, S)` according
    1. Sample a random element `x` from Zp, and compute `w = g2^x`.
    2. Sample a random element `_g1` from G1. And compute `_g2 = _g1^x`.
    3. Generate non-interactive proof of knowledge `π = PoK{x: w = g2^x && _g2 = _g1^x} = (C, S)` according
    to [section 1.2](./anon_cred.md#12-non-interactive-proof-of-knowledge-pok-protocol) which we reproduce here.
    - `r` : sample a random element r from Zp
    @@ -88,10 +87,10 @@ Given an array of attribute's names `AttributeNames`, the issuer's key pair is g
    - `C` : C = H(t1 || t2 || g2 || _g1 || w || _g2)
    - `S` : S = (r + C * x) mod p
    5. Sample an array of elements from G1 for `AttributeNames`. For each attribute in `AttributeNames`, compute `HAttrs[i] = random(G1)`
    6. Sample two random elements from G1: `HRand` and `HSk`.
    7. Set issuer's public key `ipk = (w, _g1, _g2, π, HAttrs, AttributeNames, HRand, HSk)`, and private key `isk = x`.
    8. Return **ipk** and **isk**.
    4. Sample an array of elements from G1 for `AttributeNames`. For each attribute in `AttributeNames`, compute `HAttrs[i] = random(G1)`
    5. Sample two random elements from G1: `HRand` and `HSk`.
    6. Set issuer's public key `ipk = (w, _g1, _g2, π, HAttrs, AttributeNames, HRand, HSk)`, and private key `isk = x`.
    7. Return **ipk** and **isk**.

    The following snippets in golang gives the reference data structures for issuer's key pair.
    @@ -161,7 +160,7 @@ In short, this can be summarized in the following diagram:
    --- Credential --->
    - CredRequest contains a commitment `Nym` to user's master secret which is of the form `HSk^(sk) ` and a zk-PoK of Nym.
    - CredRequest contains a commitment `Nym` to user's secret key which is of the form `HSk^(sk) ` and a zk-PoK of Nym.

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

    @@ -187,29 +186,28 @@ The following snippets in golang gives the reference data structures for credent
    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): g1^sk = Nym }
    // i.e. PoK{(sk): HSk^sk = Nym }
    C BigNum //challenge in Sigma-protocol
    S BigNum //response in Sigma-protocol
    Attrs []BigNum //user's attributes
    }
    ```

    ### 3.2 Issue credential
    After receiving credential request from user, issuer verify `π = (C, S)` and generates credential for user.
    Issuer needs an array input `attrs` (TBD).
    The credential is generated using issuer's private key `isk` as follows:
    1. Sample two random elements `e, s` from Zp.
    2. Compute `b = g1 · HRand^s · Nym · MulAll(HAttrs[i]^(Attrs[i]))`
    3. Compute `A = b^(1/(e+x))`.
    4. Return credential `(A, b, e, s, Attrs)`
    2. Compute `B = g1 · HRand^s · Nym · MulAll(HAttrs[i]^(Attrs[i]))`
    3. Compute `A = B^(1/(e+x))`.
    4. Return credential `(A, B, e, s, Attrs)`

    The following snippets in golang gives the reference data structures for credential.
    ```go
    type Credential struct {
    A G1Point
    b G1Point
    B G1Point
    e BigNum
    s BigNum
    Attrs []BigNum
    @@ -264,42 +262,42 @@ Before we give the proving algorithm, we list the information that the prover ha

    - User's secret key `sk` and its commitment `Nym`.
    - Attribute values `attrs = (a1,...,aL)`
    - BBS+ signature `(A, b, e, s)`
    - BBS+ signature `(A, B, e, s)`
    - extra input
    - `(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
    - `n` - nonce, with τ bit length -->

    ### 4.1. Proving algorithm
    Start to sign:
    The selectively disclosure proof can be generated as follows:

    1. Randomize A: sample a random element `r1` from Zp*, and compute `A' = A^r1`.
    2. Compute `_A = A'^(−e) · b^r1, r3 = 1/r1`.
    2. Compute `_A = A'^(−e) · B^r1, r3 = 1/r1`.
    3. Sample an element `r2` from Zp.
    4. Compute `b' = b^r1 · HRand^(-r2)`, `s' = s - r2·r3`.
    4. Compute `B' = B^r1 · HRand^(-r2)`, `s' = s - r2·r3`.
    5. Generate zero knowledge proof `π = PoK{ (sk, {ai}_hidden, e, r2, r3, s') }` such that
    - `_A/b' = A'^(-e) · HRand^r2 ` and
    - `g1 · MulAll(hi^ai_reveal) = d^r3 · HRand^(-s') · HSk^(-sk) · MulAll(hi^(-ai_hidden))`.
    - `_A/B' = A'^(-e) · HRand^r2 ` and
    - `g1 · MulAll(hi^ai_reveal) = (B')^r3 · HRand^(-s') · HSk^(-sk) · MulAll(hi^(-ai_hidden))`.

    This 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_gsk` : random from Zp
    - `r_sk` : random from Zp
    - `E` : E = HSk^r_sk
    - `t1` : t1 = A'^r_e · HRand^r_r2
    - `t2` : t2 = d^r_r3 · HRand^r_s' · E^(-1) · MulAll(hi^r_ai)
    - `c'` : c' = H(A', _A, d, nym, t1, t2, g1, HRand, h1, ... , hL, w)
    - `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(n, c', (D, I))
    - `s_sk` : s_sk = r_sk + c · sk
    - `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_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

    @@ -308,13 +306,7 @@ Output is `(A', _A, d, nym, π)`, where π = {c, s_sk, {s_ai}, s_e, s_r2, s_r3,
    The following snippets in golang gives the reference data structures for zero-knowledge proof.

    ```go
    // 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 {
    type Proof struct {
    APrime G1Point // randomized credential signature values
    ABar G1Point // randomized credential signature values
    BPrime G1Point // randomized credential signature values
    @@ -329,50 +321,32 @@ type Signature struct {
    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)
    Nonce BigNum // nonce used to avoid replay attack
    Nym G1Point
    }
    ```

    ### 4.2 Verification

    Verifier has the following information as input:

    - `(A', _A, b', nym, π)` : from signer
    - `(A', _A, B', nym, π)` : from signer
    - `{c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce}` : parse π

    The verification algorithm proceeds as follows:
    1. Check if `A' == 1` in G1; if false: return `false`.
    2. check if `e(A', w) == e(_A, g2)`; if false: return `false`. _This is ZKPoK for __A__._
    3. Parse __π__ : `{c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce} <- π`; if failed, return `false`.
    4. `~t1` : ~t1 = A'^s_e · h0^s_r2 · (_A/d)^(-c) . _This is ZKPoK for __e__, __r2__._
    5. `~t2` : (b')^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'__, __gsk__, __ai__ of _D.
    - `c'` : c' = H(nonce, H(A', _A, d, nym, ~t1, ~t2, g1, HRand, h1, ... , hL, w), (D, I))
    - Check if `c == c'` : if false: return `false`. Otherwise return `true`.
    1. Check if `A' == 1` in G1; if false, return `false`.
    2. check if `e(A', w) == e(_A, g2)`; if false, return `false`. _This is zk-PoK for __A__._
    3. Parse __π__ : `{c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce} <- π`; if failed, return `false`.
    4. `~t1` : ~t1 = A'^s_e · HRand^s_r2 · (_A/B')^(-c) . _This is zk-PoK for __e__, __r2__._
    5. `~t2` : (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 ZKPoK for __r3__, __s'__, __gsk__, __ai__ of _D.
    6. `c'` : c' = H(nonce, H(A', _A, B', nym, ~t1, ~t2, g1, HRand, h1, ... , hL, w), (D, I))
    7. Check if `c == c'` : if false: return `false`. Otherwise return `true`.


    <!-- In __Proof Protocol__, the ZKPoK of User's BBS+ signature (A,e,s) is
    `π <--$-- SPK{(gsk, {ai}_fasle, e, r2, r3, s'):`
    {
    `_A/d = A'^(-e) * h0^r2` &&
    `g1 * MulAll(h_{i+1}^ai_true) = d^r3 * h0^(-s') * h_sk^(-gsk) * MulAll(h_{i+1}^(-ai_false))` &&
    `nym = H1(bsn)^gsk `
    }
    {ai} is User's attribute set. "_fasle" means the attributs that User wants to hide, "_true" means the attributes User wants to disclose.
    π = {C, S_gsk, S_e, S_r2, S_r3, S_s', S_Nym, S_attrs} -->

    ## References
    ## 5. 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
  2. kunxian-xia revised this gist Jul 23, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -80,7 +80,7 @@ Given an array of attribute's names `AttributeNames`, the issuer's key pair is g
    2. Compute `w = g2^x`.
    3. Sample a random element `_g1` from G1. And compute `_g2 = _g1^x`.
    4. Generate non-interactive proof of knowledge `π = PoK{x: w = g2^x && _g2 = _g1^x} = (C, S)` according
    to [section 1.2](12-non-interactive-proof-of-knowledge-pok-protocol) which we reproduce here.
    to [section 1.2](./anon_cred.md#12-non-interactive-proof-of-knowledge-pok-protocol) which we reproduce here.
    - `r` : sample a random element r from Zp
    - `t1` : compute t1 = g2^r.
  3. kunxian-xia revised this gist Jul 23, 2018. 1 changed file with 27 additions and 20 deletions.
    47 changes: 27 additions & 20 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,7 @@ In an anonymous credential scheme there are **three** participants: issuer, user
    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**.
    **credential presentation protocol**.

    ## 1. Background
    <!--
    @@ -15,30 +15,32 @@ The user who is in possession of that credential can selectively disclose some p
    - Verify(m, sig): check if e(pk * g^{H(m)}, g^sig) == e(g, g). -->

    ### 1.1 BBS+ signature
    - *Setup*: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.
    - *Setup*: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt. G1 and G2 are both of order p.

    common params:
    - g0, g1, (g2, ..., g_{L+1}) are elements from G1.
    - g1 is a generator of G1.

    - h0 is a generator of G2.
    - g2 is a generator of G2.

    - HRand, h1, ..., hL are elements from G1.

    - *KeyGen*: sample x from uniform dist on Zp, output sk = x, pk = h0^x.
    - *KeyGen*: sample x from uniform distribution on Zp, output sk = x, pk = g2^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).
    `B = g1 * HRand^s * (h1^m1 * ... * hL^mL)`, then compute `A = B^{1/(E+x)}`.
    The signature is (A, B, E, s).

    - *Verify(pk, m1, ..., mL, sig)*:
    decode sig as (A, E, s), and check if `e(A, h0^E * pk) == e(B, h0)`.
    decode `sig` as (A, B, E, s), and check if `e(A, g2^E * pk) == e(B, h0)` and if `B == g1 * HRand^s * (h1^m1 * ... * hL^mL)`.

    ### 1.2 Statistical Non-Interactive Proof of Knowledge (SPoK) protocol
    In this subsection, we give an example of non-interactive statistical proof of knowledge protocol which proves that the public key is generated as specfied in the BBS+ signature scheme. That is, `π = SPoK{x: w = g2^x && _g2 = _g1^x}` which can be translated as the prover proves knowledge of `x` such that `g2^x = w` and `_g2 = _g1^x`. And `w, g2, _g1, _g2` are assumed to be public.
    ### 1.2 Non-Interactive Proof of Knowledge (PoK) protocol
    In this subsection, we give an example of 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 = g2^x && _g2 = _g1^x}` which can be translated as the prover proves knowledge of `x` such that `g2^x = w` and `_g2 = _g1^x`. And `w, g2, _g1, _g2` are assumed to be public.

    The protocol we give is a standard sigma protocol. It consists three steps, namely, **commit-challenge-response**. And the proof π = {C, S}
    The protocol we give is a standard sigma protocol. It consists three steps, namely, **commit, challenge, response**. Sigma protocol is a interactive protocol and it can be modified to be a non-interactive zero knowledge proof by using the well-known **Fiat-Shamir heuristic**. And the proof π = {C, S}.

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

    t1 = g2^r

    @@ -48,21 +50,26 @@ The protocol we give is a standard sigma protocol. It consists three steps, name
    ```go
    P = t1 || t2 || g2 || _g1 || w || _g2 //join them together in binary format
    C = hash_to_int(P) //C is challenge
    C = hash_to_int(P) //C is challenge
    S = (r + C * x) % p //response to verifier
    S = (r + C * x) mod p //response to verifier
    ```
    3. verify(verifier):
    ```go
    _t1 = g2^S * w^((-c))
    _t1 = g2^S * w^(-c)
    _t2 = _g1^S * _g2^((-c))
    _t2 = _g1^S * _g2^(-c)
    _P = _t1 || _t2 || g2 || _g1 || w || _g2
    _C = hash_to_int(_P) //do the same thing like prover, everything is public
    _C = hash_to_int(_P)
    check if C == _C // use C to compare with _C, which was calculated just now
    // use C to compare with _C, which was calculated just now
    if C == _C {
    return true
    } else {
    return false
    }
    ```

    ## 2. Setup of Issuer's key pair
    @@ -72,8 +79,8 @@ Given an array of attribute's names `AttributeNames`, the issuer's key pair is g
    1. Sample a random element `x` from Zp.
    2. Compute `w = g2^x`.
    3. Sample a random element `_g1` from G1. And compute `_g2 = _g1^x`.
    4. Generate non-interactive proof of knowledge `π = PoK{x: w = g2^x && _g2 = _g1^x} = {C, S}` according
    to [section 1.2](#1.2) which we reproduce here.
    4. Generate non-interactive proof of knowledge `π = PoK{x: w = g2^x && _g2 = _g1^x} = (C, S)` according
    to [section 1.2](12-non-interactive-proof-of-knowledge-pok-protocol) which we reproduce here.
    - `r` : sample a random element r from Zp
    - `t1` : compute t1 = g2^r.
  4. kunxian-xia revised this gist Jul 23, 2018. 1 changed file with 25 additions and 80 deletions.
    105 changes: 25 additions & 80 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -65,55 +65,6 @@ The protocol we give is a standard sigma protocol. It consists three steps, name
    check if C == _C // use C to compare with _C, which was calculated just now
    ```

    In the presentation protocol specified in section 3, the core part is to prove knowledge of BBS+ signature (A,e,s), namely,

    `π = SPoK{ (e, r2, r3, s', {mi}): _A/d = A'^(-e) * h0^r2 && g1 * MulAll(h_i^mi) = d^r3 * h0^(-s') }`
    <!--
    ```c
    // {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
    ```
    -->
    ## 2. Setup of Issuer's key pair
    Given an array of attribute's names `AttributeNames`, the issuer's key pair is generated as follows:
    @@ -319,38 +270,35 @@ Start to sign:
    1. Randomize A: sample a random element `r1` from Zp*, and compute `A' = A^r1`.
    2. Compute `_A = A'^(−e) · b^r1, r3 = 1/r1`.
    3. Sample an element `r2` from Zp.
    4. Compute `d = b^r1 · HRand^(-r2)`, `s' = s - r2·r3`.
    4. Compute `b' = b^r1 · HRand^(-r2)`, `s' = s - r2·r3`.
    5. Generate zero knowledge proof `π = PoK{ (sk, {ai}_hidden, e, r2, r3, s') }` such that
    - `_A/d = A'^(-e) · HRand^r2 ` and
    - `_A/b' = A'^(-e) · HRand^r2 ` and
    - `g1 · MulAll(hi^ai_reveal) = d^r3 · HRand^(-s') · HSk^(-sk) · MulAll(hi^(-ai_hidden))`.

    This proof can be generated as illustrated in [section 1.2]() which we reproduce here.
    This 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_gsk` : random from Zp
    - `E` : E = HSk^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
    - `E` : E = HSk^r_sk
    - `t1` : t1 = A'^r_e · HRand^r_r2
    - `t2` : t2 = d^r_r3 · HRand^r_s' · E^(-1) · MulAll(hi^r_ai)
    - `c'` : c' = H(A', _A, d, nym, t1, t2, g1, HRand, h1, ... , hL, w)
    - `nonce` : nonce, with τ bit length, randomly generated again
    - `c` : c = H(n, 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_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}, i belong to _D
    - `(A', _A, d, nym, π)` : signature done.
    - `π` : {c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce}, i belong to _D

    Output is `(A', _A, d, nym, π)`, where π = {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}
    Output is `(A', _A, d, nym, π)`, where π = {c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce}

    Suggested data structure:
    The following snippets in golang gives the reference data structures for zero-knowledge proof.

    ```go
    // Signature specifies a signature object that consists of
    @@ -376,30 +324,27 @@ type Signature struct {

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

    ### 4.2 Verification

    Verifier's information:

    - `(A', _A, d, nym, π)` : from signer
    - `{c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s', n}` : parse π
    Verifier has the following information as input:

    Start to verify:
    - `(A', _A, b', nym, π)` : from signer
    - `{c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce}` : parse π

    - `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 verification algorithm proceeds as follows:
    1. Check if `A' == 1` in G1; if false: return `false`.
    2. check if `e(A', w) == e(_A, g2)`; if false: return `false`. _This is ZKPoK for __A__._
    3. Parse __π__ : `{c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce} <- π`; if failed, return `false`.
    4. `~t1` : ~t1 = A'^s_e · h0^s_r2 · (_A/d)^(-c) . _This is ZKPoK for __e__, __r2__._
    5. `~t2` : (b')^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.
    - This is ZKPoK for __r3__, __s'__, __gsk__, __ai__ of _D.
    - `c'` : c' = H(nonce, H(A', _A, d, nym, ~t1, ~t2, g1, HRand, h1, ... , hL, w), (D, I))
    - Check if `c == c'` : if false: return `false`. Otherwise return `true`.


    <!-- In __Proof Protocol__, the ZKPoK of User's BBS+ signature (A,e,s) is
  5. kunxian-xia revised this gist Jul 20, 2018. 1 changed file with 159 additions and 230 deletions.
    389 changes: 159 additions & 230 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -62,16 +62,15 @@ The protocol we give is a standard sigma protocol. It consists three steps, name
    _C = hash_to_int(_P) //do the same thing like prover, everything is public
    C ==? _C // use C to compare with _C, which was calculated just now
    check if C == _C // use C to compare with _C, which was calculated just now
    ```

    In the presentation protocol specified in section 3, the core part is to prove knowledge of BBS+ signature (A,e,s), namely,

    `π = SPoK{ (e, r2, r3, s', {mi}): _A/d = A'^(-e) * h0^r2 && g1 * MulAll(h_i^mi) = d^r3 * h0^(-s') }`
    where `_A, A', h0, `
    <!--
    ```c
    // {mi} is tuple of message, such like blocks.
    // {mi} is turple of message, such like blocks.
    r1 = rand(Zp)
    r2 = rand(Zp)
    @@ -114,17 +113,77 @@ C ?= C'
    // done
    ```
    -->
    ## 2. Setup of Issuer's key pair
    Given an array of attribute's names `AttributeNames`, the issuer's key pair is generated as follows:
    1. Sample a random element `x` from Zp.
    2. Compute `w = g2^x`.
    3. Sample a random element `_g1` from G1. And compute `_g2 = _g1^x`.
    4. Generate non-interactive proof of knowledge `π = PoK{x: w = g2^x && _g2 = _g1^x} = {C, S}` according
    to [section 1.2](#1.2) which we reproduce here.
    - `r` : sample a random element r from Zp
    - `t1` : compute t1 = g2^r.
    - `t2` : compute t2 = _g1^r.
    - `C` : C = H(t1 || t2 || g2 || _g1 || w || _g2)
    - `S` : S = (r + C * x) mod p
    5. Sample an array of elements from G1 for `AttributeNames`. For each attribute in `AttributeNames`, compute `HAttrs[i] = random(G1)`
    6. Sample two random elements from G1: `HRand` and `HSk`.
    7. Set issuer's public key `ipk = (w, _g1, _g2, π, HAttrs, AttributeNames, HRand, HSk)`, and private key `isk = x`.
    8. Return **ipk** and **isk**.

    The following snippets in golang gives the reference data structures for issuer's key pair.
    ## 2. Issuance protocol
    ```go
    type IssuerSecretKey struct {
    x BigNum
    }
    ```
    ```go
    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
    }
    ```
    <!--
    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`
    -->

    ## 3. 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.
    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.
    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
    The user sends the credential request to the issuer.

    3) The issuer verifies the credential request by verifying the zero-knowledge proof

    @@ -136,65 +195,70 @@ The issuance protocol is an interactive protocol which consists of the following

    In short, this can be summarized in the following diagram:

    Issuer -------------------- Prover
    Issuer ------------------------ Prover
    -- nonce(BigNum)-->
    -- nonce(BigNum) -->
    <-- CredRequest --
    <-- CredRequest ---
    --- Credential --->
    --- 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.
    - CredRequest contains a commitment `Nym` to user's master secret which is of the form `HSk^(sk) ` and a zk-PoK of Nym.

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

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

    ```go
    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
    }
    ```
    ### 3.1 Generate Credential Request

    <!--
    Issuer generates a nonce, which is a random big number with τ bits and sends it to user.
    - `n` : nonce, n = rand{BigNum(τ)}
    -->
    User will generate the credential request with attribute values and `nonce` as input. This is done as follows:
    1. Sample a random element `sk` from Zp as user's master secret.
    2. Compute `Nym = HSk^(sk)` as a commitment to user's master secret.
    3. Generate zero knowledge proof `π = PoK{sk: Nym = HSk^sk} = (C, S)` as illustrated in [section 1.2]() which we reproduce here.
    - Sample a random element `r` from Zp.
    - Compute `t1 = HSk^r`.
    - Compute challenge `C = H(t1 || HSk || Nym || nonce)`.
    - Compute response `S = (r + C * sk) mod p`.

    The following snippets in golang gives the reference data structures for credential request.
    ```go
    type CredRequest struct {
    Nym ECPoint //commitment to user's master secret
    type CredRequest struct {
    Nym G1Point //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
    // i.e. PoK{(sk): g1^sk = Nym }
    C BigNum //challenge in Sigma-protocol
    S BigNum //response in Sigma-protocol
    Attrs []BigNum //user's attributes
    }
    ```

    ### 3.2 Issue credential
    After receiving credential request from user, issuer verify `π = (C, S)` and generates credential for user.
    Issuer needs an array input `attrs` (TBD).
    The credential is generated using issuer's private key `isk` as follows:
    1. Sample two random elements `e, s` from Zp.
    2. Compute `b = g1 · HRand^s · Nym · MulAll(HAttrs[i]^(Attrs[i]))`
    3. Compute `A = b^(1/(e+x))`.
    4. Return credential `(A, b, e, s, Attrs)`

    The following snippets in golang gives the reference data structures for credential.
    ```go
    type Credential struct { // (A, e, s) is BBS+ signature
    A ECPoint
    B ECPoint
    e BigNum
    type Credential struct {
    A G1Point
    b G1Point
    e BigNum
    s BigNum
    Attrs [][]byte
    Attrnames []string
    Attrs []BigNum
    }
    ```
    ## Anonymous credential

    <!--
    __Notice:__ This protocol is based on DAA+ protocol from [CDL16], some steps have been changed
    in order to satisfy our demands.
    @@ -216,7 +280,7 @@ Steps:
    4. Sign Request
    5. Sign Proceed
    6. Verify
    7. Link -->
    7. Link
    Public Parameter:
    @@ -228,196 +292,61 @@ Public Parameter:
    - `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

    #### <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:
    - `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
    ```go
    struct IssuerSecretKey{
    x BigNum
    }
    ```
    ```go
    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> Join phase
    ## 4. Presentation protocol
    In the presentation protocol, the prover tries to convince the verifier that he knows some secret input such that some predicate is true. A typical example of predicate is that
    the prover is *in possession of an anonymous credential*, and he can **selectively disclose** some attributes while hiding the other attributes.

    <!-- see Issuance protocol -->
    Before we give the proving algorithm, we list the information that the prover has.

    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:
    ```go
    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
    }
    ```

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

    ## 3. Presentation protocol
    ### 3.1 proof generation

    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
    - User's secret key `sk` and its commitment `Nym`.
    - Attribute values `attrs = (a1,...,aL)`
    - BBS+ signature `(A, b, e, s)`
    - extra input
    - `(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
    <!-- - `n` - nonce, with τ bit length -->
    - `n` - nonce, with τ bit length -->

    ### 4.1. Proving algorithm
    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))`
    1. Randomize A: sample a random element `r1` from Zp*, and compute `A' = A^r1`.
    2. Compute `_A = A'^(−e) · b^r1, r3 = 1/r1`.
    3. Sample an element `r2` from Zp.
    4. Compute `d = b^r1 · HRand^(-r2)`, `s' = s - r2·r3`.
    5. Generate zero knowledge proof `π = PoK{ (sk, {ai}_hidden, e, r2, r3, s') }` such that
    - `_A/d = A'^(-e) · HRand^r2 ` and
    - `g1 · MulAll(hi^ai_reveal) = d^r3 · HRand^(-s') · HSk^(-sk) · MulAll(hi^(-ai_hidden))`.

    &&

    `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.
    This proof can be generated as illustrated in [section 1.2]() which we reproduce here.
    - `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 = HSk^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}

    @@ -451,7 +380,7 @@ type Signature struct {
    }
    ```

    ### 3.2 proof verification
    ### 4.2 Verification

    Verifier's information:

  6. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 7 additions and 131 deletions.
    138 changes: 7 additions & 131 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -67,9 +67,10 @@ The protocol we give is a standard sigma protocol. It consists three steps, name

    In the presentation protocol specified in section 3, the core part is to prove knowledge of BBS+ signature (A,e,s), namely,

    `π = SPoK{ (e, r2, r3, s'): _A/d = A'^(-e) * h0^r2 && g1 * MulAll(h_i^mi) = d^r3 * h0^(-s') }`
    `π = SPoK{ (e, r2, r3, s', {mi}): _A/d = A'^(-e) * h0^r2 && g1 * MulAll(h_i^mi) = d^r3 * h0^(-s') }`
    where `_A, A', h0, `
    ```c
    // {mi} is turple of message, such like blocks.
    // {mi} is tuple of message, such like blocks.
    r1 = rand(Zp)
    @@ -114,7 +115,7 @@ C ?= C'
    // done
    ```

    ## Issuance protocol
    ## 2. 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.

    @@ -192,131 +193,6 @@ type Credential struct { // (A, e, s) is BBS+ signature
    Attrnames []string
    }
    ```
    <!-- ### 2. Proof protocol

    - __Presentation.__

    A user signs a message or authenticates with her credentials by deriving a fresh and unlinkable presentation token from her credentials according to an access control policy, hereafter called __presentation policy__. A presentation policy specifies which attributes (or which predicates about certain attributes) from which type of credential a user should include in the presentation token. It also specifies the public key(s) of the credential issuing authority(ies), which the verifier trusts to correctly certify users' attributes. If the user consents to disclose the information required by the policy, the presentation token is sent for verification.
    - __Verification.__
    The token is verified whether it satisfies the presentation policy using the public key(s) of the credential issuing authority(ies) (CA).
    - __Construction__
    An __Identity Mixer signature__ is a signature of knowledge that __signs a message and proves: (in zero-knowledge)__
    - the knowledge of the user secret (and possibly attributes) signed inside a credential
    - that was issued by a certain issuer (referred to with the issuer public key)
    - The signature is verified using the message being signed and the public key of the issuer
    - Some of the attributes from the credential can be selectvely disclosed or different statements can be proven about
    - credential atrributes without diclosing them in the clear
    The proof protocol is a non-interactive protocol with just 2 steps
    1. Prover signs a message
    - __Detail__
    ```go
    // 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 *ECP // A' = A^{r1} ...... A is cred.A
    ABar *ECP // barA = A'^{-e} B^{r1} ...... e is cred.e, B is cred.B
    BPrime *ECP // B' = B^{r1} h_r^{-r2} ...... h_r is ipk.HRand
    ProofC []byte
    ProofSSk []byte
    ProofSE []byte
    ProofSR2 []byte
    ProofSR3 []byte
    ProofSSPrime []byte // s' = s - r2 * r3
    ProofSAttrs [][]byte
    Nonce []byte
    Nym *ECP
    ProofSRNym []byte
    RevocationEpochPk *ECP2
    RevocationPkSig []byte
    Epoch int64
    NonRevocationProof *NonRevocationProof
    }
    ```
    ```go
    // NymSignature specifies a signature object that signs a message
    // with respect to a pseudonym. It differs from the standard idemix.signature in the fact that
    // the standard signature object also proves that the pseudonym is based on a secret certified by
    // a CA (issuer), whereas NymSignature only proves that the the owner of the pseudonym
    // signed the message
    type NymSignature struct {
    ProofC []byte // proof_c is the Fiat-Shamir challenge of the ZKP
    ProofSSk []byte // proof_s_sk is the s-value proving knowledge of the user secret key
    ProofSRNym []byte // proof_s_r_nym is the s-value proving knowledge of the pseudonym secret
    Nonce []byte // nonce is a fresh nonce used for the signature
    }
    ```
    - standard idemix.signature:

    * `Sign()`

    sig, err = NewSignature(cred, sk, Nym, RandNym, key.Ipk, disclosure, msg, rhindex, cri, rng)

    @input cred: the crendential user has got in Issuance Process.
    @input sk: the secret key of user.
    @input Nym: a EC point, computed from RandNym
    // Nym = EcpFromProto(IPk.HSk).Mul2(sk, EcpFromProto(IPk.HRand), RandNym).
    @input RandNym: a random number of Z* .
    @input Ipk: the publick key of Issuer.
    @input disclosure: an array of 1/0, 1 means the attr[i] will be disclosed by user.
    @input msg: the message to sign.
    @input rhindex: ????.
    @input cri: a Credential Revocation Information for a certain time period
    @input rng: a random generator, just ignore.

    @return sig: signature

    * `Verify()`

    err = sig.Ver(disclosure, key.Ipk, msg, attrs, rhindex, &revocationKey.PublicKey, epoch)

    @this sig: the signature Verifier received from user.

    @input disclosure: same as sign(), from user.
    @input Ipk: same as sign(), from issuer.
    @input msg: same as sign(), from user.
    @input attrs: the collection of attributed's map, from setup stage.
    @input rhindex: ???.
    @input &revocationKey.PublicKey: a ecdsa key pair, used in CRI creation.
    @input epoch: time point, a number. used in CRI creation.
    - pseudonym signature:
    * `Sign()`
    nymsig, err = NewNymSignature(sk, Nym, RandNym, key.Ipk, msg, rng)
    @input sk: same as above
    @input Nym: same as above
    @input RandNym: same as above
    @input Ipk: same as above
    @input msg: same as above
    @input rng: same as above
    @return nymsig: pseudonym signature
    * `Verify()`
    err = nymsig.Ver(Nym, key.Ipk, msg)
    @this nymsig: the pseudonym signature Verifier received from user.
    @input ... -->
    ## Anonymous credential

    __Notice:__ This protocol is based on DAA+ protocol from [CDL16], some steps have been changed
    @@ -476,8 +352,8 @@ type Credential struct {
    }
    ```


    #### <3> Sign phase
    ## 3. Presentation protocol
    ### 3.1 proof generation

    Signer's information:

    @@ -575,7 +451,7 @@ type Signature struct {
    }
    ```

    #### <4> Verify phase
    ### 3.2 proof verification

    Verifier's information:

  7. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 2 additions and 13 deletions.
    15 changes: 2 additions & 13 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -65,20 +65,9 @@ The protocol we give is a standard sigma protocol. It consists three steps, name
    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
    In the presentation protocol specified in section 3, the core part is to prove knowledge of BBS+ signature (A,e,s), namely,

    `π <--$-- SPK{ (e, r2, r3, s'):`
    {
    `_A/d = A'^(-e) * h0^r2` &&
    `g1 * MulAll(h_i^mi) = d^r3 * h0^(-s')`
    }
    `π = SPoK{ (e, r2, r3, s'): _A/d = A'^(-e) * h0^r2 && g1 * MulAll(h_i^mi) = d^r3 * h0^(-s') }`
    ```c
    // {mi} is turple of message, such like blocks.
  8. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 10 additions and 25 deletions.
    35 changes: 10 additions & 25 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -31,25 +31,10 @@ The user who is in possession of that credential can selectively disclose some p
    - *Verify(pk, m1, ..., mL, sig)*:
    decode sig as (A, E, s), and check if `e(A, h0^E * pk) == e(B, h0)`.

    ### 1.2 Statistical Proof of Knowledge (SPK) protocol
    ### 1.2 Statistical Non-Interactive Proof of Knowledge (SPoK) protocol
    In this subsection, we give an example of non-interactive statistical proof of knowledge protocol which proves that the public key is generated as specfied in the BBS+ signature scheme. That is, `π = SPoK{x: w = g2^x && _g2 = _g1^x}` which can be translated as the prover proves knowledge of `x` such that `g2^x = w` and `_g2 = _g1^x`. And `w, g2, _g1, _g2` are assumed to be public.

    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. `p` is order.

    ```go
    g1, g2, n //public parameters, g1, g2 are generator of G1,G2 seperately. `p` is the order of the groups.
    (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}
    The protocol we give is a standard sigma protocol. It consists three steps, namely, **commit-challenge-response**. And the proof π = {C, S}

    1. commitment(prover):
    ```go
    @@ -61,23 +46,23 @@ For `Issuer`, Prove knowledge of the private key x by creating `π <--$-- SPK{x:
    ```
    2. proof(prover):
    ```go
    P = t1 || t2 || g2 || _g1 || w || _g2 //join them together in bytes format
    P = t1 || t2 || g2 || _g1 || w || _g2 //join them together in binary format
    C = hash(P) % n //C is challenge
    C = hash_to_int(P) //C is challenge
    S = (r + C * x) % n //response to verifier
    S = (r + C * x) % p //response to verifier
    ```
    3. verify(verifier):
    ```go
    _t1 = g2^S + w^((-c) % n)
    _t1 = g2^S * w^((-c))
    _t2 = _g1^S + _g2^((-c) % n)
    _t2 = _g1^S * _g2^((-c))
    _P = _t1 || _t2 || g2 || _g1 || w || _g2
    _C = hash(_P) % n //do the same thing like prover, everything is public
    _C = hash_to_int(_P) //do the same thing like prover, everything is public
    C ?= _C // use C to compare with _C, which was calculated just now
    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}
  9. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -31,12 +31,12 @@ The user who is in possession of that credential can selectively disclose some p
    - *Verify(pk, m1, ..., mL, sig)*:
    decode sig as (A, E, s), and check if `e(A, h0^E * pk) == e(B, h0)`.

    ### Example of SPK protocol
    ### 1.2 Statistical Proof of Knowledge (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.
    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. `p` is order.

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

    x = rand{Zp} //issuer's secret key, an integer number
  10. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 7 additions and 7 deletions.
    14 changes: 7 additions & 7 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -15,21 +15,21 @@ The user who is in possession of that credential can selectively disclose some p
    - Verify(m, sig): check if e(pk * g^{H(m)}, g^sig) == e(g, g). -->

    ### 1.1 BBS+ signature
    - Setup: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.
    - *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.
    - *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).
    - *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).
    - *Verify(pk, m1, ..., mL, sig)*:
    decode sig as (A, E, s), and check if `e(A, h0^E * pk) == e(B, h0)`.

    ### Example of SPK protocol

  11. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -6,15 +6,15 @@ Issuer creates a certificate to user which contains a list of user's attributes
    The user who is in possession of that credential can selectively disclose some parts to some verifier. This protocol is formally called
    **presentation protocol**.

    ## Background
    ## 1. 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
    ### 1.1 BBS+ signature
    - Setup: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.

    common params:
  12. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 2 additions and 6 deletions.
    8 changes: 2 additions & 6 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -7,16 +7,12 @@ The user who is in possession of that credential can selectively disclose some p
    **presentation protocol**.

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

    - 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.
  13. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 6 additions and 1 deletion.
    7 changes: 6 additions & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,10 @@
    # 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.
    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**.

    ## Background

  14. kunxian-xia revised this gist Jul 19, 2018. 1 changed file with 9 additions and 8 deletions.
    17 changes: 9 additions & 8 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -342,7 +342,7 @@ type Credential struct { // (A, e, s) is BBS+ signature



    ## The __DAA Protocol__(Direct anonymous attestation) with Extensions __Πdaa+__
    ## Anonymous credential

    __Notice:__ This protocol is based on DAA+ protocol from [CDL16], some steps have been changed
    in order to satisfy our demands.
    @@ -356,9 +356,8 @@ Roles:
    Steps:

    1. Issuer Setup
    2. User Join
    3. User(Prover) Sign
    4. User(Verifier) Verify
    2. Issuance ( Issuer -> User )
    3. Presentation ( Prover -> Verifier )

    <!-- 1. Issuer Setup
    2. Join Request
    @@ -371,11 +370,13 @@ Steps:
    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
    - `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
    - `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

  15. kunxian-xia revised this gist Jul 16, 2018. 1 changed file with 6 additions and 3 deletions.
    9 changes: 6 additions & 3 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -143,17 +143,20 @@ C ?= C'
    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
    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
    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
    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:

  16. kunxian-xia revised this gist Jul 16, 2018. 1 changed file with 549 additions and 17 deletions.
    566 changes: 549 additions & 17 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,9 @@
    # 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
    ### 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).
    @@ -9,7 +13,7 @@
    - Verify(m, sig): check if e(pk * g^{H(m)}, g^sig) == e(g, g).


    ## BBS+ signature
    ### BBS+ signature
    - Setup: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.

    common params:
    @@ -26,10 +30,116 @@
    - Verify(pk, m1, ..., mL, sig):
    decode sig as (A, e, s), and check if pairing(A, h0^e * pk) == pairing(B, h0).

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

    ```go
    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):
    ```go
    r = rand{Zp}

    t1 = g2^r

    t2 = _g1^r
    ```
    2. proof(prover):
    ```go
    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):
    ```go
    _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')`
    }
    ```c
    // {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'

    ### 1. Issuance protocol
    // 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.
    @@ -60,20 +170,20 @@ In short, this can be summarized in the following diagram:
    - Credential contains the BBS+ signature on attributes and Nym.
    ```go
    type IssuerSecretKey BigNum
    type IssuerSecretKey BigNum // call it 'isk', a random number from Zp
    ```
    ```go
    type IssuerPublicKey struct {
    type IssuerPublicKey struct { // call it 'ipk'
    AttributeNames []string
    HSk ECPoint //used to hide user's master secret
    HRand ECPoint //used to encode s
    HAttrs []ECPoint //used to encode attributes
    W ECPoint2 //equals to h0^x
    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 //
    BarG2 ECPoint //
    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
    }
    @@ -95,16 +205,436 @@ type CredRequest struct {
    ```

    ```go
    type Credential struct {
    type Credential struct { // (A, e, s) is BBS+ signature
    A ECPoint
    B ECPoint
    e BigNum
    s BigNum
    Attrs [][]byte
    Attrs [][]byte
    Attrnames []string
    }
    ```
    ### 2. Proof protocol
    <!-- ### 2. Proof protocol
    - __Presentation.__
    A user signs a message or authenticates with her credentials by deriving a fresh and unlinkable presentation token from her credentials according to an access control policy, hereafter called __presentation policy__. A presentation policy specifies which attributes (or which predicates about certain attributes) from which type of credential a user should include in the presentation token. It also specifies the public key(s) of the credential issuing authority(ies), which the verifier trusts to correctly certify users' attributes. If the user consents to disclose the information required by the policy, the presentation token is sent for verification.
    - __Verification.__
    The token is verified whether it satisfies the presentation policy using the public key(s) of the credential issuing authority(ies) (CA).
    - __Construction__
    An __Identity Mixer signature__ is a signature of knowledge that __signs a message and proves: (in zero-knowledge)__
    - the knowledge of the user secret (and possibly attributes) signed inside a credential
    - that was issued by a certain issuer (referred to with the issuer public key)
    - The signature is verified using the message being signed and the public key of the issuer
    - Some of the attributes from the credential can be selectvely disclosed or different statements can be proven about
    - credential atrributes without diclosing them in the clear
    The proof protocol is a non-interactive protocol with just 2 steps
    1. Prover signs a message
    - __Detail__
    ```go
    // 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 *ECP // A' = A^{r1} ...... A is cred.A
    ABar *ECP // barA = A'^{-e} B^{r1} ...... e is cred.e, B is cred.B
    BPrime *ECP // B' = B^{r1} h_r^{-r2} ...... h_r is ipk.HRand
    ProofC []byte
    ProofSSk []byte
    ProofSE []byte
    ProofSR2 []byte
    ProofSR3 []byte
    ProofSSPrime []byte // s' = s - r2 * r3
    ProofSAttrs [][]byte
    Nonce []byte
    Nym *ECP
    ProofSRNym []byte
    RevocationEpochPk *ECP2
    RevocationPkSig []byte
    Epoch int64
    NonRevocationProof *NonRevocationProof
    }
    ```
    ```go
    // NymSignature specifies a signature object that signs a message
    // with respect to a pseudonym. It differs from the standard idemix.signature in the fact that
    // the standard signature object also proves that the pseudonym is based on a secret certified by
    // a CA (issuer), whereas NymSignature only proves that the the owner of the pseudonym
    // signed the message
    type NymSignature struct {
    ProofC []byte // proof_c is the Fiat-Shamir challenge of the ZKP
    ProofSSk []byte // proof_s_sk is the s-value proving knowledge of the user secret key
    ProofSRNym []byte // proof_s_r_nym is the s-value proving knowledge of the pseudonym secret
    Nonce []byte // nonce is a fresh nonce used for the signature
    }
    ```
    - standard idemix.signature:
    * `Sign()`
    sig, err = NewSignature(cred, sk, Nym, RandNym, key.Ipk, disclosure, msg, rhindex, cri, rng)
    @input cred: the crendential user has got in Issuance Process.
    @input sk: the secret key of user.
    @input Nym: a EC point, computed from RandNym
    // Nym = EcpFromProto(IPk.HSk).Mul2(sk, EcpFromProto(IPk.HRand), RandNym).
    @input RandNym: a random number of Z* .
    @input Ipk: the publick key of Issuer.
    @input disclosure: an array of 1/0, 1 means the attr[i] will be disclosed by user.
    @input msg: the message to sign.
    @input rhindex: ????.
    @input cri: a Credential Revocation Information for a certain time period
    @input rng: a random generator, just ignore.
    @return sig: signature
    * `Verify()`
    err = sig.Ver(disclosure, key.Ipk, msg, attrs, rhindex, &revocationKey.PublicKey, epoch)
    @this sig: the signature Verifier received from user.
    @input disclosure: same as sign(), from user.
    @input Ipk: same as sign(), from issuer.
    @input msg: same as sign(), from user.
    @input attrs: the collection of attributed's map, from setup stage.
    @input rhindex: ???.
    @input &revocationKey.PublicKey: a ecdsa key pair, used in CRI creation.
    @input epoch: time point, a number. used in CRI creation.
    - pseudonym signature:
    * `Sign()`
    nymsig, err = NewNymSignature(sk, Nym, RandNym, key.Ipk, msg, rng)
    @input sk: same as above
    @input Nym: same as above
    @input RandNym: same as above
    @input Ipk: same as above
    @input msg: same as above
    @input rng: same as above
    @return nymsig: pseudonym signature
    * `Verify()`
    err = nymsig.Ver(Nym, key.Ipk, msg)
    @this nymsig: the pseudonym signature Verifier received from user.
    @input ... -->




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

    <!-- 1. Issuer Setup
    2. Join Request
    3. Join Proceed
    4. Sign Request
    5. Sign Proceed
    6. Verify
    7. Link -->

    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:

    ```go
    struct IssuerSecretKey{
    x BigNum
    }
    ```
    ```go
    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> Join phase

    <!-- see Issuance protocol -->

    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:

    ```go
    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
    }
    ```

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


    #### <3> Sign phase

    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
    <!-- - `n` - nonce, with τ bit length -->

    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:

    ```go
    // 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 phase

    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.


    <!-- In __Proof Protocol__, the ZKPoK of User's BBS+ signature (A,e,s) is
    `π <--$-- SPK{(gsk, {ai}_fasle, e, r2, r3, s'):`
    {
    `_A/d = A'^(-e) * h0^r2` &&
    `g1 * MulAll(h_{i+1}^ai_true) = d^r3 * h0^(-s') * h_sk^(-gsk) * MulAll(h_{i+1}^(-ai_false))` &&
    `nym = H1(bsn)^gsk `
    }
    {ai} is User's attribute set. "_fasle" means the attributs that User wants to hide, "_true" means the attributes User wants to disclose.
    π = {C, S_gsk, S_e, S_r2, S_r3, S_s', S_Nym, S_attrs} -->

    ## References
    [CL02]. J. Camenisch and A. Lysyanskaya. A Signature Scheme with Efficient Protocols. SCN 2002.
    @@ -114,4 +644,6 @@ 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.
    [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.
  17. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 11 additions and 0 deletions.
    11 changes: 11 additions & 0 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -93,6 +93,17 @@ type CredRequest struct {
    ProofS2 BigNum
    }
    ```

    ```go
    type Credential struct {
    A ECPoint
    B ECPoint
    e BigNum
    s BigNum
    Attrs [][]byte
    Attrnames []string
    }
    ```
    ### 2. Proof protocol

    ## References
  18. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 14 additions and 0 deletions.
    14 changes: 14 additions & 0 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -78,7 +78,21 @@ type IssuerPublicKey struct {
    ProofS BigNum // response in Sigma-protocol
    }
    ```

    ```go
    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
    }
    ```
    ### 2. Proof protocol

    ## References
  19. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 18 additions and 3 deletions.
    21 changes: 18 additions & 3 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -47,22 +47,37 @@ The issuance protocol is an interactive protocol which consists of the following

    In short, this can be summarized in the following diagram:

    Issuer -------------------- Prover
    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.
    - 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.
    - Credential contains the BBS+ signature on attributes and Nym.

    ```go
    type IssuerSecretKey BigNum
    ```

    ```go
    type IssuerPublicKey struct {
    AttributeNames []string
    HSk ECPoint //used to hide user's master secret
    HRand ECPoint //used to encode s
    HAttrs []ECPoint //used to encode attributes
    W ECPoint2 //equals to h0^x

    // PoK that the public key is valid.
    BarG1 ECPoint //
    BarG2 ECPoint //
    ProofC BigNum // challenge in Sigma-protocol
    ProofS BigNum // response in Sigma-protocol
    }
    ```

    ### 2. Proof protocol

  20. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 10 additions and 1 deletion.
    11 changes: 10 additions & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -23,6 +23,9 @@
    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).

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

    @@ -52,7 +55,13 @@ In short, this can be summarized in the following diagram:

    --- Credential --->

    CredRequest contains a commitment to user's master secret which is of the form g
    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.

    ```go
    type IssuerSecretKey BigNum
    ```


    ### 2. Proof protocol
  21. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 12 additions and 1 deletion.
    13 changes: 12 additions & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -12,7 +12,10 @@
    ## BBS+ signature
    - Setup: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.

    common params: g0, g1, (g2, ..., g_{L+1}).
    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.

    @@ -42,6 +45,14 @@ The issuance protocol is an interactive protocol which consists of the following
    In short, this can be summarized in the following diagram:

    Issuer -------------------- Prover

    -- nonce(BigNum)-->

    <-- CredRequest --

    --- Credential --->

    CredRequest contains a commitment to user's master secret which is of the form g


    ### 2. Proof protocol
  22. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -41,8 +41,8 @@ The issuance protocol is an interactive protocol which consists of the following

    In short, this can be summarized in the following diagram:

    Issuer | | Prover
    ------ |------ |------
    Issuer -------------------- Prover


    ### 2. Proof protocol

  23. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -41,8 +41,8 @@ The issuance protocol is an interactive protocol which consists of the following

    In short, this can be summarized in the following diagram:

    | Issuer | | Prover |
    | ------ |------ |------ |
    Issuer | | Prover
    ------ |------ |------

    ### 2. Proof protocol

  24. kunxian-xia revised this gist Jul 4, 2018. 1 changed file with 26 additions and 0 deletions.
    26 changes: 26 additions & 0 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -19,7 +19,33 @@
    - 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).

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

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

    ### 2. Proof protocol

    ## References
    [CL02]. J. Camenisch and A. Lysyanskaya. A Signature Scheme with Efficient Protocols. SCN 2002.

  25. kunxian-xia revised this gist Jul 3, 2018. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -26,5 +26,6 @@
    [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
    [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.
  26. kunxian-xia revised this gist Jul 3, 2018. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -26,4 +26,5 @@
    [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.
  27. kunxian-xia revised this gist Jul 3, 2018. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -22,6 +22,8 @@

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

    [BBS+]. Man Ho Au, Willy Susilo, and Yi Mu. Constant-Size Dynamic k-TAA. SCN 2006.
  28. kunxian-xia revised this gist Jul 3, 2018. 1 changed file with 9 additions and 2 deletions.
    11 changes: 9 additions & 2 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,4 @@

    ## BBS signature

    - Setup: generate a pairing-friendly curve G, and target group Gt, pairing func e: G x G -> Gt.
    @@ -8,7 +9,7 @@
    - Verify(m, sig): check if e(pk * g^{H(m)}, g^sig) == e(g, g).


    ### BBS+ signature
    ## BBS+ signature
    - Setup: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.

    common params: g0, g1, (g2, ..., g_{L+1}).
    @@ -17,4 +18,10 @@

    - 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).
    The sig is (A, e, s).

    ## 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.
    [BBS+]. Man Ho Au, Willy Susilo, and Yi Mu. Constant-Size Dynamic k-TAA. SCN 2006.
  29. kunxian-xia revised this gist Jul 3, 2018. 1 changed file with 13 additions and 1 deletion.
    14 changes: 13 additions & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -5,4 +5,16 @@

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

    - 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).
  30. kunxian-xia revised this gist Jun 7, 2018. 1 changed file with 5 additions and 1 deletion.
    6 changes: 5 additions & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,8 @@
    ## BBS signature

    - Setup: generate a pairing-friendly curve G, and target group Gt, pairing func e: G x G -> Gt.
    - KeyGen:
    - 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).