bbs

Short group signatures by Boneh, Boyen, and Shachum and later improved in ASM as BBS+ and touched on again in section 4.3 in CDL.

This crate implements the BBS+ signature scheme which allows for signing many committed messages.

BBS+ signatures can be created in typical cryptographic fashion where the signer and signature holder are the same party or where they are two distinct parties. BBS+ signatures can also be used to generate signature proofs of knowledge and selective disclosure zero-knowledge proofs. To start, all that is needed is to add this to your Cargo.toml.

[dependencies]
bbs = "0.4"

Add in the main section of code to get all the traits, structs, and functions needed.

use bbs::prelude::*;

Keygen

BBS+ supports two types of public keys. One that is created as described in the paper where the message specific generators are randomly generated and a deterministic version that looks like a BLS public key and whose message specific generators are computed using IETF's Hash to Curve algorithm which is also constant time combined with known inputs.

generate(message_count: usize) - returns a keypair used for creating BBS+ signatures

PublicKey - w ⟵ 𝔾₂, h₀, (h₁, ... , h_L) ⟵ 𝔾₁^L

DeterministicPublicKey - w ⟵ 𝔾₂. This can be converted to a public key by calling the to_public_key method.

There is a convenience class Issuer that can be used for this as well.

let (pk, sk) = Issuer::new_keys(5).unwrap();

or

let (dpk, sk) = Issuer::new_short_keys(None);
let pk = dpk.to_public_key(5).unwrap();

Signing

Signing can be done where the signer knows all the messages or where the signature recipient commits to some messages beforehand and the signer completes the signature with the remaining messages.

To create a signature:

let (pk, sk) = Issuer::new_keys(5).unwrap();
let messages = vec![
    SignatureMessage::hash(b"message 1"),
    SignatureMessage::hash(b"message 2"),
    SignatureMessage::hash(b"message 3"),
    SignatureMessage::hash(b"message 4"),
    SignatureMessage::hash(b"message 5"),
];

let signature = Signature::new(messages.as_slice(), &sk, &pk).unwrap();

assert!(signature.verify(messages.as_slice(), &pk).unwrap());

or

// Generated by the issuer
let (pk, sk) = Issuer::new_keys(5).unwrap();

// Done by the signature recipient

let message = SignatureMessage::hash(b"message_0");

let signature_blinding = Signature::generate_blinding();

let commitment = &pk.h[0] * &message + &pk.h0 * &signature_blinding;

// Completed by the signer
// `commitment` is received from the recipient
let messages = sm_map![
    1 => b"message_1",
    2 => b"message_2",
    3 => b"message_3",
    4 => b"message_4"
];

let blind_signature = BlindSignature::new(&commitment, &messages, &sk, &pk).unwrap();

// Completed by the recipient
// receives `blind_signature` from signer
// Recipient knows all `messages` that are signed

let signature = blind_signature.to_unblinded(&signature_blinding);

let mut msgs = messages
    .iter()
    .map(|(_, m)| m.clone())
    .collect::<Vec<SignatureMessage>>();
msgs.insert(0, message.clone());

let res = signature.verify(msgs.as_slice(), &pk);
assert!(res.is_ok());
assert!(res.unwrap());

This by itself is considered insecure without the signer completing a proof of knowledge of committed messages generated by the recipient and sent with the commitment. It is IMPORTANT that the signature issuer complete this step. For simplicity, the Issuer and Prover structs can be used as follows to handle this.

let (pk, sk) = Issuer::new_keys(5).unwrap();
let signing_nonce = Issuer::generate_signing_nonce();

// Send `signing_nonce` to holder

// Recipient wants to hide a message in each signature to be able to link
// them together
let link_secret = Prover::new_link_secret();
let mut messages = BTreeMap::new();
messages.insert(0, link_secret.clone());
let (ctx, signature_blinding) =
    Prover::new_blind_signature_context(&pk, &messages, &signing_nonce).unwrap();

