BBS+ Signature Scheme | June 2020 | |
Lodder & Looker | Informational | [Page] |
BBS+ is a short group digital signature that allows a set of messages to be signed with a single key. The scheme permits a signer and signature holder to be two separate parties. The holder creates a Pedersen commitment which is combined with other messages by the signer to complete a blind signature which can be un-blinded by the holder. Lastly, BBS+ also supports an efficient Zero-Knowledge Signature Proof of Knowledge construction where a holder can selectively disclose any subset of signed messages to another party without revealing the signature or the hidden messages.¶
A signature scheme is a fundamental cryptographic primitive that is used to protect authenticity and integrity of communication. Only the holder of a secret key can sign messages, but anyone can verify the signature using the associated public key.¶
Signature schemes are used in point-to-point secure communication protocols, PKI, remote connections, etc. Designing efficient and secure digital signature is very important for these applications.¶
This document describes the BBS+ signature scheme. The scheme features many important properties:¶
The signature is over a group of Pedersen commitments--signatures can be created blinded or un-blinded.¶
The signature is encoded as a single group element and two field elements.¶
Verification requires 2 pairing operations.¶
Simple signature schemes require the entire signature and message be disclosed during verification. BBS+ allows a fast and small zero-knowledge signature proof of knowledge to be created from the signature and the public key. This allows the signature holder to selectively reveal any number of signed messages to another entity (none, all, or any number in between).¶
These properties allow the scheme to be used in applications where privacy and data minimization techniques are desired and/or required.¶
A recent emerging use case applies signature schemes in verifiable credentials. One problem with using simple signature schemes like ECSDA or ED25519 is a holder must disclose the entire signed message and signature for verification. Circuit based logic can be applied to verify these in zero-knowledge like SNARKS or Bulletproofs with R1CS but tend to be complicated. BBS+ on the other hand adds, to verifiable credentials or any other application, the ability to do very efficient zero-knowledge proofs. A holder gains the ability to choose which claims to reveal to a relying party without the need for any additional complicated logic.¶
The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear in this document, are to be interpreted as described in [RFC2119].¶
The following terminology is used throughout this document:¶
The secret key for the signature scheme¶
The public key for the signature scheme containing all information needed to perform cryptographic operations.¶
The short form of the public key or deterministic public key.¶
The set of messages that are blinded from the signer during a blind signing.¶
The set of messages that are known to the signer during a blind signing.¶
The total number of messages that the signature scheme can sign.¶
The set of message indices that are retained or hidden in a signature proof of knowledge.¶
The set of message indices that are disclosed in a signature proof of knowledge.¶
The input to be signed by the signature scheme.¶
The generator corresponding to a given msg.¶
A generator for the blinding value in the signature.¶
The digital signature output.¶
The signature blinding factor held by the signature recipient.¶
The blind digital signature output.¶
A pedersen commitment composed of 1 or more messages.¶
A cryptographic nonce¶
Zero-Knowledge Signature Proof of Knowledge.¶
A non-interactive zero-knowledge proof from fiat-shamir heuristic.¶
The domain separation tag, the ASCII string "BLS12381G1_XMD:BLAKE2B_SSWU_RO_BBS+_SIGNATURES:1_0_0" comprising 52 octets.¶
Denotes the concatenation of octet strings a and b.¶
Terms specific to pairing-friendly elliptic curves that are relevant to this document are restated below, originally defined in [I-D.irtf-cfrg-pairing-friendly-curves]¶
elliptic curve groups defined over finite fields. This document assumes that E1 has a more compact representation than E2, i.e., because E1 is defined over a smaller field than E2.¶
subgroups of E1 and E2 (respectively) having prime order r.¶
a subgroup, of prime order r, of the multiplicative group of a field extension.¶
G1 x G2 -> GT: a non-degenerate bilinear map.¶
points on G1 and G2 respectively. For a pairing-friendly curve, this document denotes operations in E1 and E2 in additive notation, i.e., P + Q denotes point addition and x * P denotes scalar multiplication. Operations in GT are written in multiplicative notation, i.e., a * b is field multiplication.¶
The cryptographic hash function that takes as an arbitrary octet string input and returns a point in G1 as defined in [I-D.irtf-cfrg-hash-to-curve]. The algorithm is BLS12381G1_XMD:BLAKE2B_SSWU_RO, i.e use Blake2b-512 as part of expand message digest, apply the isogeny simplified SWU map to compute a point in G1 using the random oracle method. The domain separation tag value is dst.¶
The cryptographic hash function that takes as an arbitrary octet string input and returns a point in G1 as defined in [I-D.irtf-cfrg-hash-to-curve]. The algorithm is BLS12381G2_XMD:BLAKE2B_SSWU_RO, i.e use Blake2b-512 as part of expand message digest, apply the isogeny simplified SWU map to compute a point in G2 using the random oracle method. The domain separation tag value is dst.¶
returns the canonical representation of the point P as an octet string in compressed form. This operation is also known as serialization.¶
returns the canonical representation of the point P as an octet string in uncompressed form. This operation is also known as serialization.¶
returns the point P corresponding to the canonical representation ostr, or INVALID if ostr is not a valid output of point_to_octets. This operation is also known as deserialization. Consumes either compressed or uncompressed ostr.¶
returns VALID when the point P is an element of the subgroup of order r, and INVALID otherwise. This function can always be implemented by checking that r * P is equal to the identity element. In some cases, faster checks may also exist, e.g., [Bowe19].¶
//TODO¶
This document is organized as follows:¶
The remainder of this section defines terminology and the high-level API.¶
Section 2 defines primitive operations used in the BLS signature scheme. These operations MUST NOT be used alone.¶
Section 3 defines security considerations.¶
Section 4 defines the references.¶
Section 5 defines test vectors.¶
The following comparison assumes BBS+ signatures with curve BLS12-381, targeting 128 bit security.¶
For 128 bits security, ECDSA with curve P-256 takes 37 and 79 micro-seconds to sign and verify signature on a modern computer. BBS+ 680 and 1400 milliseconds to sign and verify a single message. However, ECDSA can only sign a single message whereas BBS+ can sign any number of messages at the expense of a bigger public key. To sign and verify 10 messages takes 3.7 and 5.4 milliseconds, and 22.3 and 24.4 milliseconds for 100 messages.¶
The signature size remains constant regardless of the number of signed messages. ECDSA and ED25519 use 32 bytes for public keys and 64 bytes for signatures. In contrast, BBS+ public key sizes follow the formula 48 * (messages + 1) + 96, and 112 bytes for signatures. However, A single BBS+ signature is sufficient to authenticate multiple messages. We also present a method that only needs 96 bytes for the public key at the expense of a some computation before performing operations like signing, proof generation, and verification.¶
This section defines core operations used by the schemes defined in Section 3. These operations MUST NOT be used except as described in that section.¶
The core operations in this section depend on several parameters:¶
A pairing-friendly elliptic curve, plus associated functionality given in Section 1.4.¶
H, a hash function that MUST be a secure cryptographic hash function, e.g. Blake2b-512. For security, H MUST output at least ceil(log2(r)) bits, where r is the order of the subgroups G1 and G2 defined by the pairing-friendly elliptic curve.¶
PRF(n): a pseudo-random function similar to [RFC4868]. Returns n pseudo randomly generated bytes.¶
The KeyGen algorithm generates a secret key SK deterministically from a secret octet string IKM.¶
KeyGen uses HKDF [RFC5869] instantiated with the hash function H.¶
For security, IKM MUST be infeasible to guess, e.g., generated by a trusted source of randomness. IKM MUST be at least 32 bytes long, but it MAY be longer.¶
Because KeyGen is deterministic, implementations MAY choose either to store the resulting SK or to store IKM and call KeyGen to derive SK when necessary.¶
KeyGen takes an optional parameter, key_info. This parameter MAY be used to derive multiple independent keys from the same IKM. By default, key_info is the empty string.¶
SK = KeyGen(IKM)¶
Inputs: - IKM, a secret octet string. See requirements above.¶
Outputs: - SK, a uniformly random integer such that 0 < SK < r.¶
Parameters: - key_info, an optional octect string. if this is not supplied, it MUST default to an empty string.¶
Definitions: - HKDF-Extract is as defined in [RFC5869], instantiated with hash H. - HKDF-Expand is as defined in [RFC5869], instantiated with hash H. - I2OSP and OS2IP are as defined in [RFC8017], Section 4. - L is the integer given by ceil((3 * ceil(log2(r))) / 16). - "BBS-SIG-KEYGEN-SALT-" is an ASCII string comprising 20 octets.¶
Procedure:¶
SkToDpk algorithm takes a secret key SK and outputs a corresponding short formed public key.¶
SK MUST be indistinguishable from uniformly random modulo r (Section 2.2) and infeasible to guess, e.g., generated using a trusted source of randomness. KeyGen (Section 2.3) outputs SK meeting these requirements. Other key generation approaches meeting these requirements MAY also be used; details of such methods are beyond the scope of this document.¶
DPK = SkToDpk(SK)¶
Inputs: - SK, a secret integer such that 0 <= SK <= r¶
Outputs: - DPK, a public key encoded as an octet string¶
Procedure:¶
The SkToPk algorithm takes a secret key SK and the number of messages that can be signed and outputs the corresponding public key PK.¶
SK MUST be indistinguishable from uniformly random modulo r (Section 2.2) and infeasible to guess, e.g., generated using a trusted source of randomness. KeyGen (Section 2.3) outputs SK meeting these requirements. Other key generation approaches meeting these requirements MAY also be used; details of such methods are beyond the scope of this document.¶
PK = SkToPk(Sk, count)¶
Inputs: - SK, a secret integer such that 0 <= SK <= r - count, an integer¶
Outputs: - PK, a public key encoded as an octet string¶
Procedure:¶
DpkToPk converts the short form of the public key to the long form just like SkToPk.¶
PK = DpkToPk(DPK, count)¶
Inputs: - DPK, the short form of the public key - count, an integer¶
Outputs: - PK, a public key encoded as an octet string¶
Procedure:¶
KeyValidate checks if the public key is valid.¶
As an optimization, implementations MAY cache the result of KeyValidate in order to avoid unnecessarily repeating validation for known keys.¶
result = KeyValidate(PK)¶
Inputs: - PK, a public key in the format output by SkToPk.¶
Outputs: - result, either VALID or INVALID¶
Procedure:¶
Sign computes a signature from SK, PK, over a vector of messages.¶
signature = Sign((msg\_i,...,msg\_n), SK, PK)¶
Inputs: - msg_i,...,msg_n, octet strings - SK, a secret key output from KeyGen - PK, a public key output from either DpkToPk or SkToPk¶
Outputs: - signature, an octet string¶
Procedure:¶
Verify checks that a signature is valid for the octet string messages under the public key.¶
result = Verify((msg\_i,...,msg\_n), signature, PK)¶
Inputs: - msg_i,...,msg_n, octet strings. - signature, octet string. - PK, a public key in the format output by SkToPk.¶
Outputs: - result, either VALID or INVALId.¶
Procedure:¶
The PreBlindSign algorithm allows a holder of a signature to blind messages that when signed, are unknown to the signer.¶
The algorithm takes generates a blinding factor that is used to un-blind the signature from the signer, and a pedersen commitment from the generators in the signers public key PK and a vector of messages.¶
(s', commitment) = PreBlindSign((msg\_i,...,msg\_U),h0, (h\_i,...,h\_U))¶
Inputs: - msg_i,...,msg_U, octet strings of the messages to be blinded. - h0, octet string. - h_i,...,h_U, octet strings of generators for the messages to be blinded.¶
Outputs: - s', octet string. - commitment, octet string¶
Procedure:¶
BlindSign generates a blind signature from a commitment received from a holder, known messages, a secret key, and generators from the corresponding public key.¶
blind\_signature = BlindSign(commitment, (msg\_i,...msg\_K), SK, h0, (h\_i,...,h\_K))¶
Inputs: - commitment, octet string receive from the holder in output form from PreBlindSign - msg_i,...,msg_K, octet strings - SK, a secret key output from KeyGen - h0, octet string. - h_i,...,h_K, octet strings of generators for the known messages¶
Outputs: - blind_signature, octet string¶
Procedure:¶
UnblindSign computes the unblinded signature given a blind signature and the holder's blinding factor. It is advised to verify the signature after un-blinding.¶
signature = UnblindSign(blind\_signature, s')¶
Inputs: - s', octet string in output form from PreBlindSign - blind_signature, octet string in output form from BlindSign¶
Outputs: - signature, octet string¶
Procedure:¶
BlindMessagesProofGen creates a proof of committed messages zero-knowledge proof. The proof should be verified before a signer computes a blind signature. The proof is created from a nonce given to the holder from the signer, a vector of messages, a blinding factor output from PreBlindSign, and generators from the signers public key.¶
nizk = BlindMessagesProofGen(commitment, s', (msg\_i,...,msg\_U), h0, (h\_i,...,h\_U), nonce)¶
Inputs: - commitment, octet string as output from PreBlindSign - s', octet string as output from PreBlindSign - msg_i,...,msg_U, octet strings of the messages to be blinded. - h0, octet string. - h_i,...,h_U, octet strings of generators for the messages to be blinded. - nonce, octet string.¶
Outputs: - nizk, octet string¶
Procedure:¶
BlindMessagesProofVerify checks whether a proof of committed messages zero-knowledge proof is valid.¶
result = BlindMessagesProofVerify(commitment, nizk, nonce)¶
Inputs: - commitment, octet string in output form from PreBlindSign - nizk, octet string in output form from BlindMessagesProofGen - nonce, octet string¶
Outputs: - result, either VALID or INVALID.¶
Procedure:¶
A signature proof of knowledge generating algorithm that creates a zero-knowledge proof of knowledge of a signature while selectively disclosing messages from a signature, a vector of messages, vector of indices, the signer's public key, and a nonce.¶
spk = SpkGen(PK, (msg\_i,...,msg\_L), (i,...,R), signature, nonce)¶
Inputs: - PK, octet string in output form from SkToPk, DpkToPk - msg_i,...,msg_L, octet strings - i,...,R, integers - signature, octet string in output form from Sign - nonce, octet string¶
Outputs: - spk, octet string¶
Procedure:¶
(A, e, s) = signature¶
if subgroup_check(A) is INVALID abort¶
if KeyValidate(PK) is INVALID abort¶
b = commitment + h0 * s + h_i * msg_i + ... + h_L * msg_L¶
r1 = H(PRF(8*ceil(log2(r)))) mod r¶
r2 = H(PRF(8*ceil(log2(r)))) mod r¶
e~ = H(PRF(8*ceil(log2(r)))) mod r¶
r2~ = H(PRF(8*ceil(log2(r)))) mod r¶
r3~ = H(PRF(8*ceil(log2(r)))) mod r¶
s~ = H(PRF(8*ceil(log2(r)))) mod r¶
r3 = r1 ^ -1 mod r¶
m~ = [ R]¶
for i in 0 to R: m~[i] = H(PRF(8*ceil(log2(r)))) mod r¶
A' = A * r1¶
Abar = A' * -e + b * r1¶
d = b * r1 + h0 * -r2¶
s' = s - r2 * r3¶
C1 = A' * e~ + h0 * r2~¶
C2 = d * r3~ + h0 * s~ + h_i * m~_i + ... + h_R * m_{_R}¶
c = H(Abar || A' || h0 || C1 || d || h0 || h_i || ... || h_R || C2 || nonce)¶
e^ = e~ + c * e¶
r2^ = r2~ - c * r2¶
r3^ = r3~ + c * r3¶
s^ = s~ - c * s'¶
m^_i = m~_i - c m_i¶
spk = (A', Abar, d, C1, e^, r2^, C2, r3^, s^, (m^{_i,...,m}¶
return spk¶
SpkVerify checks if a signature proof of knowledge is VALID given the signer's public key, a vector of revealed messages, the proof, and the nonce used in SpkGen.¶
result = SpkVerify(spk, PK, (msg\_i,...,msg\_D), nonce)¶
Inputs: - spk, octet string. - PK, octet string in output form from SkToPk, DpkToPk. - msg_i,...,msg_D, octet strings. - nonce, octet string.¶
Outputs: - result, either VALID or INVALID.¶
Procedure:¶
if KeyValidate(PK) is INVALID¶
(A', Abar, d, C1, e^, r2^, C2, r3^, s^, (m^{_i,...,m}¶
(w, h0, h_i,...,h_L) = PK¶
if A' == 1 return INVALID¶
X1 = e(A', w)¶
X2 = e(Abar, P2)¶
if X1 != X2 return INVALID¶
c = H(Abar || A' || h0 || C1 || d || h0 || h_i || ... || h_R || C2 || nonce)¶
T1 = Abar - d¶
T2 = P1 + h_i * -m^_i + ... + h_D * -m^{_D}¶
Y1 = A' * e^ + h0 * r2^ + T1 * c¶
Y2 = d * r3^ + h0 * s^ + h_i * m^_i + ... + h_R * m^_R + T2 * c¶
if C1 != Y1 return INVALID¶
if C2 != Y2 return INVALID¶
return VALID¶
All algorithms in Section 2 that operate on points in public keys require first validating those keys. For the sign, verify and proof schemes, the use of KeyValidate is REQUIRED.¶
Some existing implementations skip the subgroup_check invocation in Verify (Section 2.8), whose purpose is ensuring that the signature is an element of a prime-order subgroup. This check is REQUIRED of conforming implementations, for two reasons.¶
For most pairing-friendly elliptic curves used in practice, the pairing operation e (Section 1.3) is undefined when its input points are not in the prime-order subgroups of E1 and E2. The resulting behavior is unpredictable, and may enable forgeries.¶
Even if the pairing operation behaves properly on inputs that are outside the correct subgroups, skipping the subgroup check breaks the strong unforgeability property [ADR02].¶
Implementations of the signing algorithm SHOULD protect the secret key from side-channel attacks. One method for protecting against certain side-channel attacks is ensuring that the implementation executes exactly the same sequence of instructions and performs exactly the same memory accesses, for any value of the secret key. In other words, implementations on the underlying pairing-friendly elliptic curve SHOULD run in constant time.¶
As discussed in Section 2.2, the IKM input to KeyGen MUST be infeasible to guess and MUST be kept secret. One possibility is to generate IKM from a trusted source of randomness. Guidelines on constructing such a source are outside the scope of this document.¶
Secret keys MAY be generated using other methods; in this case they MUST be infeasible to guess and MUST be indistinguishable from uniformly random modulo r.¶
BBS+ signatures are nondeterministic, meaning care must be taken against attacks arising from signing with bad randomness, for example, the nonce reuse attack on ECDSA [HDWH12]. It is recommended that the nonces used in signature proof generation are from a trusted source of randomness.¶
BlindSign as discussed in 2.10 uses randomness from two parties so care MUST be taken that both sources of randomness are trusted. If one party uses weak randomness, it could compromise the signature.¶
When a trusted source of randomness is used, signatures and proofs are much harder to forge or break due to the use of multiple nonces.¶
The security analysis models hash_to_point and hash_pubkey_to_point as random oracles. It is crucial that these functions are implemented using a cryptographically secure hash function. For this purpose, implementations MUST meet the requirements of [I-D.irtf-cfrg-hash-to-curve].¶
In addition, ciphersuites MUST specify unique domain separation tags for hash_to_point. The domain separation tag used in Section 1.4 is the RECOMMENDED one.¶
Contexts can be used to separate uses of the protocol between different protocols (which is very hard to reliably do otherwise) and between different uses within the same protocol. However, the following SHOULD be kept in mind:¶
The context SHOULD be a constant string specified by the protocol using it. It SHOULD NOT incorporate variable elements from the message itself.¶
Contexts SHOULD NOT be used opportunistically, as that kind of use is very error prone. If contexts are used, one SHOULD require all signature schemes available for use in that purpose support contexts.¶
Contexts are an extra input, which percolate out of APIs; as such, even if the signature scheme supports contexts, those may not be available for use. This problem is compounded by the fact that many times the application is not invoking the signing, verification, and proof functions directly but via some other protocol.¶
The ZKP protocols use nonces which MUST be different in each context.¶
BBS+ signatures can be implemented on any pairing-friendly curve. Using BLS12-381 the signature achieves close to 128-bit security, and is the recommended curve at this time.¶
This document does not make any requests of IANA.¶
BLS12-381¶
The cipher-suites in Section 4 are based upon the BLS12-381 pairing-friendly elliptic curve. The following defines the correspondence between the primitives in Section 1.3 and the parameters given in Section 4.2.2 of [I-D.irtf-cfrg-pairing-friendly-curves].¶
E1, G1: the curve E and its order-r subgroup.¶
E2, G2: the curve E' and its order-r subgroup.¶
GT: the subgroup G_T.¶
P1: the point BP.¶
P2: the point BP'.¶
e: the optimal Ate pairing defined in Appendix A of [I-D.irtf-cfrg-pairing-friendly-curves].¶
pointtooctets and octetstopoint use the compressed serialization formats for E1 and E2 defined by [ZCash].¶
subgroup_check MAY use either the naive check described in Section 1.3 or the optimized check given by [Bowe19].¶
//TODO¶