anon_cred.md

BBS signature

Setup: generate a pairing-friendly curve G, and target group Gt, pairing func e: G x G -> Gt.
KeyGen: sk = (x), pk = (g^x).
Sign(m): sig = g^{1/(x+mprime)}, where mprime = H(m).
Verify(m, sig): check if e(pk * g^{H(m)}, g^sig) == e(g, g).

BBS+ signature

Setup: group G1, G2, Gt. pairing function e: G1 x G2 -> Gt.

common params:
- g0, g1, (g2, ..., g_{L+1}) are elements from G1.
- h0 is a generator of G2.
KeyGen: sample x from uniform dist on Zp, output sk = x, pk = h0^x.
Sign(sk, m1, ..., mL): choose two random numbers e and s from Zp. Compute B = g0 * g1^s * (g2^m1 ... * g_{L+1}^mL), then let A = B^{1/(e+x)}. The sig is (A, e, s).
Verify(pk, m1, ..., mL, sig): decode sig as (A, e, s), and check if pairing(A, h0^e * pk) == pairing(B, h0).

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:

The issuer sends a random nonce to the user.
The user creates a Credential Request using the public key of the issuer, user secret, and the nonce as input The request consists of a commitment to the user secret (can be seen as a public key) and a zero-knowledge proof of knowledge of the user secret key The user sends the credential request to the issuer
The issuer verifies the credential request by verifying the zero-knowledge proof If the request is valid, the issuer issues a credential to the user by signing the commitment to the secret key together with the attribute values and sends the credential back to the user
The user verifies the issuer's signature and stores the credential that consists of the signature value, a randomness used to create the signature, the user secret, and the attribute values

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

   Issuer  --------------------  Prover 
    
        -- nonce(BigNum)--> 
        
        <-- CredRequest --
        
        --- Credential --->

CredRequest contains a commitment Nym to user's master secret which is of the form g1^(ms) * g2^(credS) and a zk-PoK of Nym.
Credential contains the BBS+ signature on attributes and Nym.

type IssuerSecretKey BigNum

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
}

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   
}

type Credential struct {
   A               ECPoint 
   B               ECPoint
   e               BigNum 
   s               BigNum
   Attrs           [][]byte
   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).

Detail

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

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

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