Crate bbs_plus

source ·
Expand description

Implements BBS and BBS+ signatures.

BBS+ signature according to the paper: Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited. Provides

  • signature creation and verification with signature in group G1 and public key in group G2 and vice-versa.
  • proof of knowledge of signature and corresponding messages in group G1 as that is more efficient.

BBS signature according to the paper: Revisiting BBS Signatures. Provides

  • signature creation and verification with signature in group G1 and public key in group G2.
  • proof of knowledge of signature and corresponding messages. The implemented protocols are a bit different from whats mentioned in the paper. The modifications are made in the Schnorr proof part to allow for use-cases like proving equality (in zero-knowledge) of messages among same/different signatures or proving predicates (in zero-knowledge) about messages. Check the documentation of corresponding modules for more details.

Threshold BBS and BBS+ signatures based on the paper Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance The threshold signing protocol has 3 phases (not communication rounds) 1. This is the randomness generation phase 2. This is the phase where multiplications happen 3. Here the outputs of phases 1 and 2 and the messages to be signed are used to generate the signature. This phase is non-interactive from signers’ point of view as they don’t just interact among themselves

Note that only 3rd phase requires the messages to be known so the first 2 phases can be treated as pre-computation and can be done proactively and thus only phase 1 and 2 are online phases of the MPC protocol and phase 3 is the offline phase. Secondly since the communication time among signers is most likely to be the bottleneck in threshold signing, phase 1 and 2 support batching meaning that to generate n signatures only a single execution of phase 1 and 2 needs to done, although with larger inputs. Then n executions of phase 3 are done to generate the signature. Also, its assumed that parties have done the DKG as well as the base OT and stored their results before starting phase 1. Both BBS and BBS+ implementations share the same multiplication phase and the base OT phase but their phase 1 is slightly less expensive as BBS+ needs 2 random fields elements but BBS needs only 1.

§Modules

  1. BBS and BBS+ signature parameters and key generation module - setup. The signature params for BBS are slightly different from BBS+ but public key is same.
  2. BBS+ signature module - signature
  3. BBS+ proof of knowledge of signature module - proof
  4. BBS signature module - signature_23
  5. BBS proof of knowledge of signature module - proof_23
  6. BBS proof of knowledge of signature module, implementation as in appendix B - proof_23_cdl
  7. BBS proof of knowledge of signature module, implementation as in appendix A - proof_23_ietf
  8. Threshold BBS and BBS+ signatures - threshold

The implementation tries to use the same variable names as the paper and thus violate Rust’s naming conventions at places.

Modules§

  • Proof of knowledge of BBS+ signature and corresponding messages as per section 4.5 of the BBS+ paper
  • Proof of knowledge of BBS signature and corresponding messages as per section 5.2 of the BBS paper with slight modification described below. The paper requires the prover to prove e(A_bar, X_2) = e (B_bar, g2) where B_bar = C(m)*r + A_bar*-e. The prover sends A_bar, B_bar to the verifier and also proves the knowledge of r, e and any messages in C(m) in B_bar. Here r is a random element chosen by the prover on each proof of knowledge. Above approach has a problem when some messages under 2 signatures need to be proven equal in zero knowledge. Because r will be different for each signature, the witnesses for the Schnorr proof will be different, i.e. m*r and m*r' for the same message m and thus the folklore method of proving equal witnesses in multiple statements cant be used. Thus the protocol below accepts r (called signature randomizer) from the prover who can use the same r when proving message equality in multiple signatures. When doing so also prove the equality of r in term C_j(m) * r and thus use the same blinding eg. when proving equality of certain messages under 2 signatures sigma_1 = (A_1, e_1) and sigma_2 = A_2 * e_2, it should be proven that r and Schnorr responses for the equal messages m_k are equal. i.e. for known messages J_1, J_2, hidden messages I_1, I_2 for signatures sigma_1, sigma_2 with equal messages m_k being a subset of I_1, I_2, r and m_k are same in following 2 relations:
  • Proof of knowledge of BBS signature and corresponding messages as per Appendix B of the BBS paper with slight modification described below. In section 5.2, the paper requires the prover to prove e(A_bar, X_2) = e (B_bar, g2) where A_bar = A * r and B_bar = C(m)*r + A_bar*-e. The prover sends A_bar, B_bar to the verifier and also proves the knowledge of r, e and any messages in C(m) in B_bar. Here r is a random element chosen by the prover on each proof of knowledge. Above approach has a problem when some messages under 2 signatures need to be proven equal in zero knowledge or proving predicates about the messages in zero-knowledge using LegoSnark where the proof contains a Pedersen commitment to witness of the SNARK. Because r will be different for each signature, the witnesses for the Schnorr proof will be different, i.e. m*r and m*r' for the same message m and thus the folklore method of proving equal witnesses in multiple statements cant be used. Thus the protocol below uses a similar approach as used in BBS+. The prover in addition to sending A_bar = A*r1*r2, B_bar = (C(m) - A*e)*r1*r2 to the verifier sends d = C(m)*r2 as well for random r1, r2. The prover calculates r3 = 1 / r2 and creates 2 Schnorr proofs for:
  • Proof of knowledge of BBS signature and corresponding messages using the protocol described in Appendix A of the paper. This protocol is used by the BBS IETF draft in sections 3.6.3, 3.6.4, 3.7. The difference with the IETF draft is that this does not assume the mandatory message called “signature domain”. The protocol works as follows
  • Keys and setup parameters
  • BBS+ signature and verification as per section 4.3 of the paper
  • BBS signature and verification. Signature is in group G1.
  • Implementation of threshold BBS and BBS+ based on the paper Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance The threshold signing protocol has 3 phases (not communication rounds) 1. This is the randomness generation phase 2. This is the phase where multiplications happen 3. Here the outputs of phases 1 and 2 and the messages to be signed are used to generate the signature. This phase is non-interactive from signers’ point of view as they don’t just interact among themselves