Skip to content

Instantly share code, notes, and snippets.

@Doresimon

Doresimon/anon_cred.md

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

Revisions

  1. Doresimon revised this gist Jul 23, 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
    @@ -558,8 +558,8 @@ Start to sign:
    - `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_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.
  2. Doresimon revised this gist Jul 17, 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
    @@ -168,7 +168,7 @@ In short, this can be summarized in the following diagram:
    - 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 // call it 'isk', a random number from Zp
    ```
    @@ -213,7 +213,7 @@ type Credential struct { // (A, e, s) is BBS+ signature
    Attrs [][]byte
    Attrnames []string
    }
    ```
    ``` -->
    <!-- ### 2. Proof protocol
    - __Presentation.__
  3. Doresimon revised this gist Jul 17, 2018. 2 changed files with 18 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
    @@ -435,7 +435,7 @@ After issuer's setup, it makes `ipk` published, so public parameters has followi
    - `HRand`
    - `HSk`

    #### <2> Join phase
    #### <2> Issurance

    <!-- see Issuance protocol -->

    @@ -498,7 +498,7 @@ type Credential struct {
    ```


    #### <3> Sign phase
    #### <3> Presentation

    Signer's information:

    @@ -596,7 +596,7 @@ type Signature struct {
    }
    ```

    #### <4> Verify phase
    #### <4> Verify

    Verifier's information:

    15 changes: 15 additions & 0 deletions interface.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,20 @@
    # Anonymous Credential Interface Instruction

    ## Process

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

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

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

    ## Dependent Library

    1. Bignum
  4. Doresimon revised this gist Jul 17, 2018. 1 changed file with 9 additions and 7 deletions.
    16 changes: 9 additions & 7 deletions interface.md
    View file
    Original file line number Diff line number Diff line change
    @@ -52,7 +52,7 @@ class IssuerPublicKey {
    ```
    ```c++
    class IssuerSecretKey { // for isk, class is not a must, BigNum is ok.
    class IssuerSecretKey { // for IssuerSecretKey, class is not a must, BigNum is ok.
    BigNum isk;
    }
    ```
    @@ -113,29 +113,31 @@ class Signature {
    ## Main Function

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

    bool CheckIssuerKey(IssuerPublicKey ipk) // check correctness of Issuer's public key, Zero Knowledge Verification
    ```
    ```c++
    CredRequest GenerateCredRequest(IssuerNonce nonce) // User generate credential request with nonce from Issuer
    CredRequest GenerateCredRequest(BigNum usk, IssuerNonce nonce, IssuerPublicKey ipk) // User generate credential request with nonce from Issuer
    ```

    ```c++
    Credential GenerateCredential(CredRequest cr) // Issuer generates Credential for user with credential request
    Credential GenerateCredential(IssuerKey key, CredRequest cr, BigNum Attrs[]) // Issuer generates Credential for user with credential request
    ```
    ```c++
    Signature Sign(Credential c, bool Disclosure[], BigNum IndexAttrs[], string bsn) // User signs a message with its Credential
    Signature Sign(Credential c, BigNum usk, BigNum bsn, G1Point nym, bool Disclosure[], string message, IssuerPublicKey ipk) // User signs a message with its Credential
    ```

    ```c++
    bool Verify(Signature sig) // Another user verifies a signature.
    bool Verify(bool Disclosure[], BigNum Attrs[], Signature sig, string message, IssuerPublicKey ipk) // Another user verifies a signature.
    ```
    ## Utility Function
    ```c++
    string/char* Marshal(any*); // Marshal a class for communication and transfer.
    string/char* Marshal(any*); // Marshal a class(IssuerPublicKey, CredRequest, Credential...) for communication and transfer.
    any* UnMarshal(string/char*); // Unmarshal data.
    ```
  5. Doresimon revised this gist Jul 17, 2018. 1 changed file with 6 additions and 11 deletions.
    17 changes: 6 additions & 11 deletions interface.md
    View file
    Original file line number Diff line number Diff line change
    @@ -7,6 +7,7 @@
    3. Pairing
    4. Rand
    5. Hash
    6. Protobuf / Json

    ## Elliptic

    @@ -15,21 +16,13 @@ Use BN256 as Pairing Based Curve
    ```c++
    // G1 Point
    class G1Point {
    // char X[];
    // char Y[];

    BigNum X;
    BigNum Y;
    }
    ```
    ```c++
    // G2 Point
    class G2Point {
    // char Xa[];
    // char Xb[];
    // char Ya[];
    // char Yb[];
    BigNum Xa;
    BigNum Xb;
    BigNum Ya;
    @@ -132,15 +125,17 @@ Credential GenerateCredential(CredRequest cr) // Issuer generates Credential for
    ```

    ```c++
    Signature Sign(Credential c, bool Disclosure[], BigNum IndexAttrs[], string bsn) // User sign a message with its Credential
    Signature Sign(Credential c, bool Disclosure[], BigNum IndexAttrs[], string bsn) // User signs a message with its Credential
    ```
    ```c++
    bool Verify(Signature sig) // User sign a message with its Credential
    bool Verify(Signature sig) // Another user verifies a signature.
    ```

    ## Utility Function

    ```c++
    string/char* Marshal(any*); // Marshal the * class for communication and transfer.
    string/char* Marshal(any*); // Marshal a class for communication and transfer.

    any* UnMarshal(string/char*); // Unmarshal data.
    ```
  6. Doresimon revised this gist Jul 17, 2018. 1 changed file with 146 additions and 0 deletions.
    146 changes: 146 additions & 0 deletions interface.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,146 @@
    # Anonymous Credential Interface Instruction

    ## Dependent Library

    1. Bignum
    2. Elliptic
    3. Pairing
    4. Rand
    5. Hash

    ## Elliptic

    Use BN256 as Pairing Based Curve

    ```c++
    // G1 Point
    class G1Point {
    // char X[];
    // char Y[];

    BigNum X;
    BigNum Y;
    }
    ```
    ```c++
    // G2 Point
    class G2Point {
    // char Xa[];
    // char Xb[];
    // char Ya[];
    // char Yb[];
    BigNum Xa;
    BigNum Xb;
    BigNum Ya;
    BigNum Yb;
    }
    ```

    ## Issuer's Key Pair

    ```c++
    class IssuerPublicKey {
    string AttributeNames[];

    G1Point HSk;
    G1Point HRand;
    G1Point HAttrs[];

    G2Point W;

    G1Point _g1;
    G1Point _g2;

    BigNum ProofC;
    BigNum ProofS;

    }
    ```
    ```c++
    class IssuerSecretKey { // for isk, class is not a must, BigNum is ok.
    BigNum isk;
    }
    ```

    ```c++
    class IssuerKey {
    IssuerSecretKey Isk;
    IssuerPublicKey Ipk;
    }
    ```
    ## Credential Request
    ```c++
    class CredRequest {
    G1Point Nym;
    BigNum IssuerNonce;
    BigNum ProofC;
    BigNum ProofS;
    }
    ```

    ## User's Credential

    ```c++
    class Credential {
    G1Point A;
    G1Point B;
    BigNum E;
    BigNum S;
    BigNum Attrs[];
    }
    ```
    ## User's Signature
    ```c++
    class Signature {
    G1Point APrime
    G1Point ABar
    G1Point BPrime
    BigNum ProofC
    /* response in sigma-protocol */
    BigNum ProofSSk
    BigNum ProofSE
    BigNum ProofSR2
    BigNum ProofSR3
    BigNum ProofSSPrime
    BigNum ProofSAttrs[]
    BigNum Nonce // a fresh nonce used for the signature
    G1Point Nym // a fresh pseudonym (a commitment to to the user secret)
    }
    ```

    ## Main Function

    ```c++
    IssuerKey IssuerSetup() // Issuer generates key pair
    ```

    ```c++
    CredRequest GenerateCredRequest(IssuerNonce nonce) // User generate credential request with nonce from Issuer
    ```
    ```c++
    Credential GenerateCredential(CredRequest cr) // Issuer generates Credential for user with credential request
    ```

    ```c++
    Signature Sign(Credential c, bool Disclosure[], BigNum IndexAttrs[], string bsn) // User sign a message with its Credential
    ```
    ```c++
    bool Verify(Signature sig) // User sign a message with its Credential
    ```

    ## Utility Function

    ```c++
    string/char* Marshal(any*); // Marshal the * class for communication and transfer.
    ```
  7. Doresimon revised this gist Jul 16, 2018. 1 changed file with 117 additions and 113 deletions.
    230 changes: 117 additions & 113 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'

    // 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
    ```
    ### 1. Issuance protocol
    ## 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.
    @@ -95,7 +205,7 @@ type CredRequest struct {
    ```

    ```go
    type Credential struct {
    type Credential struct { // (A, e, s) is BBS+ signature
    A ECPoint
    B ECPoint
    e BigNum
    @@ -227,115 +337,9 @@ type Credential struct {
    @input ... -->


    ### 3. 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) Protocol__, there is also a SPK of `User's` private key __sk__ `π <--$-- SPK{(gsk): Q =h_sk^gsk}(nonce)`, π = {C, S}

    In __Sign Protocol__, 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'

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

    ### 4. The __DAA Protocol__(Direct anonymous attestation) with Extensions __Πdaa+__
    ## 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.
  8. Doresimon revised this gist Jul 16, 2018. 1 changed file with 5 additions and 5 deletions.
    10 changes: 5 additions & 5 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -175,7 +175,7 @@ type Credential struct {
    sig, err = NewSignature(cred, sk, Nym, RandNym, key.Ipk, disclosure, msg, rhindex, cri, rng)
    @input cred: the crendential user has got in Issurance Process.
    @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).
    @@ -276,7 +276,7 @@ For `Issuer`, Prove knowledge of the private key x by creating `π <--$-- SPK{x:
    C ?= _C // use C to compare with _C, which was calculated just now
    ```

    In __Issurance(Join) Protocol__, there is also a SPK of `User's` private key __sk__ `π <--$-- SPK{(gsk): Q =h_sk^gsk}(nonce)`, π = {C, S}
    In __Issuance(Join) Protocol__, there is also a SPK of `User's` private key __sk__ `π <--$-- SPK{(gsk): Q =h_sk^gsk}(nonce)`, π = {C, S}

    In __Sign Protocol__, the SPK of User's BBS+ signature (A,e,s) is
    @@ -433,9 +433,9 @@ After issuer's setup, it makes `ipk` published, so public parameters has followi

    #### <2> Join phase

    <!-- see Issurance protocol -->
    <!-- see Issuance protocol -->

    Join phase has 3 steps. So it is an interactive phase.
    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
    @@ -459,7 +459,7 @@ With nonce number `n`, user generates its key pair, same as CredRequest.
    - `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.
    User sends `(Q, π)` to Issuer.

    `Issuer`

  9. Doresimon revised this gist Jul 16, 2018. 1 changed file with 30 additions and 30 deletions.
    60 changes: 30 additions & 30 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -173,12 +173,12 @@ type Credential struct {
    * `Sign()`
    sig, err := NewSignature(cred, sk, Nym, RandNym, key.Ipk, disclosure, msg, rhindex, cri, rng)
    sig, err = NewSignature(cred, sk, Nym, RandNym, key.Ipk, disclosure, msg, rhindex, cri, rng)
    @input cred: the crendential user has got in Issurance 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).
    // 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.
    @@ -207,7 +207,7 @@ type Credential struct {
    * `Sign()`
    nymsig, err := NewNymSignature(sk, Nym, RandNym, key.Ipk, msg, rng)
    nymsig, err = NewNymSignature(sk, Nym, RandNym, key.Ipk, msg, rng)
    @input sk: same as above
    @input Nym: same as above
    @@ -235,11 +235,11 @@ Suppose we have initialized the Issuer's key pair, now we need to generate a Non
    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
    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
    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
    }
    @@ -249,29 +249,29 @@ For `Issuer`, Prove knowledge of the private key x by creating `π <--$-- SPK{x:

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

    t1 := g2^r
    t1 = g2^r

    t2 := _g1^r
    t2 = _g1^r
    ```
    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 bytes format
    C := hash(P) % n //C is challenge
    C = hash(P) % n //C is challenge
    S := (r + C * x) % n //response to verifier
    S = (r + C * x) % n //response to verifier
    ```
    3. verify(verifier):
    ```go
    _t1 := g2^S + w^((-c) % n)
    _t1 = g2^S + w^((-c) % n)
    _t2 := _g1^S + _g2^((-c) % n)
    _t2 = _g1^S + _g2^((-c) % n)
    _P := _t1 || _t2 || g2 || _g1 || w || _g2
    _P = _t1 || _t2 || g2 || _g1 || w || _g2
    _C := hash(_P) % n //do the same thing like prover, everything is public
    _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
    ```
    @@ -387,10 +387,10 @@ generate Issuer's key pair:
    - `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]
    - `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
    - `HAttr` : h[i] = random(G1), len(HAttr) = len(AttributeName), __h1, h2, h3 ... hL__
    - `HRand` : h0 = random(G1)
    - `HSk` : h_sk = random(G1)
    @@ -455,7 +455,7 @@ With nonce number `n`, user generates its key pair, same as CredRequest.
    - `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
    - `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.
    @@ -537,16 +537,16 @@ Start to sign:
    `nym = H1(bsn)^gsk `

    }
    - `r_ai` : for i belongs to _D(attributes not disclosed), means D[i]==0
    - `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
    - `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
    @@ -597,19 +597,19 @@ type Signature struct {
    Verifier's information:

    - `(A', _A, d, nym, π)` : from signer
    - `{c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}` : parse π
    - `{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._
    - `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.__
    - 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.

  10. Doresimon revised this gist Jul 16, 2018. 1 changed file with 86 additions and 85 deletions.
    171 changes: 86 additions & 85 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -350,8 +350,8 @@ Steps:
    1. Issuer Setup
    2. User Join
    3. User Sign
    4. User Verify
    3. User(Prover) Sign
    4. User(Verifier) Verify
    <!-- 1. Issuer Setup
    2. Join Request
    @@ -364,15 +364,15 @@ Steps:
    Public Parameter:
    - `τ` : security parameter
    - `G1` `G2` `GT` : a bilinear group
    - `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
    #### Setup phase
    #### <1> Setup phase
    `Issuer`
    @@ -385,14 +385,14 @@ generate Issuer's key pair:
    - `_g2` : _g2 = _g1^x
    - `π <--$-- SPK{x: w = g2^x && _g2 = _g1^x}` - π = (C, S)
    - `r` : r = rand{Zp}
    - `t1` : t1 = g2^r
    - `t2` : t2 = _g1^r
    - `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)
    - `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:
    @@ -404,7 +404,8 @@ struct IssuerSecretKey{
    ```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.
    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

    @@ -418,7 +419,7 @@ struct IssuerPublicKey{

    After issuer's setup, it makes `ipk` published, so public parameters has following addition content:

    - `ipk` - Issuer's public key
    - `ipk` : Issuer's public key
    - `w`
    - `_g1`
    - `_g2`
    @@ -430,7 +431,7 @@ After issuer's setup, it makes `ipk` published, so public parameters has followi
    - `HRand`
    - `HSk`

    #### Join phase
    #### <2> Join phase

    <!-- see Issurance protocol -->

    @@ -444,32 +445,32 @@ Join phase has 3 steps. So it is an interactive phase.

    Issuer generates a nonce, which is a random big number with τ bits and sends it to user.

    - `n` - nonce, n = rand{BigNum(τ)}
    - `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
    - `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, []BigNum, random from Zp, corresponding to user's attributes.
    - `b` - b = g1 · h0^s · Q · MulAll(hi^ai)
    - `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) )
    - `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:

    @@ -493,7 +494,7 @@ type Credential struct {
    ```


    #### Sign phase
    #### <3> Sign phase

    Signer's information:

    @@ -506,24 +507,21 @@ Signer's information:
    - `s`
    - `b`
    - extra input
    - `m` - message to sign
    - `(D, I)` - attribute predicate, describe what attributes will be disclosed
    - `bsn` - basename, a string to make signature different everytime
    - `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
    - `r_gsk` - random from Zp
    - `E` - E = h_sk^r_gsk
    - `L` - L = H1(bsn)^r_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
    - `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'):`

    {
    @@ -539,25 +537,28 @@ Start to sign:
    `nym = H1(bsn)^gsk `

    }
    - `r_ai` - for i belongs to _D(attributes not disclosed)
    - `r_e` - random from Zp
    - `r_r2` - random from Zp
    - `r_r3` - random from Zp
    - `r_s'` - random from Zp
    - `t1` - t1 = A'^r_e · h0^r_r2
    - `t2` - t2 = d^r_r3 · h0^r_s' · E^(-1) · MulAll(h_{i+1})^r_ai
    - `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.
    - `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}

    @@ -571,46 +572,46 @@ Suggested data structure:
    // 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
    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
    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 // ???

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

    #### Verify phase
    #### <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 π
    - `(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
    - the i above, second MulAll( ) belongs to D
    - _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.
    - `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
  11. Doresimon revised this gist Jul 13, 2018. 1 changed file with 3 additions and 1 deletion.
    4 changes: 3 additions & 1 deletion anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -639,4 +639,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.
  12. Doresimon revised this gist Jul 13, 2018. 1 changed file with 26 additions and 22 deletions.
    48 changes: 26 additions & 22 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -226,7 +226,7 @@ type Credential struct {
    @input ... -->

    <!--

    ### 3. 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.
    @@ -276,9 +276,9 @@ For `Issuer`, Prove knowledge of the private key x by creating `π <--$-- SPK{x:
    C ?= _C // use C to compare with _C, which was calculated just now
    ```

    In __Issurance Protocol__, there is also a SPK of `User's` private key __sk__ `π <--$-- SPK{(gsk): Q =h1^gsk}(nonce)`, π = {C, S}
    In __Issurance(Join) Protocol__, there is also a SPK of `User's` private key __sk__ `π <--$-- SPK{(gsk): Q =h_sk^gsk}(nonce)`, π = {C, S}

    In __Proof Protocol__, the SPK of User's BBS+ signature (A,e,s) is
    In __Sign Protocol__, the SPK of User's BBS+ signature (A,e,s) is
    `π <--$-- SPK{ (e, r2, r3, s'):`
    @@ -333,10 +333,13 @@ C' = Hash(A' + _A + d + t1' + t2' + g1 + h_{0~max})
    C ?= C'
    // done
    ``` -->
    ```
    ### 4. 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
    @@ -481,9 +484,9 @@ type CredRequest struct {

    ```go
    type Credential struct {
    A G1Point
    A G1Point
    B G1Point
    e BigNum
    e BigNum
    s BigNum
    Attrs []BigNum
    }
    @@ -568,23 +571,23 @@ Suggested data structure:
    // nonce - a fresh nonce used for the signature
    // nym - a fresh pseudonym (a commitment to to the user secret)
    type Signature struct {
    APrime *ECP
    ABar *ECP
    BPrime *ECP
    ProofC BigNum
    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
    Nym *ECP
    ProofSRNym BigNum
    // RevocationEpochPk *ECP2
    // RevocationPkSig []byte
    // Epoch int64
    // NonRevocationProof *NonRevocationProof
    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 // ???
    }
    ```

    @@ -598,13 +601,14 @@ Verifier's information:
    Start to verify:

    - `A' ?= 1 of G1` - false: verify failed. true: continue.
    - `e(A', w) ?= e(_A, g2)` - 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^s_gsk · nym^(-c)
    - `~t1` - ~t1 = A'^s_e · h0^s_r2 · (_A/d)^(-c)
    - `~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
    - the i above, second MulAll( ) belongs to D
    - _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.

    @@ -617,7 +621,7 @@ Start to verify:
    `_A/d = A'^(-e) * h0^r2` &&
    `g1 * MulAll(h_{i+1}^ai_true) = d^r3 * h0^(-s') * h1^(-gsk) * MulAll(h_{i+1}^(-ai_false))` &&
    `g1 * MulAll(h_{i+1}^ai_true) = d^r3 * h0^(-s') * h_sk^(-gsk) * MulAll(h_{i+1}^(-ai_false))` &&
    `nym = H1(bsn)^gsk `
  13. Doresimon revised this gist Jul 13, 2018. 1 changed file with 187 additions and 47 deletions.
    234 changes: 187 additions & 47 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -29,7 +29,7 @@
    ## 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
    ### 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.

    @@ -340,72 +340,181 @@ C ?= C'
    Roles:

    - I - Issuer
    - M - TPM(Trusted Platform Module) // M and H can be substituted by one signer.
    - H - Host // M and H can be substituted by one signer.
    - V - Verifier
    - U - User
    - V - Verifier(also an user)

    Steps:

    1. Issuer Setup
    2. User Join
    3. User Sign
    4. User Verify

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

    Public Parameter:

    #### Setup protocol
    - `τ` : security parameter
    - `G1` `G2` `GT` : a bilinear group
    - `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

    #### 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
    - `t2` : t2 = _g1^r
    - `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:

    generate Issuer's key pair.
    ```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
    }
    ```

    #### Join protocol
    After issuer's setup, it makes `ipk` published, so public parameters has following addition content:

    see Issurance protocol
    - `ipk` - Issuer's public key
    - `w`
    - `_g1`
    - `_g2`
    - `π` = (`C`, `S`)
    - `C`
    - `S`
    - `AttributeName`
    - `HAttr`
    - `HRand`
    - `HSk`

    #### Join phase

    #### Sign protocol
    <!-- see Issurance protocol -->

    Public Parameter:
    Join phase has 3 steps. So it is an interactive phase.

    - `τ` - security parameter
    - `G1` `G2` `GT` - a bilinear group
    - `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
    - `isk` - Issuer's secret key, call it x.
    - `ipk` - Issuer's public key
    - `w` - w = g2^x
    - `_g1` - random element from G1
    - `_g2` - _g2 = _g1^x
    - `AttributeNames` - []string
    - `HAttrs` - []ECP, one attribute, one random G1 point, cprresponding to AttributeNames
    - `HSk` - ECP, cprresponding to secret key x(isk)
    - `HRand` - ECP, randomness
    1. Issuer --------nonce(BigNum)-------> User
    2. Issuer <-------CredRequest---------- User
    3. Issuer --------Credential----------> User

    Signer's information:
    `Issuer`

    - `gsk` - signer's secret key
    - `Q` - Q = h1^gsk, public key
    - `attrs = (a1,...,aL)` - one attribute, one number from Zp
    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
    - `C` : C = H(t1 || h_sk || Q || n)
    - `S` : S = (r + C * gsk) % p

    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, []BigNum, random from Zp, corresponding to user's attributes.
    - `b` - b = g1 · h0^s · Q · MulAll(hi^ai)
    - BBS+ signature
    - `A` - A = ( g1 · h0^s · Q · MulAll(h_{i+1}^ai) )^( 1/(e+x) )
    - `e` - random from Zp
    - `s` - random from Zp
    - `b` - b = g1 · h0^s · Q · MulAll(h_{i+1}^ai), so A = b^( 1/(e+x) )
    - `(D, I)` - attribute predicate, describe what attributes will be disclosed
    - `bsn` - basename, a string to make signature different everytime
    - `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
    }
    ```


    #### 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
    - `bsn` - basename, a string to make signature different everytime
    <!-- - `n` - nonce, with τ bit length -->

    Start to sign:

    - `nym` - nym = H1(bsn)^gsk
    - `nym` - nym = H1(bsn)^gsk
    - `r_gsk` - random from Zp
    - `E` - E = h1^r_gsk
    - `E` - E = h_sk^r_gsk
    - `L` - L = H1(bsn)^r_gsk
    - `r1` - random from Zp
    - `r1` - random from Zp*
    - `A'` - A' = A^r1
    - `r3` - r3 = 1/r1
    - `_A` - _A = A'^(−e) · b^r1 = A'^x
    @@ -420,7 +529,7 @@ Start to sign:

    &&

    `g1 · MulAll(h_{i+1}^ai_true) = d^r3 · h0^(-s') · h1^(-gsk) · MulAll(h_{i+1}^(-ai_false))`
    `g1 · MulAll(hi^ai_true) = d^r3 · h0^(-s') · h_sk^(-gsk) · MulAll(hi^(-ai_false))`

    &&

    @@ -435,20 +544,51 @@ Start to sign:
    - `t1` - t1 = A'^r_e · h0^r_r2
    - `t2` - t2 = d^r_r3 · h0^r_s' · E^(-1) · MulAll(h_{i+1})^r_ai
    - `c'` - c' = H(A', _A, d, nym, t1, t2, L, g1, h0, ... , hL, w)
    - `n` - nonce, with τ bit length
    - `n` - nonce, with τ bit length, randomly generated again
    - `m` - message to sign
    - `SRL` - signature-based revocation list, we don't use it.
    - `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}
    - `π` - {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}, i belong to _D
    - `(A', _A, d, nym, π)` - signature done.

    #### Verify ~~protocol~~ Algorithm
    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 *ECP
    ABar *ECP
    BPrime *ECP
    ProofC BigNum
    ProofSSk BigNum
    ProofSE BigNum
    ProofSR2 BigNum
    ProofSR3 BigNum
    ProofSSPrime BigNum
    ProofSAttrs []BigNum
    Nonce BigNum
    Nym *ECP
    ProofSRNym BigNum
    // RevocationEpochPk *ECP2
    // RevocationPkSig []byte
    // Epoch int64
    // NonRevocationProof *NonRevocationProof
    }
    ```

    #### Verify phase

    Verifier's information:

    @@ -458,14 +598,14 @@ Verifier's information:
    Start to verify:

    - `A' ?= 1 of G1` - false: verify failed. true: continue.
    - `e(A', X) ?= e(_A, g2)` - false: verify failed. true: continue.
    - `e(A', w) ?= e(_A, g2)` - false: verify failed. true: continue.
    - `π ---> {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}` - parse π
    - `~L` - ~L = h1^s_gsk · nym^(-c)
    - `~t1` - ~t1 = A'^s_e · h0^s_r2 · (_A/d)^(-c)
    - `~t2` - d^s_r3 · h0^s_s' · h1^(-s_gsk) · MulAll(h_{i+1})^(-s_ai) · (g1·MulAll(h_{i+1})^ai)^(-c)
    - `~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
    - the i above, second MulAll( ) belongs to D
    - `c'` - c' = H(n, H(A', _A, d, nym, ~t1, ~t2, ~L, g1, h0,... , hL, w), m, bsn, (D, I), SRL)
    - `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.


  14. Doresimon revised this gist Jul 10, 2018. 1 changed file with 142 additions and 9 deletions.
    151 changes: 142 additions & 9 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -100,11 +100,11 @@ type Credential struct {
    B ECPoint
    e BigNum
    s BigNum
    Attrs [][]byte
    Attrs [][]byte
    Attrnames []string
    }
    ```
    ### 2. Proof protocol
    <!-- ### 2. Proof protocol
    - __Presentation.__
    @@ -224,8 +224,9 @@ type Credential struct {
    @this nymsig: the pseudonym signature Verifier received from user.
    @input ...
    @input ... -->

    <!--
    ### 3. 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.
    @@ -256,7 +257,7 @@ 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 form, "+" means concat.
    P := t1 || t2 || g2 || _g1 || w || _g2 //join them together in bytes format
    C := hash(P) % n //C is challenge
    @@ -268,7 +269,7 @@ For `Issuer`, Prove knowledge of the private key x by creating `π <--$-- SPK{x:
    _t2 := _g1^S + _g2^((-c) % n)
    _P := _t1 + _t2 + g2 + _g1 + w + _g2
    _P := _t1 || _t2 || g2 || _g1 || w || _g2
    _C := hash(_P) % n //do the same thing like prover, everything is public
    @@ -279,7 +280,6 @@ In __Issurance Protocol__, there is also a SPK of `User's` private key __sk__ `
    In __Proof Protocol__, the SPK of User's BBS+ signature (A,e,s) is
    <!-- `π <--$-- SPK{({mi}, e, r2, r3, s'):` -->
    `π <--$-- SPK{ (e, r2, r3, s'):`
    {
    @@ -333,10 +333,143 @@ C' = Hash(A' + _A + d + t1' + t2' + g1 + h_{0~max})
    C ?= C'
    // done
    ```
    ``` -->

    ### 4. The __DAA Protocol__(Direct anonymous attestation) with Extensions __Πdaa+__

    Roles:

    - I - Issuer
    - M - TPM(Trusted Platform Module) // M and H can be substituted by one signer.
    - H - Host // M and H can be substituted by one signer.
    - V - Verifier

    Steps:

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


    #### Setup protocol

    generate Issuer's key pair.

    #### Join protocol

    see Issurance protocol


    #### Sign protocol

    Public Parameter:

    - `τ` - security parameter
    - `G1` `G2` `GT` - a bilinear group
    - `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
    - `isk` - Issuer's secret key, call it x.
    - `ipk` - Issuer's public key
    - `w` - w = g2^x
    - `_g1` - random element from G1
    - `_g2` - _g2 = _g1^x
    - `AttributeNames` - []string
    - `HAttrs` - []ECP, one attribute, one random G1 point, cprresponding to AttributeNames
    - `HSk` - ECP, cprresponding to secret key x(isk)
    - `HRand` - ECP, randomness

    Signer's information:

    - `gsk` - signer's secret key
    - `Q` - Q = h1^gsk, public key
    - `attrs = (a1,...,aL)` - one attribute, one number from Zp
    - BBS+ signature
    - `A` - A = ( g1 · h0^s · Q · MulAll(h_{i+1}^ai) )^( 1/(e+x) )
    - `e` - random from Zp
    - `s` - random from Zp
    - `b` - b = g1 · h0^s · Q · MulAll(h_{i+1}^ai), so A = b^( 1/(e+x) )
    - `(D, I)` - attribute predicate, describe what attributes will be disclosed
    - `bsn` - basename, a string to make signature different everytime

    Start to sign:

    - `nym` - nym = H1(bsn)^gsk
    - `r_gsk` - random from Zp
    - `E` - E = h1^r_gsk
    - `L` - L = H1(bsn)^r_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'):`

    {

    <!--
    In __Proof Protocol__, the ZKPoK of User's BBS+ signature (A,e,s) is
    `_A/d = A'^(-e) · h0^r2`

    &&

    `g1 · MulAll(h_{i+1}^ai_true) = d^r3 · h0^(-s') · h1^(-gsk) · MulAll(h_{i+1}^(-ai_false))`

    &&

    `nym = H1(bsn)^gsk `

    }
    - `r_ai` - for i belongs to _D(attributes not disclosed)
    - `r_e` - random from Zp
    - `r_r2` - random from Zp
    - `r_r3` - random from Zp
    - `r_s'` - random from Zp
    - `t1` - t1 = A'^r_e · h0^r_r2
    - `t2` - t2 = d^r_r3 · h0^r_s' · E^(-1) · MulAll(h_{i+1})^r_ai
    - `c'` - c' = H(A', _A, d, nym, t1, t2, L, g1, h0, ... , hL, w)
    - `n` - nonce, with τ bit length
    - `m` - message to sign
    - `SRL` - signature-based revocation list, we don't use it.
    - `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}
    - `(A', _A, d, nym, π)` - signature done.

    #### Verify ~~protocol~~ Algorithm

    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', X) ?= e(_A, g2)` - false: verify failed. true: continue.
    - `π ---> {c, s_gsk, {s_ai}, s_e, s_r2, s_r3, s_s' ,n}` - parse π
    - `~L` - ~L = h1^s_gsk · nym^(-c)
    - `~t1` - ~t1 = A'^s_e · h0^s_r2 · (_A/d)^(-c)
    - `~t2` - d^s_r3 · h0^s_s' · h1^(-s_gsk) · MulAll(h_{i+1})^(-s_ai) · (g1·MulAll(h_{i+1})^ai)^(-c)
    - the i above, first MulAll( ) belongs to _D
    - the i above, second MulAll( ) belongs to D
    - `c'` - c' = H(n, H(A', _A, d, nym, ~t1, ~t2, ~L, g1, h0,... , hL, w), m, bsn, (D, I), SRL)
    - `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'):`
  15. Doresimon revised this gist Jul 9, 2018. 1 changed file with 97 additions and 3 deletions.
    100 changes: 97 additions & 3 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -114,6 +114,19 @@ type Credential struct {

    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
    @@ -213,9 +226,9 @@ type Credential struct {
    @input ...
    ### 3. example of ZKPoK protocol
    ### 3. example of SPK protocol
    Suppose we have initialized the Issuer's key pair, now we need to generate a Non-interactive Zero knowledge proof. 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. n is order.

    ```go
    g1, g2, n //public parameters, g1, g2 are generator of G1,G2 seperately. n is order.
    @@ -231,12 +244,14 @@ x := rand{Zp} //issuer's secret key, an integer number
    }
    ```

    Prove knowledge of the private key x by creating `π <--$-- SPK{x: w = g2^x && _g2 = _g1^x}`.
    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):
    @@ -260,6 +275,85 @@ Prove knowledge of the private key x by creating `π <--$-- SPK{x: w = g2^x && _
    C ?= _C // use C to compare with _C, which was calculated just now
    ```

    In __Issurance Protocol__, there is also a SPK of `User's` private key __sk__ `π <--$-- SPK{(gsk): Q =h1^gsk}(nonce)`, π = {C, S}

    In __Proof Protocol__, the SPK of User's BBS+ signature (A,e,s) is
    <!-- `π <--$-- SPK{({mi}, e, r2, r3, s'):` -->
    `π <--$-- 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'

    // 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
    ```
    <!--
    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') * h1^(-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.

  16. Doresimon revised this gist Jul 9, 2018. 1 changed file with 17 additions and 17 deletions.
    34 changes: 17 additions & 17 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -215,47 +215,47 @@ type Credential struct {
    ### 3. example of ZKPoK protocol
    Suppose we have initialized the Issuer's key pair, now we need to generate a Non-interactive Zero knowledge proof. And the public paramaters have been decided, 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 Zero knowledge proof. 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
    x := rand{Zp} //issuer's secret key, an integer number
    { //issuer's public key, a turple with some public infomation
    w = g2^x
    _g1 =
    _g2 =
    // pC
    // pS
    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
    }
    ```

    Prove knowledge of the private key x by creating `π <--$-- SPK{x: w = g2^x && _g2 = _g1^x}`.

    1. commitment(prover):
    ```go
    r = rand{Zp}
    t1 = g2^r
    t2 = _g1^r
    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 form, "+" means concat.
    P := t1 + t2 + g2 + _g1 + w + _g2 //join them together in bytes form, "+" means concat.
    C = hash(P) % n //C is challenge
    C := hash(P) % n //C is challenge
    S = (r + C * x) % n //response to verifier
    S := (r + C * x) % n //response to verifier
    ```
    3. verify(verifier):
    ```go
    _t1 = g2^S + w^((-c) % n)
    _t1 := g2^S + w^((-c) % n)
    _t2 = _g1^S + _g2^((-c) % n)
    _t2 := _g1^S + _g2^((-c) % n)
    _P = _t1 + _t2 + g2 + _g1 + w + _g2
    _P := _t1 + _t2 + g2 + _g1 + w + _g2
    _C = hash(_P) % n //do the same thing like prover, everything is public
    _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
    ```
  17. Doresimon revised this gist Jul 9, 2018. 1 changed file with 53 additions and 8 deletions.
    61 changes: 53 additions & 8 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -60,20 +60,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
    }
    @@ -213,7 +213,52 @@ type Credential struct {
    @input ...
    ### 3. example of ZKPoK protocol
    Suppose we have initialized the Issuer's key pair, now we need to generate a Non-interactive Zero knowledge proof. And the public paramaters have been decided, 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 =
    _g2 =
    // pC
    // pS
    }
    ```

    Prove knowledge of the private key x by creating `π <--$-- SPK{x: w = g2^x && _g2 = _g1^x}`.

    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 form, "+" means concat.
    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
    ```

    ## References
    [CL02]. J. Camenisch and A. Lysyanskaya. A Signature Scheme with Efficient Protocols. SCN 2002.
  18. Doresimon revised this gist Jul 5, 2018. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -124,15 +124,15 @@ type Credential struct {
    // nonce - a fresh nonce used for the signature
    // nym - a fresh pseudonym (a commitment to to the user secret)
    type Signature struct {
    APrime *ECP
    ABar *ECP
    BPrime *ECP
    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
    ProofSSPrime []byte // s' = s - r2 * r3
    ProofSAttrs [][]byte
    Nonce []byte
    Nym *ECP
  19. Doresimon revised this gist Jul 5, 2018. 1 changed file with 109 additions and 0 deletions.
    109 changes: 109 additions & 0 deletions anon_cred.md
    View file
    Original file line number Diff line number Diff line change
    @@ -106,6 +106,115 @@ type Credential struct {
    ```
    ### 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).

    - __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
    ABar *ECP
    BPrime *ECP
    ProofC []byte
    ProofSSk []byte
    ProofSE []byte
    ProofSR2 []byte
    ProofSR3 []byte
    ProofSSPrime []byte
    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 Issurance 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 ...
    ## References
    [CL02]. J. Camenisch and A. Lysyanskaya. A Signature Scheme with Efficient Protocols. SCN 2002.
  20. @kunxian-xia 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
  21. @kunxian-xia 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
  22. @kunxian-xia 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

  23. @kunxian-xia 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
  24. @kunxian-xia 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
  25. @kunxian-xia 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

  26. @kunxian-xia 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

  27. @kunxian-xia 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.

  28. @kunxian-xia 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.
  29. @kunxian-xia 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.
  30. @kunxian-xia 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.