// Send `ctx` to signer
let messages = sm_map![
    1 => b"message_1",
    2 => b"message_2",
    3 => b"message_3",
    4 => b"message_4"
];

// Will fail if `ctx` is invalid
let blind_signature = Issuer::blind_sign(&ctx, &messages, &sk, &pk, &signing_nonce).unwrap();

// Send `blind_signature` to recipient
// Recipient knows all `messages` that are signed
let mut msgs = messages
    .iter()
    .map(|(_, m)| m.clone())
    .collect::<Vec<SignatureMessage>>();
msgs.insert(0, link_secret.clone());

let res =
    Prover::complete_signature(&pk, msgs.as_slice(), &blind_signature, &signature_blinding);
assert!(res.is_ok());

Proofs

Verifiers ask a Prover to reveal some number of signed messages (from zero to all of them), while and the remaining messages are hidden. If the Prover agrees, she completes a signature proof of knowledge and proof of committed values. These messages could be combined in other zero-knowledge proofs like zkSNARKs or Bulletproofs like bound checks or set memberships. If this is the case, the hidden messages will need to linked to the other proofs using a common blinding factor. This crate provides three message classifications for proofs to accommodate this flexibility.

• ProofMessage::Revealed: message will become known to the verifier. Caveat: cryptography operates on integers and not directly on strings. Usually the hash of the string is signed. The verifier will learn the revealed hash and not the message content. The prover must send the preimage so the verifier can check if the hashes are equal after verifying the signature.
• ProofMessage::Hidden: message is not shown to the verifier. There are two kinds of hidden messages.
  • HiddenMessage::ProofSpecificBlinding: message is hidden and not used in any other proof, the blinding is specific to this signature only.
  • HiddenMessage::ExternalBlinding: message is hidden but is also used in another proof. For example, to show two messages are the same across two signature or 'linked', the same blinding factor must be used for both proofs. This kind groups the blinding factor and the message.

To begin a zero-knowledge proof exchange, the verifier indicates which messages to be revealed and provides a nonce limit the prover's ability to cheat i.e. create a valid proof without knowing the actual messages or signature.

The Verifier must trust the signer of the credential and know the message structure i.e. what message is at index 1, 2, 3, ... etc.

let (pk, sk) = Issuer::new_keys(5).unwrap();
let messages = vec![
    SignatureMessage::hash(b"message_1"),
    SignatureMessage::hash(b"message_2"),
    SignatureMessage::hash(b"message_3"),
    SignatureMessage::hash(b"message_4"),
    SignatureMessage::hash(b"message_5"),
];

let signature = Signature::new(messages.as_slice(), &sk, &pk).unwrap();

let nonce = Verifier::generate_proof_nonce();
let proof_request = Verifier::new_proof_request(&[1, 3], &pk).unwrap();

// Sends `proof_request` and `nonce` to the prover
let proof_messages = vec![
    pm_hidden!(b"message_1"),
    pm_revealed!(b"message_2"),
    pm_hidden!(b"message_3"),
    pm_revealed!(b"message_4"),
    pm_hidden!(b"message_5"),
];

let pok = Prover::commit_signature_pok(&proof_request, proof_messages.as_slice(), &signature)
    .unwrap();

// complete other zkps as desired and compute `challenge_hash`
// add bytes from other proofs

let mut challenge_bytes = Vec::new();
challenge_bytes.extend_from_slice(pok.to_bytes().as_slice());
challenge_bytes.extend_from_slice(nonce.to_bytes().as_slice());

let challenge = ProofNonce::hash(&challenge_bytes);

let proof = Prover::generate_signature_pok(pok, &challenge).unwrap();

// Send `proof` and `challenge` to Verifier

match Verifier::verify_signature_pok(&proof_request, &proof, &nonce) {
    Ok(_) => assert!(true),   // check revealed messages
    Err(_) => assert!(false), // Why did the proof failed
};