Internet-Draft The BBS Signature Scheme March 2023
Looker, et al. Expires 12 September 2023 [Page]
Workgroup:
CFRG
Internet-Draft:
draft-irtf-cfrg-bbs-signatures-latest
Published:
Intended Status:
Informational
Expires:
Authors:
T. Looker
MATTR
V. Kalos
MATTR
A. Whitehead
Portage
M. Lodder
CryptID

The BBS Signature Scheme

Abstract

BBS is a digital signature scheme categorized as a form of short group signature that supports several unique properties. Notably, the scheme supports signing multiple messages whilst producing a single output digital signature. Through this capability, the possessor of a signature is able to generate proofs that selectively disclose subsets of the originally signed set of messages, whilst preserving the verifiable authenticity and integrity of the messages. Furthermore, these proofs are said to be zero-knowledge in nature as they do not reveal the underlying signature; instead, what they reveal is a proof of knowledge of the undisclosed signature.

Discussion Venues

This note is to be removed before publishing as an RFC.

Source for this draft and an issue tracker can be found at https://github.com/decentralized-identity/bbs-signature.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on 12 September 2023.

Table of Contents

1. Introduction

A digital signature scheme is a fundamental cryptographic primitive that is used to provide data integrity and verifiable authenticity in various protocols. The core premise of digital signature technology is built upon asymmetric cryptography where-by the possessor of a private key is able to sign a message, where anyone in possession of the corresponding public key matching that of the private key is able to verify the signature.

The name BBS is derived from the authors of the original academic work of Dan Boneh, Xavier Boyen, and Hovav Shacham, where the scheme was first described.

Beyond the core properties of a digital signature scheme, BBS signatures provide multiple additional unique properties, three key ones are:

Selective Disclosure - The scheme allows a signer to sign multiple messages and produce a single -constant size- output signature. A holder/prover then possessing the messages and the signature can generate a proof whereby they can choose which messages to disclose, while revealing no-information about the undisclosed messages. The proof itself guarantees the integrity and authenticity of the disclosed messages (e.g. that they were originally signed by the signer).

Unlinkable Proofs - The proofs generated by the scheme are known as zero-knowledge, proofs-of-knowledge of the signature, meaning a verifying party in receipt of a proof is unable to determine which signature was used to generate the proof, removing a common source of correlation. In general, each proof generated is indistinguishable from random even for two proofs generated from the same signature.

Proof of Possession - The proofs generated by the scheme prove to a verifier that the party who generated the proof (holder/prover) was in possession of a signature without revealing it. The scheme also supports binding a presentation header to the generated proof. The presentation header can include arbitrary information such as a cryptographic nonce, an audience/domain identifier and or time based validity information.

Refer to the Appendix B for an elaboration on situations where these properties are useful

Below is a basic diagram describing the main entities involved in the scheme

  (1) sign                                      (3) ProofGen
   +-----                                         +-----
   |    |                                         |    |
   |    |                                         |    |
   |   \ /                                        |   \ /
+----------+                                   +-----------+
|          |                                   |           |
|          |                                   |           |
|          |                                   |           |
|  Signer  |---(2)* Send signature + msgs----->|  Holder/  |
|          |                                   |  Prover   |
|          |                                   |           |
|          |                                   |           |
+----------+                                   +-----------+
                                                     |
                                                     |
                                                     |
                                      (4)* Send proof + disclosed msgs
                                                     |
                                                     |
                                                    \ /
                                               +-----------+
                                               |           |
                                               |           |
                                               |           |
                                               | Verifier  |
                                               |           |
                                               |           |
                                               |           |
                                               +-----------+
                                                  |   / \
                                                  |    |
                                                  |    |
                                                  +-----
                                             (5) ProofVerify


Figure 1: Basic diagram capturing the main entities involved in using the scheme

Note The protocols implied by the items annotated by an asterisk are out of scope for this specification

1.1. Terminology

The following terminology is used throughout this document:

SK
The secret key for the signature scheme.
PK
The public key for the signature scheme.
L
The total number of signed messages.
R
The number of message indexes that are disclosed (revealed) in a proof-of-knowledge of a signature.
U
The number of message indexes that are undisclosed in a proof-of-knowledge of a signature.
msg
An input message to be signed by the signature scheme.
generator
A valid point on the selected subgroup of the curve being used that is employed to commit a value.
scalar
An integer between 0 and r-1, where r is the prime order of the selected groups, defined by each ciphersuite (see also Notation).
signature
The digital signature output.
nonce
A cryptographic nonce
presentation_header (ph)
A payload generated and bound to the context of a specific spk.
nizk
A non-interactive zero-knowledge proof from the Fiat-Shamir heuristic.
dst
The domain separation tag.
I2OSP
An operation that transforms a non-negative integer into an octet string, defined in Section 4 of [RFC8017]. Note, the output of this operation is in big-endian order.
OS2IP
An operation that transforms a octet string into an non-negative integer, defined in Section 4 of [RFC8017]. Note, the input of this operation must be in big-endian order.

1.2. Notation

The following notation and primitives are used:

a || b
Denotes the concatenation of octet strings a and b.
I \ J
For sets I and J, denotes the difference of the two sets i.e., all the elements of I that do not appear in J, in the same order as they were in I.
X[a..b]
Denotes a slice of the array X containing all elements from and including the value at index a until and including the value at index b. Note when this syntax is applied to an octet string, each element in the array X is assumed to be a single byte.
range(a, b)
For integers a and b, with a <= b, denotes the ascending ordered list of all integers between a and b inclusive (i.e., the integers "i" such that a <= i <= b).
length(input)
Takes as input either an array or an octet string. If the input is an array, returns the number of elements of the array. If the input is an octet string, returns the number of bytes of the inputted octet string.

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]

E1, E2
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.
G1, G2
subgroups of E1 and E2 (respectively) having prime order r.
GT
a subgroup, of prime order r, of the multiplicative group of a field extension.
e
G1 x G2 -> GT: a non-degenerate bilinear map.
r
The prime order of the G1 and G2 subgroups.
P1, P2
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.
Identity_G1, Identity_G2, Identity_GT
The identity element for the G1, G2, and GT subgroups respectively.
hash_to_curve_g1(ostr, dst) -> P
A cryptographic hash function that takes an arbitrary octet string as input and returns a point in G1, using the hash_to_curve operation defined in [I-D.irtf-cfrg-hash-to-curve] and the inputted dst as the domain separation tag for that operation (more specifically, the inputted dst will become the DST parameter for the hash_to_field operation, called by hash_to_curve).
point_to_octets_g1(P) -> ostr, point_to_octets_g2(P) -> ostr
returns the canonical representation of the point P for the respective subgroup as an octet string. This operation is also known as serialization.
octets_to_point_g1(ostr) -> P, octets_to_point_g2(ostr) -> P
returns the point P for the respective subgroup corresponding to the canonical representation ostr, or INVALID if ostr is not a valid output of the respective point_to_octets_g* function. This operation is also known as deserialization.
subgroup_check(P) -> VALID or INVALID
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].

1.3. Organization of this document

This document is organized as follows:

2. Conventions

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

3. Scheme Definition

This section defines the BBS signature scheme, including the parameters required to define a concrete ciphersuite.

3.1. Parameters

The schemes operations defined in this section depend on the following parameters:

  • A pairing-friendly elliptic curve, plus associated functionality given in Section 1.2.

  • A hash-to-curve suite as defined in [I-D.irtf-cfrg-hash-to-curve], using the aforementioned pairing-friendly curve. This defines the hash_to_curve and expand_message operations, used by this document.

  • get_random(n): returns a random octet string with a length of n bytes, sampled uniformly at random using a cryptographically secure pseudo-random number generator (CSPRNG) or a pseudo random function. See [RFC4086] for recommendations and requirements on the generation of random numbers.

3.2. Considerations

3.2.1. Subgroup Selection

In definition of this signature scheme there are two possible variations based upon the sub-group selection, namely where public keys are defined in G2 and signatures in G1 OR the opposite where public keys are defined in G1 and signatures in G2. Some pairing cryptography based digital signature schemes such as [I-D.irtf-cfrg-bls-signature] elect to allow for both variations, because they optimize for different things. However, in the case of this scheme, due to the operations involved in both signature and proof generation being computational in-efficient when performed in G2 and in the pursuit of simplicity, the scheme is limited to a construction where public keys are in G2 and signatures in G1.

3.2.2. Messages

Each of the core operations of the BBS signature scheme expect the inputted messages to be scalar values within a given range (specifically 1 and r-1, where r is the prime order of the G1 and G2 subgroups, defined by each ciphersuite, see Notation). There are multiple ways to transform a message from an octet string to a scalar value. This document defines the MapMessageToScalarAsHash operation, which hashes an octet string to a scalar (see MapMessageToScalarAsHash). An application can use a different MapMessageToScalar operation, but it MUST be clearly and unambiguously defined, for all parties involved. Before using the core operations, all messages MUST be mapped to their respective scalars using the same operation. The defined MapMessageToScalarAsHash is the RECOMMENDED way of mapping octet strings to scalar values.

3.2.3. Generators

Throughout the operations of this signature scheme, each message that is signed is paired with a specific generator (point in G1). Specifically, if a generator H_1 is multiplied with msg_1 during signing, then H_1 MUST be multiplied with msg_1 in all other operations (signature verification, proof generation and proof verification).

Aside from the message generators, the scheme uses two additional generators: Q_1 and Q_2. The first (Q_1), is used for the blinding value (s) of the signature. The second generator (Q_2), is used to sign the signature's domain, which binds both the signature and generated proofs to a specific context and cryptographically protects any potential application-specific information (for example, messages that must always be disclosed etc.).

3.2.4. Serializing to octet strings

When serializing one or more values to produce an octet string, each element will be encoded using a specific operation determined by its type. More concretely,

  • Points in G* will be serialized using the point_to_octets_g* implementation for a particular ciphersuite.
  • Non-negative integers will be serialized using I2OSP with an output length of 8 bytes.
  • Scalars will be serialized using I2OSP with a constant output length defined by a particular ciphersuite.

We also use strings in double quotes to represent ASCII-encoded literals. For example "BBS" will be used to refer to the octet string, 010000100100001001010011.

Those rules will be used explicitly on every operation. See also Serialize.

3.3. Key Generation Operations

3.3.1. KeyGen

This operation generates a secret key (SK) deterministically from a secret octet string (IKM).

KeyGen uses an HKDF [RFC5869] instantiated with the hash function hash.

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, key_info)

Inputs:

- IKM (REQUIRED), a secret octet string. See requirements above.
- key_info (OPTIONAL), an octet string. if this is not supplied, it
                       MUST default to an empty string.

Definitions:

- HKDF-Extract is as defined in [@!RFC5869], instantiated with hash function hash.
- HKDF-Expand is as defined in [@!RFC5869], instantiated with hash function hash.
- I2OSP and OS2IP are as defined in [@!RFC8017], Section 4.
- L is the integer given by ceil((3 * ceil(log2(r))) / 16).
- INITSALT is the ASCII string "BBS-SIG-KEYGEN-SALT-".

Outputs:

- SK, a uniformly random integer such that 0 < SK < r.

Procedure:

1. salt = INITSALT
2. SK = 0
3. while SK == 0:
4.     salt = hash(salt)
5.     PRK = HKDF-Extract(salt, IKM || I2OSP(0, 1))
6.     OKM = HKDF-Expand(PRK, key_info || I2OSP(L, 2), L)
7.     SK = OS2IP(OKM) mod r
8. return SK

Note This operation is the RECOMMENDED way of generating a secret key, but its use is not required for compatibility, and implementations MAY use a different KeyGen procedure. For security, such an alternative MUST output a secret key that is statistically close to uniformly random in the range 0 < SK < r.

3.3.2. SkToPk

This operation takes a secret key (SK) and outputs a corresponding public key (PK).

PK = SkToPk(SK)

Inputs:

- SK (REQUIRED), a secret integer such that 0 < SK < r.

Outputs:

- PK, a public key encoded as an octet string.

Procedure:

1. W = SK * P2
2. return point_to_octets_g2(W)

3.4. Core Operations

The operations of this section make use of functions and sub-routines defined in Utility Operations. More specifically,

  • hash_to_scalar is defined in Section 4.3
  • calculate_domain and calculate_challenge are defined in Section 4.4 and Section 4.5 correspondingly.
  • serialize, signature_to_octets, octets_to_signature, proof_to_octets, octets_to_proof and octets_to_pubkey are defined in Section 4.6

The following operations also make use of the create_generators operation defined in Section 4.1, to create generator points on G1 (see Messages and Generators). Note that the values of those points depends only on a cipheruite defined seed. As a result, the output of that operation can be cached to avoid unnecessary calls to the create_generators procedure. See Section 4.1 for more details.

3.4.1. Sign

This operation computes a deterministic signature from a secret key (SK) and optionally over a header and or a vector of messages (as scalar values, see Messages).

signature = Sign(SK, PK, header, messages)

Inputs:

- SK (REQUIRED), a non negative integer mod r outputted by the KeyGen
                 operation.
- PK (REQUIRED), an octet string of the form outputted by the SkToPk
                 operation provided the above SK as input.
- header (OPTIONAL), an octet string containing context and application
                     specific information. If not supplied, it defaults
                     to an empty string.
- messages (OPTIONAL), a vector of scalars. If not supplied, it defaults
                       to the empty array "()".

Parameters:

- P1, fixed point of G1, defined by the ciphersuite.
- expand_message, the expand_message operation defined by the suite
                  specified by the hash_to_curve_suite parameter.
- octet_scalar_length, non-negative integer. The length of a scalar
                       octet representation, defined by the ciphersuite.

Definitions:

- L, is the non-negative integer representing the number of messages to
     be signed.
- expand_dst, an octet string representing the domain separation tag:
              utf8(ciphersuite_id || "SIG_DET_DST_"), where
              ciphersuite_id is defined by the ciphersuite.

Outputs:

- signature, a signature encoded as an octet string.

Deserialization:

1. L = length(messages)
2. (msg_1, ..., msg_L) = messages

Procedure:

1.  (Q_1, Q_2, H_1, ..., H_L) = create_generators(L+2)
2.  domain = calculate_domain(PK, Q_1, Q_2, (H_1, ..., H_L), header)
3.  if domain is INVALID, return INVALID
4.  e_s_octs = serialize((SK, domain, msg_1, ..., msg_L))
5.  if e_s_octs is INVALID, return INVALID
6.  e_s_len = octet_scalar_length * 2
7.  e_s_expand = expand_message(e_s_octs, expand_dst, e_s_len)
8.  if e_s_expand is INVALID, return INVALID
9.  e = hash_to_scalar(e_s_expand[0..(octet_scalar_length - 1)])
10. s = hash_to_scalar(e_s_expand[octet_scalar_length..(e_s_len - 1)])
11. if e or s is INVALID, return INVALID
12. B = P1 + Q_1 * s + Q_2 * domain + H_1 * msg_1 + ... + H_L * msg_L
13. A = B * (1 / (SK + e))
14. return signature_to_octets(A, e, s)

Note When computing step 12 of the above procedure there is an extremely small probability (around 2^(-r)) that the condition (SK + e) = 0 mod r will be met. How implementations evaluate the inverse of the scalar value 0 may vary, with some returning an error and others returning 0 as a result. If the returned value from the inverse operation 1/(SK + e) does evaluate to 0 the value of A will equal Identity_G1 thus an invalid signature. Implementations MAY elect to check (SK + e) = 0 mod r prior to step 9, and or A != Identity_G1 after step 9 to prevent the production of invalid signatures.

3.4.2. Verify

This operation checks that a signature is valid for a given header and vector of messages against a supplied public key (PK). The messages MUST be supplied in this operation in the same order they were supplied to Sign when creating the signature.

result = Verify(PK, signature, header, messages)

Inputs:

- PK (REQUIRED), an octet string of the form outputted by the SkToPk
                 operation.
- signature (REQUIRED), an octet string of the form outputted by the
                        Sign operation.
- header (OPTIONAL), an octet string containing context and application
                     specific information. If not supplied, it defaults
                     to an empty string.
- messages (OPTIONAL), a vector of scalars. If not supplied, it defaults
                       to the empty array "()".

Parameters:

- P1, fixed point of G1, defined by the ciphersuite.

Definitions:

- L, is the non-negative integer representing the number of messages to
     be signed.

Outputs:

- result, either VALID or INVALID.

Deserialization:

1. signature_result = octets_to_signature(signature)
2. if signature_result is INVALID, return INVALID
3. (A, e, s) = signature_result
4. W = octets_to_pubkey(PK)
5. if W is INVALID, return INVALID
6. L = length(messages)
7. (msg_1, ..., msg_L) = messages

Procedure:

1. (Q_1, Q_2, H_1, ..., H_L) = create_generators(L+2)
2. domain = calculate_domain(PK, Q_1, Q_2, (H_1, ..., H_L), header)
3. if domain is INVALID, return INVALID
4. B = P1 + Q_1 * s + Q_2 * domain + H_1 * msg_1 + ... + H_L * msg_L
5. if e(A, W + P2 * e) * e(B, -P2) != Identity_GT, return INVALID
6. return VALID

3.4.3. ProofGen

This operation computes a zero-knowledge proof-of-knowledge of a signature, while optionally selectively disclosing from the original set of signed messages. The "prover" may also supply a presentation header, see Presentation header selection for more details.

The messages supplied in this operation MUST be in the same order as when supplied to Sign. To specify which of those messages will be disclosed, the prover can supply the list of indexes (disclosed_indexes) that the disclosed messages have in the array of signed messages. Each element in disclosed_indexes MUST be a non-negative integer, in the range from 1 to length(messages).

The operation calculates multiple random scalars using the calculate_random_scalars utility operation defined in Section 4.1. See also Section 5.10 for considerations and requirements on random scalars generation.

To allow for flexibility in implementations, although ProofGen defines a specific value for expand_len, applications may use any value larger than ceil((ceil(log2(r))+k)/8) (for example, for the BLS12-381-SHAKE-256 and BLS12-381-SHA-256 ciphersuites, an implementation can elect to use a value of 64, instead of 48, as to allow for certain optimizations).

proof = ProofGen(PK, signature, header, ph, messages, disclosed_indexes)

Inputs:

- PK (REQUIRED), an octet string of the form outputted by the SkToPk
                 operation.
- signature (REQUIRED), an octet string of the form outputted by the
                        Sign operation.
- header (OPTIONAL), an octet string containing context and application
                     specific information. If not supplied, it defaults
                     to an empty string.
- ph (OPTIONAL), an octet string containing the presentation header. If not
                 supplied, it defaults to an empty string.
- messages (OPTIONAL), a vector of scalars. If not supplied, it defaults
                       to the empty array "()".
- disclosed_indexes (OPTIONAL), vector of unsigned integers in ascending
                                order. Indexes of disclosed messages. If
                                not supplied, it defaults to the empty
                                array "()".

Parameters:

- P1, fixed point of G1, defined by the ciphersuite.

Definitions:

- L, is the non-negative integer representing the number of messages.
- R, is the non-negative integer representing the number of disclosed
     (revealed) messages.
- U, is the non-negative integer representing the number of undisclosed
     messages, i.e., U = L - R.

Outputs:

- proof, an octet string; or INVALID.

Deserialization:

1.  signature_result = octets_to_signature(signature)
2.  if signature_result is INVALID, return INVALID
3.  (A, e, s) = signature_result
4.  L = length(messages)
5.  R = length(disclosed_indexes)
6.  U = L - R
7.  (i1, ..., iR) = disclosed_indexes
8.  (j1, ..., jU) = range(1, L) \ disclosed_indexes
9.  (msg_1, ..., msg_L) = messages
10. (msg_i1, ..., msg_iR) = (messages[i1], ..., messages[iR])
11. (msg_j1, ..., msg_jU) = (messages[j1], ..., messages[jU])

Procedure:

1.  (Q_1, Q_2, MsgGenerators) = create_generators(L+2)
2.  (H_1, ..., H_L) = MsgGenerators
3.  (H_j1, ..., H_jU) = (MsgGenerators[j1], ..., MsgGenerators[jU])

4.  domain = calculate_domain(PK, Q_1, Q_2, (H_1, ..., H_L), header)
5.  if domain is INVALID, return INVALID
6.  random_scalars = calculate_random_scalars(6+U)
7.  (r1, r2, e~, r2~, r3~, s~, m~_j1, ..., m~_jU) = random_scalars
8.  B = P1 + Q_1 * s + Q_2 * domain + H_1 * msg_1 + ... + H_L * msg_L
9.  r3 = r1 ^ -1 mod r
10. A' = A * r1
11. Abar = A' * (-e) + B * r1
12. D = B * r1 + Q_1 * r2
13. s' = r2 * r3 + s mod r
14. C1 = A' * e~ + Q_1 * r2~
15. C2 = D * (-r3~) + Q_1 * s~ + H_j1 * m~_j1 + ... + H_jU * m~_jU
16. c = calculate_challenge(A', Abar, D, C1, C2, (i1, ..., iR),
                                     (msg_i1, ..., msg_iR), domain, ph)
17. if c is INVALID, return INVALID
18. e^ = c * e + e~ mod r
19. r2^ = c * r2 + r2~ mod r
20. r3^ = c * r3 + r3~ mod r
21. s^ = c * s' + s~ mod r
22. for j in (j1, ..., jU): m^_j = c * msg_j + m~_j mod r
23. proof = (A', Abar, D, c, e^, r2^, r3^, s^, (m^_j1, ..., m^_jU))
24. return proof_to_octets(proof)

3.4.4. ProofVerify

This operation checks that a proof is valid for a header, vector of disclosed messages (along side their index corresponding to their original position when signed) and presentation header against a public key (PK).

The operation accepts the list of messages the prover indicated to be disclosed. Those messages MUST be in the same order as when supplied to Sign (as a subset of the signed messages list). The operation also requires the total number of signed messages (L). Lastly, it also accepts the indexes that the disclosed messages had in the original array of messages supplied to Sign (i.e., the disclosed_indexes list supplied to ProofGen). Every element in this list MUST be a non-negative integer in the range from 1 to L, in ascending order.

result = ProofVerify(PK, proof, header, ph,
                     disclosed_messages,
                     disclosed_indexes)

Inputs:

- PK (REQUIRED), an octet string of the form outputted by the SkToPk
                 operation.
- proof (REQUIRED), an octet string of the form outputted by the
                    ProofGen operation.
- header (OPTIONAL), an optional octet string containing context and
                     application specific information. If not supplied,
                     it defaults to an empty string.
- ph (OPTIONAL), an octet string containing the presentation header. If not
                 supplied, it defaults to an empty string.
- disclosed_messages (OPTIONAL), a vector of scalars. If not supplied,
                                 it defaults to the empty array "()".
- disclosed_indexes (OPTIONAL), vector of unsigned integers in ascending
                                order. Indexes of disclosed messages. If
                                not supplied, it defaults to the empty
                                array "()".

Parameters:

- P1, fixed point of G1, defined by the ciphersuite.

Definitions:

- R, is the non-negative integer representing the number of disclosed
     (revealed) messages.
- U, is the non-negative integer representing the number of undisclosed
     messages.
- L, is the non-negative integer representing the number of total,
     messages i.e., L = U + R.

Outputs:

- result, either VALID or INVALID.

Deserialization:

1.  proof_result = octets_to_proof(proof)
2.  if proof_result is INVALID, return INVALID
3.  (A', Abar, D, c, e^, r2^, r3^, s^, commitments) = proof_result
4.  W = octets_to_pubkey(PK)
5.  if W is INVALID, return INVALID
6.  U  = length(commitments)
7.  R = length(disclosed_indexes)
8.  L = R + U
9.  (i1, ..., iR) = disclosed_indexes
10. (j1, ..., jU) = range(1, L) \ disclosed_indexes
11. (msg_i1, ..., msg_iR) = disclosed_messages
12. (m^_j1, ...., m^_jU) = commitments

Preconditions:

1. for i in (i1, ..., iR), if i < 1 or i > L, return INVALID
2. if length(disclosed_messages) != R, return INVALID

Procedure:

1.  (Q_1, Q_2, MsgGenerators) = create_generators(L+2)
2.  (H_1, ..., H_L) = MsgGenerators
3.  (H_i1, ..., H_iR) = (MsgGenerators[i1], ..., MsgGenerators[iR])
4.  (H_j1, ..., H_jU) = (MsgGenerators[j1], ..., MsgGenerators[jU])

5.  domain = calculate_domain(PK, Q_1, Q_2, (H_1, ..., H_L), header)
6.  if domain is INVALID, return INVALID
7.  C1 = (Abar - D) * c + A' * e^ + Q_1 * r2^
8.  T = P1 + Q_2 * domain + H_i1 * msg_i1 + ... + H_iR * msg_iR
9.  C2 = T * c - D * r3^ + Q_1 * s^ + H_j1 * m^_j1 + ... + H_jU * m^_jU
10. cv = calculate_challenge(A', Abar, D, C1, C2, (i1, ..., iR),
                                      (msg_i1, ..., msg_iR), domain, ph)
11. if cv is INVALID, return INVALID
12. if c != cv, return INVALID
13. if A' == Identity_G1, return INVALID
14. if e(A', W) * e(Abar, -P2) != Identity_GT, return INVALID
15. return VALID

4. Utility Operations

4.1. Random scalars computation

This operation returns the requested number of pseudo-random scalars, using the get_random operation (see Parameters). The operation makes multiple calls to get_random. It is REQUIRED that each call will be independent from each other, as to ensure independence of the returned pseudo-random scalars.

The required length of the get_random output is defined as expand_len. Each value returned by the get_random function is reduced modulo the group order r. To avoid biased results when creating the random scalars, the output of get_random MUST be at least (ceil(log2(r))+k bytes long, where k is the targeted security level specified by the ciphersuite (see Section 5 in [I-D.irtf-cfrg-hash-to-curve] for more details). ProofGen defines expand_len = ceil((ceil(log2(r))+k)/8). For both the BLS12-381-SHAKE-256 and BLS12-381-SHA-256 ciphersuites, log2(r) = 255 and k = 128 resulting to expand_len = 48. See Section 5.10 for further security considerations and requirements around the generated randomness.

Note: The security of the proof generation algorithm (ProofGen) is highly dependant on the quality of the get_random function. Care must be taken to ensure that a cryptographically secure pseudo-random generator is chosen, and that its outputs are not leaked to an adversary. See also Section 5.10 for more details.

random_scalars = calculate_random_scalars(count)

Inputs:

- count (REQUIRED), non negative integer. The number of pseudo random
                    scalars to return.

Parameters:

- get_random, a pseudo random function with extendable output, returning
              uniformly distributed pseudo random bytes.
- expand_len = ceil((ceil(log2(r))+k)/8), where r and k are defined by
                                          the ciphersuite.

Outputs:

- random_scalars, a list of pseudo random scalars,

Procedure:

1. for i in (1, ..., count):
2.     r_i = OS2IP(get_random(expand_len)) mod r
3. return (r_1, r_2, ..., r_count)

4.2. Generator point computation

This operation defines how to create a set of generators that form a part of the public parameters used by the BBS Signature scheme to accomplish operations such as Sign, Verify, ProofGen and ProofVerify. It takes one input, the number of generator points to create, which is determined in part by the number of signed messages.

As an optimization, implementations MAY cache the result of create_generators for a specific generator_seed (determined by the ciphersuite) and count (which can be arbitrarily large, depending on the application). Then, during the execution of one of the Core Operations, if K generators are needed with K <= count, the application can use the K first of the cached generators (in place of the direct call to create_generators(K)).

NOTE: If the generator points are retrieved from cache, the order in which they are retrieved MUST be the same as the order they were originally returned by the create_generators operation.

For example, an application can save 100 generator points H_1, H_2, ..., H_100 returned from create_generators(100). Then if one of the core operations needs 30 of them, the application instead of calling create_generators again, can just retrieve the 30 first generators H_1, H_2, ..., H_30 from the cache instead, in the same order they where originally created (starting from the first one).

The values n and v MAY also be cached in order to efficiently extend an existing list of cached generator points.

generators = create_generators(count)

Inputs:

- count (REQUIRED), unsigned integer. Number of generators to create.

Parameters:

- hash_to_curve_suite, the hash to curve suite id defined by the
                       ciphersuite.
- hash_to_curve_g1, the hash_to_curve operation for the G1 subgroup,
                    defined by the suite specified by the
                    hash_to_curve_suite parameter.
- expand_message, the expand_message operation defined by the suite
                  specified by the hash_to_curve_suite parameter.
- generator_seed, an octet string. A seed value selected by the
                  ciphersuite.
- P1, fixed point of G1, defined by the ciphersuite.

Definitions:

- seed_dst, an octet string representing the domain separation tag:
            ciphersuite_id || "SIG_GENERATOR_SEED_" where
            ciphersuite_id is defined by the ciphersuite and
            "SIG_GENERATOR_SEED_" is an ASCII string comprised of 19
            bytes.
- generator_dst, an octet string representing the domain separation tag:
                 ciphersuite_id || "SIG_GENERATOR_DST_", where
                 ciphersuite_id is defined by the ciphersuite and
                 "SIG_GENERATOR_DST_" is an ASCII string comprised of
                 18 bytes.
- seed_len = ceil((ceil(log2(r)) + k)/8), where r and k are defined by
                                          the ciphersuite.

Outputs:

- generators, an array of generators.

Procedure:

1.  v = expand_message(generator_seed, seed_dst, seed_len)
2.  n = 1
3.  for i in range(1, count):
4.     v = expand_message(v || I2OSP(n, 4), seed_dst, seed_len)
5.     n = n + 1
6.     generator_i = Identity_G1
7.     candidate = hash_to_curve_g1(v, generator_dst)
8.     if candidate in (generator_1, ..., generator_i):
9.        go back to step 4
10.    generator_i = candidate
11. return (generator_1, ..., generator_count)

4.3. MapMessageToScalar

There are multiple ways in which messages can be mapped to their respective scalar values, which is their required form to be used with the Sign, Verify, ProofGen and ProofVerify operations.

4.3.1. MapMessageToScalarAsHash

This operation takes an input message and maps it to a scalar value via a cryptographic hash function for the given curve. The operation takes also as an optional input a domain separation tag (dst). If a dst is not supplied, its value MUST default to the octet string returned from ciphersuite_id || "MAP_MSG_TO_SCALAR_AS_HASH_", where ciphersuite_id is the ASCII string representing the unique ID of the ciphersuite "MAP_MSG_TO_SCALAR_AS_HASH_" is an ASCII string comprised of 26 bytes.

msg_scalar = MapMessageToScalarAsHash(msg, dst)

Inputs:

- msg (REQUIRED), an octet string.
- dst (OPTIONAL), an octet string representing a domain separation tag.
                  If not supplied, it default to the octet string
                  ciphersuite_id || "MAP_MSG_TO_SCALAR_AS_HASH_" where
                  ciphersuite_id is defined by the ciphersuite.

Outputs:

- msg_scalar, a scalar value.

Procedure:

1. if length(msg) > 2^64 - 1 or length(dst) > 255 return INVALID
2. msg_scalar = hash_to_scalar(msg, dst)
3. if msg_scalar is INVALID, return INVALID
4. return msg_scalar

4.4. Hash to Scalar

This operation describes how to hash an arbitrary octet string to n scalar values in the multiplicative group of integers mod r (i.e., values in the range [1, r-1]). This procedure acts as a helper function, used internally in various places within the operations described in the spec. To hash a message to a scalar that would be passed as input to the Sign, Verify, ProofGen and ProofVerify functions, one must use MapMessageToScalarAsHash instead.

This operation makes use of expand_message defined in [I-D.irtf-cfrg-hash-to-curve], in a similar way used by the hash_to_field operation of Section 5 from the same document (with the additional checks for getting a scalar that is 0). If an implementer wants to use hash_to_field instead, they MUST use the multiplicative group of integers mod r (Fr), as the target group (F). Note however, that the hash_to_curve document, makes use of hash_to_field with the target group being the multiplicative group of integers mod p (Fp). For this reason, we don’t directly use hash_to_field here, rather we define a similar operation (hash_to_scalar), making direct use of the expand_message function, that will be defined by the hash-to-curve suite used (i.e., either expand_message_xmd or expand_message_xof). If someone also has a hash_to_field implementation available, with the target group been Fr, they can use this instead (adding the check for a scalar been 0).

The operation takes as input an octet string representing the message to hash (msg), the number of the scalars to return (count) as well as an optional domain separation tag (dst). If a dst is not supplied, its value MUST default to the octet string returned from ciphersuit_id || "H2S_", where ciphersuite_id is the octet string representing the unique ID of the ciphersuite and "H2S_" is an ASCII string comprised of 4 bytes.

Note It is possible that the hash_to_scalar procedure will return an error, if the underlying expand_message operation aborts. See [I-D.irtf-cfrg-hash-to-curve], Section 5.3, for more details on the cases that expand_message will abort (note that the input term len_in_bytes of expand_message in the Hash-to-Curve document equals count * expand_len in our case).

hashed_scalar = hash_to_scalar(msg_octets, dst)

Inputs:

- msg_octets (REQUIRED), an octet string. The message to be hashed.
- dst (OPTIONAL), an octet string representing a domain separation tag.
                  If not supplied, it defaults to the octet string given
                  by ciphersuite_id || "H2S_", where ciphersuite_id is
                  defined by the ciphersuite.

Parameters:

- hash_to_curve_suite, the hash to curve suite id defined by the
                       ciphersuite.
- expand_message, the expand_message operation defined by the suite
                  specified by the hash_to_curve_suite parameter.

Definitions:

- expand_len = ceil((ceil(log2(r))+k)/8), where r and k are defined by
                                          the ciphersuite.

Outputs:

- hashed_scalar, a non-zero scalar mod r.

Procedure:

1.  counter = 0
2.  hashed_scalar = 0
3.  while hashed_scalar == 0:
4.      if counter > 255, return INVALID
5.      msg_prime = msg_octets || I2OSP(counter, 1)
6.      uniform_bytes = expand_message(msg_prime, dst, expand_len)
7.      if uniform_bytes is INVALID, return INVALID
8.      hashed_scalar = OS2IP(uniform_bytes) mod r
9.      counter = counter + 1
10. return hashed_scalar

4.5. Domain Calculation

This operation calculates the domain value, a scalar representing the distillation of all essential contextual information for a signature. The same domain value must be calculated by all parties (the signer, the prover, and the verifier) for both the signature and proofs to be validated.

The input to the domain value includes an octet string called the header, chosen by the signer and meant to encode any information that is required to be revealed by the prover (such as an expiration date, or an identifier for the target audience). This is in contrast to the signed message values, which may be withheld during a proof.

When a signature is calculated, the domain value is combined with a specific generator point (Q_2, see Sign) to protect the integrity of the public parameters and the header.

This operation makes use of the serialize function, defined in Section 4.6.1.

domain = calculate_domain(PK, Q_1, Q_2, H_Points, header)

Inputs:

- PK (REQUIRED), an octet string, representing the public key of the
                 Signer of the form outputted by the SkToPk operation.
- (Q_1, Q_2) (REQUIRED), points of G1 (the first 2 points returned from
                         create_generators).
- H_Points (REQUIRED), array of points of G1.
- header (OPTIONAL), an octet string. If not supplied, it must default to
                     the empty octet string ("").

Parameters:

- ciphersuite_id, an octet string. The unique ID of the ciphersuite.

Outputs:

- domain, a scalar value or INVALID.

Procedure:

1.  L = length(H_Points)
2.  if length(header) > 2^64 - 1 or L > 2^64 - 1, return INVALID
3.  (H_1, ..., H_L) = H_Points
4.  dom_array = (L, Q_1, Q_2, H_1, ..., H_L)
5.  dom_octs = serialize(dom_array) || ciphersuite_id
6.  if dom_octs is INVALID, return INVALID
7.  dom_input = PK || dom_octs || I2OSP(length(header), 8) || header
8.  domain = hash_to_scalar(dom_input)
9.  if domain is INVALID, return INVALID
10. return domain

Note: If the header is not supplied in calculate_domain, it defaults to the empty octet string (""). This means that in the concatenation step of the above procedure (step 7), 8 bytes representing a length of 0 (i.e., 0x0000000000000000), will still need to be appended at the end, even though a header value is not provided.

4.6. Challenge Calculation

This operation calculates the challenge scalar value, used during ProofGen and ProofVerify, as part of the Fiat-Shamir heuristic, for making the proof protocol non-interactive (in a interactive sating, the challenge would be a random value supplied by the verifier).

This operation makes use of the serialize function, defined in Section 4.6.1.

challenge = calculate_challenge(A', Abar, D, C1, C2, i_array,
                                                  msg_array, domain, ph)

Inputs:

- (A', Abar, D, C1, C2) (REQUIRED), points of G1, as calculated in
                                    ProofGen.
- i_array (REQUIRED), array of non-negative integers (the indexes of
                      the disclosed messages).
- msg_array (REQUIRED), array of scalars (the disclosed messages).
- domain (REQUIRED), a scalar.
- ph (OPTIONAL), an octet string. If not supplied, it must default to the
                 empty octet string ("").

Outputs:

- challenge, a scalar or INVALID.

Procedure:

1.  R = length(i_array)
2.  if R > 2^64 - 1 or R != length(msg_array), return INVALID
3.  if length(ph) > 2^64 - 1, return INVALID
4.  (i1, ..., iR) = i_array
5.  (msg_i1, ..., msg_iR) = msg_array
6.  c_array = (A', Abar, D, C1, C2, R, i1, ..., iR,
                                   msg_i1, ..., msg_iR, domain)
7.  c_octs = serialize(c_array)
8.  if c_octs is INVALID, return INVALID
9.  c_input = c_octs || I2OSP(length(ph), 8) || ph
10. challenge = hash_to_scalar(c_input)
11. if challenge is INVALID, return INVALID
12. return challenge

Note: Similarly to the header value in Domain Calculation, if the presentation header (ph) is not supplied in calculate_challenge, 8 bytes representing a length of 0 (i.e., 0x0000000000000000), must still be appended after the c_octs value, during the concatenation step of the above procedure (step 9).

4.7. Serialization

4.7.1. Serialize

This operation describes how to transform multiple elements of different types (i.e., elements that are not already in a octet string format) to a single octet string (see Section 3.2.3). The inputted elements can be points, scalars (see Terminology) or integers between 0 and 2^64-1. The resulting octet string will then either be used as an input to a hash function (i.e., in Sign, ProofGen etc.), or to serialize a signature or proof (see SignatureToOctets and ProofToOctets).

octets_result = serialize(input_array)

Inputs:

- input_array (REQUIRED), an array of elements to be serialized. Each
                          element must be either a point of G1 or G2, a
                          scalar, an ASCII string or an integer value
                          between 0 and 2^64 - 1.

Parameters:

- octet_scalar_length, non-negative integer. The length of a scalar
                       octet representation, defined by the ciphersuite.
- r, the prime order of the subgroups G1 and G2, defined by the
     ciphersuite.
- point_to_octets_g*, operations that serialize a point of G1 or G2 to
                      an octet string of fixed length, defined by the
                      ciphersuite.

Outputs:

- octets_result, a scalar value or INVALID.

Procedure:

1.  let octets_result be an empty octet string.
2.  for el in input_array:
3.      if el is a point of G1: el_octs = point_to_octets_g1(el)
4.      else if el is a point of G2: el_octs = point_to_octets_g2(el)
5.      else if el is a scalar: el_octs = I2OSP(el, octet_scalar_length)
6.      else if el is an integer between 0 and 2^64 - 1:
7.          el_octs = I2OSP(el, 8)
8.      else: return INVALID
9.      octets_result = octets_result || el_octs
10. return octets_result

4.7.2. SignatureToOctets

This operation describes how to encode a signature to an octet string.

Note this operation deliberately does not perform the relevant checks on the inputs A, e and s because its assumed these are done prior to its invocation, e.g as is the case with the Sign operation.

signature_octets = signature_to_octets(signature)

Inputs:

- signature (REQUIRED), a valid signature, in the form (A, e, s), where
                        A a point in G1 and e, s non-zero scalars mod r.

Outputs:

- signature_octets, an octet string or INVALID.

Procedure:

1. (A, e, s) = signature
2. return serialize((A, e, s))

4.7.3. OctetsToSignature

This operation describes how to decode an octet string, validate it and return the underlying components that make up the signature.

signature = octets_to_signature(signature_octets)

Inputs:

- signature_octets (REQUIRED), an octet string of the form output from
                               signature_to_octets operation.

Outputs:

signature, a signature in the form (A, e, s), where A is a point in G1
           and e and s are non-zero scalars mod r.

Procedure:

1.  expected_len = octet_point_length + 2 * octet_scalar_length
2.  if length(signature_octets) != expected_len, return INVALID
3.  A_octets = signature_octets[0..(octet_point_length - 1)]
4.  A = octets_to_point_g1(A_octets)
5.  if A is INVALID, return INVALID
6.  if A == Identity_G1, return INVALID
7.  index = octet_point_length
8.  end_index = index + octet_scalar_length - 1
9.  e = OS2IP(signature_octets[index..end_index])
10. if e = 0 OR e >= r, return INVALID
11. index += octet_scalar_length
12. end_index = index + octet_scalar_length - 1
13. s = OS2IP(signature_octets[index..end_index])
14. if s = 0 OR s >= r, return INVALID
15. return (A, e, s)

4.7.4. ProofToOctets

This operation describes how to encode a proof, as computed at step 25 in ProofGen, to an octet string. The input to the operation MUST be a valid proof.

The inputted proof value must consist of the following components, in that order:

  1. Three (3) valid points of the G1 subgroup, different from the identity point of G1 (i.e., A', Abar, D, in ProofGen)
  2. Five (5) integers representing scalars in the range of 1 to r-1 inclusive (i.e., c, e^, r2^, r3^, s^, in ProofGen).
  3. A number of integers representing scalars in the range of 1 to r-1 inclusive, corresponding to the undisclosed from the proof messages (i.e., m^_j1, ..., m^_jU, in ProofGen, where U the number of undisclosed messages).
proof_octets = proof_to_octets(proof)

Inputs:

- proof (REQUIRED), a BBS proof in the form calculated by ProofGen in
                    step 27 (see above).

Parameters:

- octet_scalar_length (REQUIRED), non-negative integer. The length of
                                  a scalar octet representation, defined
                                  by the ciphersuite.

Outputs:

- proof_octets, an octet string or INVALID.

Procedure:

1. (A', Abar, D, c, e^, r2^, r3^, s^, (m^_1, ..., m^_U)) = proof
2. return serialize((A', Abar, D, c, e^, r2^, r3^, s^, m^_1, ..., m^_U))

4.7.5. OctetsToProof

This operation describes how to decode an octet string representing a proof, validate it and return the underlying components that make up the proof value.

The proof value outputted by this operation consists of the following components, in that order:

  1. Three (3) valid points of the G1 subgroup, each of which must not equal the identity point.
  2. Five (5) integers representing scalars in the range of 1 to r-1 inclusive.
  3. A set of integers representing scalars in the range of 1 to r-1 inclusive, corresponding to the undisclosed from the proof message commitments. This set can be empty (i.e., "()").
proof = octets_to_proof(proof_octets)

Inputs:

- proof_octets (REQUIRED), an octet string of the form outputted from the
                           proof_to_octets operation.

Parameters:

- r (REQUIRED), non-negative integer. The prime order of the G1 and
                G2 groups, defined by the ciphersuite.
- octet_scalar_length (REQUIRED), non-negative integer. The length of
                                  a scalar octet representation, defined
                                  by the ciphersuite.
- octet_point_length (REQUIRED), non-negative integer. The length of
                                 a point in G1 octet representation,
                                 defined by the ciphersuite.

Outputs:

- proof, a proof value in the form described above or INVALID

Procedure:

1.  proof_len_floor = 3 * octet_point_length + 5 * octet_scalar_length
2.  if length(proof_octets) < proof_len_floor, return INVALID

// Points (i.e., (A', Abar, D) in ProofGen) de-serialization.
3.  index = 0
4.  for i in range(0, 2):
5.      end_index = index + octet_point_length - 1
6.      A_i = octets_to_point_g1(proof_octets[index..end_index])
7.      if A_i is INVALID or Identity_G1, return INVALID
8.      index += octet_point_length

// Scalars (i.e., (c, e^, r2^, r3^, s^, (m^_j1, ..., m^_jU)) in
// ProofGen) de-serialization.
9.  j = 0
10. while index < length(proof_octets):
11.     end_index = index + octet_scalar_length - 1
12.     s_j = OS2IP(proof_octets[index..end_index])
13.     if s_j = 0 or if s_j >= r, return INVALID
14.     index += octet_scalar_length
15.     j += 1

16. if index != length(proof_octets), return INVALID
17. msg_commitments = ()
18. If j > 5, set msg_commitments = (s_5, ..., s_(j-1))
19. return (A_0, A_1, A_2, s_0, s_1, s_2, s_3, s_4, msg_commitments)

4.7.6. OctetsToPublicKey

This operation describes how to decode an octet string representing a public key, validates it and returns the corresponding point in G2. Steps 2 to 5 check if the public key is valid. As an optimization, implementations MAY cache the result of those steps, to avoid unnecessarily repeating validation for known public keys.

W = octets_to_pubkey(PK)

Inputs:

- PK, an octet string. A public key in the form outputted by the SkToPK
      operation

Outputs:

- W, a valid point in G2 or INVALID

Procedure:

1. W = octets_to_point_g2(PK)
2. If W is INVALID, return INVALID
3. if subgroup_check(W) is INVALID, return INVALID
4. If W == Identity_G2, return INVALID
5. return W

5. Security Considerations

5.1. Validating public keys

It is RECOMENDED for any operation in Core Operations involving public keys, that they deserialize the public key first using the OctetsToPublicKey operation, even if they only require the octet-string representation of the public key. If the octets_to_pubkey procedure (see the OctetsToPublicKey section) returns INVALID, the calling operation should also return INVALID and abort. An example of where this recommendation applies is the Sign operation. An example of where an explicit invocation to the octets_to_pubkey operation is already defined and therefore required is the Verify operation.

5.2. Point de-serialization

This document makes use of octet_to_point_g* to parse octet strings to elliptic curve points (either in G1 or G2). It is assumed (even if not explicitly described) that the result of this operation will not be INVALID. If octet_to_point_g* returns INVALID, then the calling operation should immediately return INVALID as well and abort the operation. Note that the only place where the output is assumed to be VALID implicitly is in the EncodingForHash section.

5.3. Skipping membership checks

Some existing implementations skip the subgroup_check invocation in Verify, 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.

  1. For most pairing-friendly elliptic curves used in practice, the pairing operation e Section 1.2 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.

  2. 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].

5.4. Side channel attacks

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.

5.5. Randomness considerations

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 proofs are nondeterministic, meaning care must be taken against attacks arising from using bad randomness, for example, the nonce reuse attack on ECDSA [HDWH12]. It is RECOMMENDED that the presentation header used in this specification contain a nonce chosen at random from a trusted source of randomness, see the Section 5.6 for additional considerations.

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.

5.6. Presentation header selection

The signature proofs of knowledge generated in this specification are created using a specified presentation header. A verifier-specified cryptographically random value (e.g., a nonce) featuring in the presentation header provides strong protections against replay attacks, and is RECOMMENDED in most use cases. In some settings, proofs can be generated in a non-interactive fashion, in which case verifiers MUST be able to verify the uniqueness of the presentation header values.

5.7. Implementing hash_to_curve_g1

The security analysis models hash_to_curve_g1 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_curve. Some guidance around defining this can be found in Section 6.

5.8. Choice of underlying curve

BBS signatures can be implemented on any pairing-friendly curve. However care MUST be taken when selecting one that is appropriate, this specification defines a ciphersuite for using the BLS12-381 curve in Section 6 which as a curve achieves around 117 bits of security according to a recent NCC ZCash cryptography review [ZCASH-REVIEW].

5.9. Security of proofs generated by ProofGen

The proof, as returned by ProofGen, is a zero-knowledge proof-of-knowledge [CDL16]. This guarantees that no information will be revealed about the signature itself or the undisclosed messages, from the output of ProofGen. Note that the security proofs in [CDL16] work on type 3 pairing setting. This means that G1 should be different from G2 and with no efficient isomorphism between them.

5.10. Randomness requirements

ProofGen is by its nature a randomized algorithm, requiring the generation of multiple uniformly distributed, pseudo random scalars. This makes ProofGen vulnerable to bad entropy in certain applications. As an example of such application, consider systems that need to monitor and potentially restrict outbound traffic, in order to minimize data leakage during a breach. In such cases, the attacker could manipulate couple of bits in the output of the get_random function to create an undetected chanel out of the system. Although the applicability of such attacks is limited for most of the targeted use cases of the BBS scheme, some applications may want to take measures towards mitigating them. To that end, it is RECOMMENDED to use a deterministic RNG (like a ChaCha20 based deterministic RNG), seeded with a unique, uniformly random, single seed [DRBG]. This will limit the amount of bits the attacker can manipulate (note that some randomness is always needed).

In any case, the randomness used in ProofGen MUST be unique in each call and MUST have a distribution that is indistinguishable from uniform. If the random scalars are re-used, are created from "bad randomness" (for example with a known relationship to each other) or are in any way predictable, an adversary will be able to unveil the undisclosed from the proof messages or the hidden signature value. Naturally, a cryptographically secure pseudorandom number generator or pseudo random function is REQUIRED to implement the get_random functionality. See also [RFC8937], for recommendations on generating good randomness in cases where the Prover has direct or in-direct access to a secret key.

6. Ciphersuites

This section defines the format for a BBS ciphersuite. It also gives concrete ciphersuites based on the BLS12-381 pairing-friendly elliptic curve [I-D.irtf-cfrg-pairing-friendly-curves].

6.1. Ciphersuite Format

6.1.1. Ciphersuite ID

The following section defines the format of the unique identifier for the ciphersuite denoted ciphersuite_id, which will be represented as an ASCII encoded octet string. The REQUIRED format for this string is

  "BBS_" || H2C_SUITE_ID || ADD_INFO
  • H2C_SUITE_ID is the suite ID of the hash-to-curve suite used to define the hashtocurve function.

  • ADD_INFO is an optional octet string indicating any additional information used to uniquely qualify the ciphersuite. When present this value MUST only contain ASCII encoded characters with codes between 0x21 and 0x7e (inclusive) and MUST end with an underscore (ASCII code: 0x5f), other than the last character the string MUST not contain any other underscores (ASCII code: 0x5f).

6.1.2. Additional Parameters

The parameters that each ciphersuite needs to define are generally divided into three main categories; the basic parameters (a hash function etc.,), the serialization operations (point_to_octets_g1 etc.,) and the generator parameters. See below for more details.

Basic parameters:

  • hash: a cryptographic hash function.

  • octet_scalar_length: Number of bytes to represent a scalar value, in the multiplicative group of integers mod r, encoded as an octet string. It is RECOMMENDED this value be set to ceil(log2(r)/8).

  • octet_point_length: Number of bytes to represent a point encoded as an octet string outputted by the point_to_octets_g* function. It is RECOMMENDED that this value is set to ceil(log2(p)/8).

  • hash_to_curve_suite: The hash-to-curve ciphersuite id, in the form defined in [I-D.irtf-cfrg-hash-to-curve]. This defines the hash_to_curve_g1 (the hash_to_curve operation for the G1 subgroup, see the Notation section) and the expand_message (either expand_message_xmd or expand_message_xof) operations used in this document.

  • P1: A fixed point in the G1 subgroup.

Serialization functions:

  • point_to_octets_g1: a function that returns the canonical representation of the point P for the G1 subgroup as an octet string.

  • point_to_octets_g2: a function that returns the canonical representation of the point P for the G2 subgroup as an octet string.

  • octets_to_point_g1: a function that returns the point P in the subgroup G1 corresponding to the canonical representation ostr, or INVALID if ostr is not a valid output of point_to_octets_g1.

  • octets_to_point_g2: a function that returns the point P in the subgroup G2 corresponding to the canonical representation ostr, or INVALID if ostr is not a valid output of point_to_octets_g2.

Generator parameters:

  • generator_seed: The seed used to determine the generator points which form part of the public parameters used by the BBS signature scheme. Note there are multiple possible scopes for this seed, including: a globally shared seed (where the resulting message generators are common across all BBS signatures); a signer specific seed (where the message generators are specific to a signer); and a signature specific seed (where the message generators are specific per signature). The ciphersuite MUST define this seed OR how to compute it as a pre-cursor operation to any others.

6.2. BLS12-381 Ciphersuites

The following two ciphersuites are based on the BLS12-381 elliptic curves defined in Section 4.2.1 of [I-D.irtf-cfrg-pairing-friendly-curves]. The targeted security level of both suites in bits is k = 128.

The first ciphersuite makes use of an extendable output function, and most specifically of SHAKE-256, as defined in Section 6.2 of [SHA3]. It also uses the hash-to-curve suite defined by this document in Appendix A.1, which also makes use of the SHAKE-256 function.

The second ciphersuite uses SHA-256, as defined in Section 6.2 of [SHA2] and the BLS12-381 G1 hash-to-curve suite defined in Section 8.8.1 of the [I-D.irtf-cfrg-hash-to-curve] document.

Note that these two ciphersuites differ only in the hash function (SHAKE-256 vs SHA-256) and in the hash-to-curve suites used. The hash-to-curve suites differ in the expand_message variant and underlying hash function. More concretely, the BLS12-381-SHAKE-256 ciphersuite makes use of expand_message_xof with SHAKE-256, while BLS12-381-SHA-256 makes use of expand_message_xmd with SHA-256. Curve parameters are common between the two ciphersuites.

6.2.1. BLS12-381-SHAKE-256

Basic parameters:

  • ciphersuite_id: "BBS_BLS12381G1_XOF:SHAKE-256_SSWU_RO_"

  • hash: SHAKE-256 as defined in [SHA3].

  • octet_scalar_length: 32, based on the RECOMMENDED approach of ceil(log2(r)/8).

  • octet_point_length: 48, based on the RECOMMENDED approach of ceil(log2(p)/8).

  • hash_to_curve_suite: "BLS12381G1_XOF:SHAKE-256_SSWU_RO_" as defined in Appendix A.1 for the G1 subgroup.

  • P1: The G1 point returned from the create_generators procedure, with generator_seed = "BBS_BLS12381G1_XOF:SHAKE-256_SSWU_RO_BP_MESSAGE_GENERATOR_SEED". More specifically,

    P1 = 91b784eaac4b2b2c6f9bfb2c9eae97e817dd12bba49a0821d175a50f1632465b319ca9fb
    81dda3fb0434412185e2cca5
    

Serialization functions:

Generator parameters:

  • generator_seed: A global seed value of "BBS_BLS12381G1_XOF:SHAKE-256_SSWU_RO_MESSAGE_GENERATOR_SEED" (an ASCII string comprised of 59 bytes) which is used by the create_generators operation to compute the required set of message generators.

6.2.2. BLS12-381-SHA-256

Basic parameters:

  • Ciphersuite_ID: "BBS_BLS12381G1_XMD:SHA-256_SSWU_RO_"

  • hash: SHA-256 as defined in [SHA2].

  • octet_scalar_length: 32, based on the RECOMMENDED approach of ceil(log2(r)/8).

  • octet_point_length: 48, based on the RECOMMENDED approach of ceil(log2(p)/8).

  • hash_to_curve_suite: "BLS12381G1_XMD:SHA-256_SSWU_RO_" as defined in Section 8.8.1 of the [I-D.irtf-cfrg-hash-to-curve] for the G1 subgroup.

  • P1: The G1 point returned from the create_generators procedure, with generator_seed = "BBS_BLS12381G1_XMD:SHA-256_SSWU_RO_BP_MESSAGE_GENERATOR_SEED". More specifically,

    P1 = 8533b3fbea84e8bd9ccee177e3c56fbe1d2e33b798e491228f6ed65bb4d1e0ada07bcc44
    89d8751f8ba7a1b69b6eecd7
    

Serialization functions:

Generator parameters:

  • generator_seed: A global seed value of "BBS_BLS12381G1_XMD:SHA-256_SSWU_RO_MESSAGE_GENERATOR_SEED" (an ASCII string comprised of 57 bytes) which is used by the create_generators operation to compute the required set of message generators.

7. Test Vectors

The following section details a basic set of test vectors that can be used to confirm an implementations correctness

NOTE All binary data below is represented as octet strings in big endian order, encoded in hexadecimal format.

NOTE These fixtures are a work in progress and subject to change.

7.1. Mocked random scalars

For the purpose of presenting fixtures for the ProofGen operation we describe here a way to mock the calculate_random_scalars operation (Random scalars computation), used by ProofGen to create all the necessary random scalars.

To that end, the seeded_random_scalars(SEED) operation is defined, which will deterministically calculate count random-looking scalars from a single SEED. The proof test vector will then define a SEED (as a nothing-up-my-sleeve value) and set

mocked_calculate_random_scalars(count) :=
                             seeded_random_scalars(SEED, count)

The mocked_calculate_random_scalars operation will then be used in place of calculate_random_scalars during the ProofGen operation's procedure.

Note For the BLS12-381-SHA-256 ciphersuite if more than 170 mocked random scalars are required, the operation will return INVALID. Similarly, for the BLS12-381-SHAKE-256 ciphersuite, if more than 1365 mocked random scalars are required, the operation will return INVALID. For the purpose of describing ProofGen test vectors, those limits are inconsequential.

seeded_scalars = seeded_random_scalars(SEED, count)

Inputs:

- count (REQUIRED), non negative integer. The number of scalars to
                    return.
- SEED (REQUIRED), an octet string. The random seed from which to generate
                   the scalars.

Parameters:

- expand_message, the expand_message operation defined by the
                  ciphersuite.
- expand_len = ceil((ceil(log2(r))+k)/8), where r and k are defined by
                                          the ciphersuite.
- dst = utf8(ciphersuite_id || "MOCK_RANDOM_SCALARS_DST_"), where
      ciphersuite_id is defined by teh ciphersuite.

Outputs:

- mocked_random_scalars, a list of "count" pseudo random scalars

Preconditions:

1. if count * expand_len > 65535, return INVALID

Procedure:

1. out_len = expand_len * count
2. v = expand_message(SEED, dst, out_len)
3. if v is INVALID, return INVALID

4. for i in (1, ..., count):
5.     start_idx = (i-1) * expand_len
6.     end_idx = i * expand_len - 1
7.     r_i = OS2IP(v[start_idx..end_idx]) mod r
8. return (r_1, ...., r_count)

7.2. Key Pair

The following key pair will be used for the test vectors of both ciphersuites. Note that it is made based on the BLS12-381-SHA-356 ciphersuite, meaning that it uses SHA-256 as a hash function. Although KeyGen is not REQUIRED for ciphersuite compatibility, it is RECOMMENDED that implementations will NOT re-use keys across different ciphersuites (even if they are based on the same curve).

NOTE: this is work in progress and in the future, we may add different key pairs per ciphersuite for the test vectors.

Following the procedure defined in Section 3.3.1 with an input IKM value as follows

746869732d49532d6a7573742d616e2d546573742d494b4d2d746f2d67656e6572617465
2d246528724074232d6b6579

and the following key_info value

746869732d49532d736f6d652d6b65792d6d657461646174612d746f2d62652d75736564
2d696e2d746573742d6b65792d67656e

Outputs the following SK value

4a39afffd624d69e81808b2e84385cc80bf86adadf764e030caa46c231f2a8d7

Following the procedure defined in Section 3.3.2 with an input SK value as above produces the following PK value

aaff983278257afc45fa9d44d156c454d716fb1a250dfed132d65b2009331f618c623c14
efa16245f50cc92e60334051087f1ae92669b89690f5feb92e91568f95a8e286d110b011
e9ac9923fd871238f57d1295395771331ff6edee43e4ccc6

7.3. Messages

The following messages are used by the test vectors of both ciphersuites (unless otherwise stated).

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

87a8bd656d49ee07b8110e1d8fd4f1dcef6fb9bc368c492d9bc8c4f98a739ac6

96012096adda3f13dd4adbe4eea481a4c4b5717932b73b00e31807d3c5894b90

ac55fb33a75909edac8994829b250779298aa75d69324a365733f16c333fa943

d183ddc6e2665aa4e2f088af9297b78c0d22b4290273db637ed33ff5cf703151

515ae153e22aae04ad16f759e07237b43022cb1ced4c176e0999c6a8ba5817cc

496694774c5604ab1b2544eababcf0f53278ff5040c1e77c811656e8220417a2

77fe97eb97a1ebe2e81e4e3597a3ee740a66e9ef2412472c23364568523f8b91

7372e9daa5ed31e6cd5c825eac1b855e84476a1d94932aa348e07b7320912416

c344136d9ab02da4dd5908bbba913ae6f58c2cc844b802a6f811f5fb075f9b80

7.4. BLS12-381-SHAKE-256 Test Vectors

Test vectors of the BLS12-381-SHAKE-256 ciphersuite. Further fixtures are available in additional BLS12-381-SHAKE-256 test vectors.

7.4.1. Map Messages to Scalars

The messages in Section 3.2.2 must be mapped to scalars before passed to the Sign, Verify, ProofGen and ProofVerify operations. For the purpose of the test vectors presented in this document we are using the MapMessageToScalarAsHash operation to map each message to a scalar. For the BLS12-381-SHAKE-256 ciphersuite, on input each message in Section 3.2.2 and the following default dst

4242535f424c53313233383147315f584f463a5348414b452d3235365f535357555f524f
5f4d41505f4d53475f544f5f5343414c41525f41535f484153485f

The output scalars, encoded to octets using I2OSP and represented in big endian order, are the following,

47f99622ec7bdc140b947eacc95f716a7223527751589febf4877e669a636667

55464a899adb6635e449e4289b7d4540655017242843116f419294b363f15662

3575b312561f50a72cff7652345264173afc4858f7d63dbfc2760978dbb0fe9a

4365f9e2175e58be3dff52760e52583374cf8b02f4c71336b1d31d1b780d0b79

1145adf00892d230c084e585fdfd656022957695265152c8964309f03fc8c4c1

06182ce52763232b1aeb1aa5164e0984b6243ab8bb65a17ef82274140378078f

46fb647beb5547df20ffdb5cb4a6492b7796e24c14283b7f2793b1b14ca2cdf1

4e42aecc90ad7a59820ecd74eaa70404abbc1f979b3f2ea164abe42d79e5d9c9

6194d15c9c8f4dbf710b2bbfa6a95356a8999b1192698b8cfdddd4b9b8a67025

363ba017bba906cab5f9dd5c289f93ff5f9e6cc76296c7a3a1992c1dafe2c979

Note that in both the following test vectors, as well as the additional BLS12-381-SHAKE-256 test vectors in Appendix C.1, when we are referring to a message that will be passed to one of the Sign, Verify, ProofGen or ProofVerify operations, we assume that it will first be mapped into one of the above scalars, using the MapMessageToScalarAsHash operation.

7.4.2. Message Generators

Following the procedure defined in Section 4.2 with an input count value of 12, for the BLS12-381-SHAKE-256 suite, outputs the following values (note that the first 2 correspond to Q_1 and Q_2, while the next 10, to the message generators H_1, ..., H_10).

b60acd4b0dc13b580394d2d8bc6c07d452df8e2a7eff93bc9da965b57e076cae640c2858
fb0c2eaf242b1bd11107d635

ad03f655b4c94f312b051aba45977c924bc5b4b1780c969534c183784c7275b70b876db6
41579604328c0975eaa0a137

b63ae18d3edd64a2edd381290f0c68bebabaf3d37bc9dbb0bd5ad8daf03bbd2c48260255
ba73f3389d2d5ad82303ac25

b0b92b79a3e1fc59f39c6b9f78f00b873121c6a4c1814b94c07848efd172762fefbc4844
7a16f9ba8ed1b638e2933029

b671ed7256777fb5b82f66d1268d03492a1cecc19fd327d56e100cce69c2e15fcd03dcdc
fe6b2d42aa039edcd58092f4

867009da287e1186884084ed71477ce9bd401e0bf4a7be48e2af0a3a4f2e7e21d2b7bb0f
fdc4c03b5aa9672c3c76e0c9

a3a10489bf1a244753e864454fd24ed8c312f737c0c2a529905222509199a0b48715a048
cd93d134dac2cd4934c549bb

81d548904ec8aa58b3f56f69c3f543fb73f339699a33df82c338cad9657b70c457b735c4
ae96e8ea0c1ea0da65059d95

b4bbc2a56104c2289fc7688fef30222746467df27698b6c2d53dad5477fd05b7ec8a8412
2b8122c1de2d2f16750d2a92

ae22a4e89029d3507b8e40af3531b114b564cc77375c249036926e6973f69d21b356e734
cdeda47fd320035781eda7df

98b266b03b9cea3d466bafbcd2e1c600c40cba8817d52d46ea77612df911a6e6c0406352
11fc1bffd4ca914afca1ce55

b458cd3d7af0b5ceea335436a66e2015b216467c204b850b15547f68f6f2a209e8229d15
4d4f998c7b96aa4f88cdca15

7.4.3. Signature Fixtures

7.4.3.1. Valid Single Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following message (the first message defined in Section 3.2.2)

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

After it is mapped to the first scalar in Section 7.4.1, along with the SK value as defined in Section 7.2 as inputs into the Sign operations, yields the following output signature

a7386ffaa4e70a9a44483adccc202a658e1c1f02190fb95bfd0f826a0188d73ab910c556
fb3c1d9e212dea3c5e9989271a5e578c4625d290a0e7f2355eabe7584af5eb822c72319e
588b2c20cd1e8256698d6108f599c2e48cf1be8e4ebfaf7ae397a5733a498d3d466b843c
027311bb
7.4.3.2. Valid Multi-Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the messages defined in Section 3.2.2 (Note the ordering of the messages MUST be preserved), after they are mapped to the scalars in Section 7.4.1, along with the SK value as defined in Section 7.2 as inputs into the Sign operations, yields the following output signature

ae0587beb6b307f847eaf654f74177de4689b46c6d2b3eca6a6a80c798db78b0ccc25196
6debb500ec7fee8ca382bcc925860a0030570b2b56eb39868215b3b1ca1ab1ad9cdd5bac
cc8825f8133f12a4288c875e7f1aedc5861d7f3e45542e456425c632c9a82f4cc0b237e3
b603b1b6

7.4.4. Proof fixtures

For the generation of the following fixtures the mocked_calculate_random_scalars defined in Mocked Random Scalars is used, in place of the calculate_random_scalars operation, with the following seed value (hex encoding of utf8("<30 first digits of pi>"))

SEED = "332e313431353932363533353839373933323338343632363433333833323739"

Given the above seed the first 10 scalars returned by the mocked_calculate_random_scalars operation will be,

01b6e08fc79e13fad32d67f961ddb2e78d71efc3535ca36a5ff473f48266ce64
0cdd099ab5ed28de45eccfff6ef8aca07572c771bcea4540ae1bd946c4f08824
43353ad073f69d394b60a74ff6c3ec776fdb2d5ef3c74e5e2e1608fb108621a9
035cec79e2a2f8110e521d5d58b8b905799505a87f287e80ec7b5597b278b3c1
3fef09ffc2157bac6bebbd27f6a8fcea7d2220c319514aa23f3e7ea0c13307a4
12a5e44260a0da4ce2e05fb02c7d004990f89cd30c80eca9fabe2f3ca09c5d6c
5329ef2334622fde7f10c1963e19bd0a4fdaf39477b377be19cdcdc4b8b95fa9
3fc6ae2d0c872e17be8444e6eb8197923c3f91372e5261e59d79b49983ef62d5
732d59e95be946b589ffaa98f096bc51a8c0babf99f903303db1aca0645e4eee
50ef4ed6a0aee7fda4d21df7a566bea1fc4eb1efe567affbc41795c9f044fa09
7.4.4.1. Valid Single Message Proof

Using the header, message and signature used in Valid Single Message Signature to create a proof disclosing the message, with the following presentation header

bed231d880675ed101ead304512e043ade9958dd0241ea70b4b3957fba941501

will result to the following proof value

8acd61a806203fb1c5203c4d90d92e8dfb1b7706cd9fc6e4233116204e9bfb96b0b0293f
4b7c3fac69229e62c9e2bf36a9052cce6cc4ed37ebfbc3a45e45f77a87c2d4f90dc88aae
23433b761f420debdfd2041057dc57f5cdf945c4e1df729cace4a3043f1b832731362434
a0ab77086be5750a18505eb96422b9ff9fecf325197898760a4304af699e3d35ee996920
48b58e5864da380772e16fd3e339b05b334f900a0b663b329379713ae925dbdc5dfa2490
c7ebf390ec7d39e1bdfd1c1e3c8062d5254e683d46003cf5bf4a9366607d1e5c4ed120b4
e9a7776d205c83aac9559ff1110ee4550801abdb5ea48a9d33514b9afb2fbc9eaca94ed1
af5795ee5dec1664dc38ec908b4b7dd92cfd6f995c6bc436842be7608437c813b812220e
fe6a06b780cfaf8a57214319c0618915
7.4.4.2. Valid Multi-Message, All Messages Disclosed Proof

Using the header, messages and signature used in Valid Multi Message Signature to create a proof disclosing all the messages, with the following presentation header

bed231d880675ed101ead304512e043ade9958dd0241ea70b4b3957fba941501

will result to the following proof value

af210c6571df52d805fa17620bf1a88dbcfb23829b5af59a86b9f4bc931d72942a94edfa
aa88fa2363dce155ec70a2368e9b01eef49ec11f13fe4bb6b730bbec6b0cce4c3e7a0705
fb57218563ec997d31daf49ad2b52621c03b83af8568b0a1a4daa67c99b04482f7556fb4
5f892e90ee0383564eed3ef199db76189d575c97307b02cf1fc8e384357f7c14ef308732
287ae4e96c6f371e6864f6527542895e28ef39c8354ebb0174958212aba8da360fc6d5be
d9faabad83601d8035cf8b86ab8b1a2a4984bbe09f653d68e06af0952c3a78e9a47d2b20
c626e13a33a7830f147a41d306b3dcb97488d46cd561312c112ba29eb82bda43f452b255
627210c2c4d9197be6bbaa9e5113617716caa6a25f6e297ccd4a6d716bdd9d258f9dc529
477098cd69b6282ff351c21e35c19dc8
7.4.4.3. Valid Multi-Message, Half of Messages Disclosed Proof

Using the same header, messages and signature as in Multi-Message, All Messages Disclosed Proof but this time with only every other messages disclosed (messages in index 0, 2, 4 and 6, in that order), with the following presentation header

bed231d880675ed101ead304512e043ade9958dd0241ea70b4b3957fba941501

will result to the following proof value

8733f60b98294aea82f8cc2994203a5ff630a50147d5aca82f41f26cbb4425e9b23b4187
4110d4f5de1e7c2db5945dc88e2f0c1ac96a03ccb3f6fd5759799302f100db5c14975eb6
8331442a99544c096b18efc9500ece042e628303faf7fa0f91047bc8295d97953bb8a1c0
34f17963ba70eff00eea8e41d1c4218a42132b536dc22ee56405f8c4f8a9576bb206aabc
66052fc0e9ce161349966b9c257137eddef48b33a87fb4e492376e54dabe7b256523e671
0cee7f117679943b4768faf4c516cb656cbc85199d9b4f51472c5b4464dda241332c4501
b6fcae13c746e460e0478f241837efa80d87151dd72c57b664faaa912fe781ad4589d67c
cb86270aadcc8f8786052d5599f902640f0d1de55f188b3e5f077841fdd6379e7b27df42
b0069df43700eb5381aba2b2ba9d74890fc710a17567ec0b8052282d68a61eafd289f476
7f0a927b6a1c6e6b2ce7546928cbd5c2e61407a76654d0ed19102effb8330d883a40af5c
9cd6bb2e15103c5733b0eba1cc7ec617ceabd65beb8dee3abb2bd32f584c5cd3ff0637fd
caa700212548816512cbbb5e218ff74cf6f6ae8e327b9e29d5e578c400ca334ba0e1e176
33215c59152d3c933eb9db6ca954558df5a2bc211e8f6e6b7a779a6c46222c1e6ec129d7
d38aad9a9eff5a1bc0cef0e87cb58205f86c8c92f01fe04c4805aba3

7.5. BLS12381-SHA-256 Test Vectors

Test vectors of the BLS12-381-SHA-256 ciphersuite. Further fixtures are available in additional BLS12-381-SHA-256 test vectors.

7.5.1. Map Messages to Scalars

Similarly to how messages are mapped to scalars in BLS12381-SHAKE-256 Test Vectors, we are using the MapMessageToScalarAsHash operation to map each message to a scalar. For the BLS12-381-SHA-256 ciphersuite, on input each message in Section 3.2.2 and the following default dst

4242535f424c53313233383147315f584d443a5348412d3235365f535357555f524f5f4d
41505f4d53475f544f5f5343414c41525f41535f484153485f

The output scalars, encoded to octets using I2OSP and represented in big endian order, are the following,

0e95c55a6ba91b0ed5e9425151dca52fff8748d935e780c828ad00031b93ed7f

1b8a006679df6534aca94caf0fed58234b1d7f575a2646308e6c9d5fdf4bba60

0060ba23303163460a943404fa505b5e039bb11d6efd3689560cc9985094d0c2

4380b070a45f309c3abed92324a15a8a6ccdc6972f9735e043e267745b50b3a0

6df7849922283ab15f3dfe1b4699f33d5820acf5dede3e48e33df5e7fcf3762c

0e1aa2ed096260ebd262673b5d3613c44371374849b9f3dd25c456a41f56ecc1

4ceec5a33e7c25c95e6234825b013f846243f492805a81a65b242c2422b516e6

05dfbcc38db8c56cd638903805a0068be05c8201afebc04926b6332f44ff46f0

313750e2398ea3547d558aa8d25ad2426c8cea82d68d9f159f08c72223e1673a

364dd864673c8b33ebd7a1f8a1249f5735c757f08e3c94e2265b61a019cb4bd3

Note that in both the following test vectors, as well as the additional BLS12-381-SHA-256 test vectors in Appendix C.2, when we are referring to a message that will be passed to one of the Sign, Verify, ProofGen or ProofVerify operations, we assume that it will first be mapped into one of the above scalars, using the MapMessageToScalarAsHash operation.

7.5.2. Message Generators

Following the procedure defined in Section 4.2 with an input count value of 12, for the BLS12-381-SHA-256 suite, outputs the following values (note that the first 2 correspond to Q_1 and Q_2, while the next 10, to the message generators H_1, ..., H_10).

b57ec5e001c28d4063e0b6f5f0a6eee357b51b64d789a21cf18fd11e73e73577910182d4
21b5a61812f5d1ca751fa3f0

909573cbb9da401b89d2778e8a405fdc7d504b03f0158c31ba64cdb9b648cc35492b18e5
6088b44c8b4dc6310afb5e49

90248350d94fd550b472a54269e28b680757d8cbbe6bb2cb000742c07573138276884c28
72a8285f4ecf10df6029be15

8fb7d5c43273a142b6fc445b76a8cdfc0f96c5fdac7cdd73314ac4f7ec4990a0a6f28e4a
d97fb0a3a22efb07b386e3ff

8241e3e861aaac2a54a8d7093301143d7d3e9911c384a2331fcc232a3e64b4882498ce4d
9da8904ffcbe5d6eadafc82b

99bb19d202a4019c14a36933264ae634659994076bf02a94135e1026ea309c7d3fd6da60
c7929d30b656aeaba7c0dcec

81779fa5268e75a980799c0a01677a763e14ba82cbf0a66c653edc174057698636507ac5
8e73522a59585558dca80b42

98a3f9af71d391337bc6ae5d26980241b6317d5d71570829ce03d63c17e0d2164e1ad793
645e1762bfcc049a17f5994b

aca6a84770bb1f515591b4b95d69777856ddc52d5439325839e31ce5b6237618a9bc01a0
4b0057d33eab14341504c7e9

b96e206d6cf32b51d2f4d543972d488a4c4cbc5d994f6ebb0bdffbc5459dcb9a8e5ab045
c5949dc7eb33b0545b62aae3

8edf840b56ecf8d7c5a9c4a0aaf8a5525f3480df735743298dd2f4ae1cbb56f56ed6a04e
f6fa7c92cd68d9101c7b8c8f

86d4ae04738dc082eb37e753bc8ec35a8d982e463559214d0f777599f71aa1f95780b3dc
cbdcae45e146e5c7623dfe7d

7.5.3. Signature Fixtures

7.5.3.1. Valid Single Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following message (the first message defined in Section 3.2.2)

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

After it is mapped to the first scalar in Section 7.5.1, along with the SK value as defined in Section 7.2 as inputs into the Sign operations, yields the following output signature

a7386ffaa4e70a9a44483adccc202a658e1c1f02190fb95bfd0f826a0188d73ab910c556
fb3c1d9e212dea3c5e9989271a5e578c4625d290a0e7f2355eabe7584af5eb822c72319e
588b2c20cd1e8256698d6108f599c2e48cf1be8e4ebfaf7ae397a5733a498d3d466b843c
027311bb
7.5.3.2. Valid Multi-Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the messages defined in Section 3.2.2 (Note the ordering of the messages MUST be preserved), after they are mapped to the scalars in Section 7.5.1, along with the SK value as defined in Section 7.2 as inputs into the Sign operations, yields the following output signature

b058678021dba2313c65fadc469eb4f030264719e40fb93bbf68bdf79079317a0a361932
88b7dcb983fae0bc3e4c077f145f99a66794c5d0510cb0e12c0441830817822ad4ba7406
8eb7f34eb11ce3ee606d86160fecd844dda9d04bed759a676b0c8868d3f97fbe2e8b5741
69bd73a3

7.5.4. Proof fixtures

Similarly to the proof fixtures for the BLS12381-SHA-256 ciphersuite, the generation of the following fixtures uses the mocked_calculate_random_scalars defined in Mocked Random Scalars, in place of the calculate_random_scalars operation, with the following seed value (hex encoding of utf8("<30 first digits of pi>"))

SEED = "332e313431353932363533353839373933323338343632363433333833323739"

Given the above seed the first 10 scalars returned by the mocked_calculate_random_scalars operation will be,

41b5e116922813fab50e1bcafd5a68f38c977fe4b01b3992424bc4ff1f1490bc
57062c3eb0b030cbb45535bc7e8b3756288cfeee52ab6e2d1a56aedcfee668ba
20a1f16c18342bc8650655783cd87b4491ce3986d0942e863d62053914bb3da1
21ba43b4e1da365c6062b8cb00e3c22b0d49d68e30fae8a21ff9a476912a49ee
2d34df08a57d8d7c6d3a8bdd34f45f0db539a4fc17b3e8948cb36360190248ed
4840669faf2ab03e2b8a80d3ebc597cabfe35642680cec12f622daf63529be52
3151326acfc6ec15b68ce67d52ce75abbe17d4224e78abb1c31f410f5664fc1a
4cb74272bc2673959a3c72d992485057b1312cd8d2bf32747741324a92152c81
2af0ebadecd3e43aefaafcfd3f426dca179140cdaf356a838381e584dfa0e4d1
3aa6190cb2ae26ba433c3f6ff01504088cead97687f417f4bc80ac906201356c
7.5.4.1. Valid Single Message Proof

Using the header, message and signature used in Valid Single Message Signature to create a proof disclosing the message, with the following presentation header

bed231d880675ed101ead304512e043ade9958dd0241ea70b4b3957fba941501

will result to the following proof value

99b6215be8357400353057b57b440e3998c259d34bce12e1d24dc7f9b63762122d4144ca
cefc5f3231172308907e3f2c8cf98d238dccf7e1eecf66441f27a7e140fc1a11788f24c6
34c5e4e6675c904670be71cdd44e613d1436f6badc4d9f31b6b575ab7a165dd120bb97d2
b5a481f43e202477fdf5798af07c6ee639c80b3ec83c727cbe4a98da6c2966489524c26e
3d84d7985370e3628271ec8cf5dafcb0e39de2d90f6fcdd2b72f2793e6cb985f60143f2a
320e875036b5a0bb85e8548b531f2b60f3f9ed5b3d490eecd9ae44916098e8f293efeeef
fe51ed4cac07bb46677b65f7de0ab3096f5ab39b4bcc187d25a14520bbf0cfe1c861bda6
3e0afdd2c030e4862b52cdaee5d6d9ace784493a576d96a3e0b29205aeaa2fea8bd5888e
ead49c7b06bba9c7d642260887756cd7
7.5.4.2. Valid Multi-Message, All Messages Disclosed Proof

Using the header, messages and signature used in Valid Multi Message Signature to create a proof disclosing all the messages, with the following presentation header

bed231d880675ed101ead304512e043ade9958dd0241ea70b4b3957fba941501

will result to the following proof value

af210c6571df52d805fa17620bf1a88dbcfb23829b5af59a86b9f4bc931d72942a94edfa
aa88fa2363dce155ec70a2368e9b01eef49ec11f13fe4bb6b730bbec6b0cce4c3e7a0705
fb57218563ec997d31daf49ad2b52621c03b83af8568b0a1a4daa67c99b04482f7556fb4
5f892e90ee0383564eed3ef199db76189d575c97307b02cf1fc8e384357f7c14ef308732
287ae4e96c6f371e6864f6527542895e28ef39c8354ebb0174958212aba8da360fc6d5be
d9faabad83601d8035cf8b86ab8b1a2a4984bbe09f653d68e06af0952c3a78e9a47d2b20
c626e13a33a7830f147a41d306b3dcb97488d46cd561312c112ba29eb82bda43f452b255
627210c2c4d9197be6bbaa9e5113617716caa6a25f6e297ccd4a6d716bdd9d258f9dc529
477098cd69b6282ff351c21e35c19dc8
7.5.4.3. Valid Multi-Message, Half of Messages Disclosed Proof

Using the same header, messages and signature as in Multi-Message, All Messages Disclosed Proof but this time with only every other messages disclosed (messages in index 0, 2, 4 and 6, in that order), with the following presentation header

bed231d880675ed101ead304512e043ade9958dd0241ea70b4b3957fba941501

will result to the following proof value

8ee5a0c7fc62e6058bfac10b1489cb872283faee59c4132a076f01660eb3f28dd03fcf44
fb8dadf8794e314a33b6b84cb95bfd630da6fe9f10b818b51f205d08143ea55bc05f6ad8
5a332b2acb3567c9134aeb29b9fa1e26ba8db63f956949ff846e9ff2cccfee820c4ffaf1
aaa161cf04af8b7f27bede66c42f18c9289007972f0f0230f4cda28beb5885aa71bcbe9b
27d4dca32aae82f02961e982bb7f50483924087180f9ca76efdd1b3534b5b393614b5107
0a6f5d088fb464ccb2d296ccb69e31ef0f84d25f286186a6ab36ce4a257eacf0c7e3ad36
2ae00738d876999f44228c085ffd0a97961280c05113ed21075115770819d9afbcb40d4f
ae6c40e3d66a324637d3b1b79e5abd86fb3a1a8d3404ffa0019cacdf988f065009fe8bb2
7fd99e804ab679c96fe559bbf2e3a95b2183b54eb4238c4a268e04c51036dd24139c6d00
1698614484d285e55e3911af18af4fc1b241f2f168565ffa74dc082aaf15d7b82cc59889
6ad34efe960bbcb06cea9ee551d65080cae87181e50463b9348cbfb05f5242174197b3d3
4efa56f513fc11cb31591d199e61af4f46bcbcca67d46cd16e2ec83694767780e0c8ccbc
70d7fc61c0bda6209e22d17049e90e61c940104ca0cc69310393dc14b6c2b51221925778
2c19e185e3bbc85cfe0bc432a91082fd148044fbd14092702bd39e81

8. IANA Considerations

This document does not make any requests of IANA.

9. Acknowledgements

The authors would like to acknowledge the significant amount of academic work that preceeded the development of this document. In particular the original work of [BBS04] which was subsequently developed in [ASM06] and in [CDL16]. This last academic work is the one mostly used by this document.

The current state of this document is the product of the work of the Decentralized Identity Foundation Applied Cryptography Working group, which includes numerous active participants. In particular, the following individuals contributed ideas, feedback and wording that influenced this specification:

Orie Steele, Christian Paquin, Alessandro Guggino and Tomislav Markovski

10. Normative References

[DRBG]
NIST, "Recommendation for Random Number Generation Using Deterministic Random Bit Generators", <https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf>.
[I-D.irtf-cfrg-hash-to-curve]
Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., and C. A. Wood, "Hashing to Elliptic Curves", Work in Progress, Internet-Draft, draft-irtf-cfrg-hash-to-curve-16, , <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16>.
[I-D.irtf-cfrg-pairing-friendly-curves]
Sakemi, Y., Kobayashi, T., Saito, T., and R. S. Wahby, "Pairing-Friendly Curves", Work in Progress, Internet-Draft, draft-irtf-cfrg-pairing-friendly-curves-11, , <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-pairing-friendly-curves-11>.
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/info/rfc2119>.
[RFC4086]
Eastlake 3rd, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, DOI 10.17487/RFC4086, , <https://www.rfc-editor.org/info/rfc4086>.
[RFC5869]
Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)", RFC 5869, DOI 10.17487/RFC5869, , <https://www.rfc-editor.org/info/rfc5869>.
[RFC8017]
Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, , <https://www.rfc-editor.org/info/rfc8017>.
[RFC8937]
Cremers, C., Garratt, L., Smyshlyaev, S., Sullivan, N., and C. Wood, "Randomness Improvements for Security Protocols", RFC 8937, DOI 10.17487/RFC8937, , <https://www.rfc-editor.org/info/rfc8937>.
[SHA2]
NIST, "Secure Hash Standard (SHS)", <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf>.
[SHA3]
NIST, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf>.

11. Informative References

[ADR02]
An, J. H., Dodis, Y., and T. Rabin, "On the Security of Joint Signature and Encryption", pages 83-107, , <https://doi.org/10.1007/3-540-46035-7_6>.
[ASM06]
Au, M. H., Susilo, W., and Y. Mu, "Constant-Size Dynamic k-TAA", Springer, Berlin, Heidelberg, , <https://link.springer.com/chapter/10.1007/11832072_8>.
[BBS04]
Boneh, D., Boyen, X., and H. Shacham, "Short Group Signatures", pages 41-55, , <https://link.springer.com/chapter/10.1007/978-3-540-28628-8_3>.
[Bowe19]
Bowe, S., "Faster subgroup checks for BLS12-381", , <https://eprint.iacr.org/2019/814>.
[CDL16]
Camenisch, J., Drijvers, M., and A. Lehmann, "Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited", Springer, Cham, , <https://eprint.iacr.org/2016/663.pdf>.
[HDWH12]
Heninger, N., Durumeric, Z., Wustrow, E., and J.A. Halderman, "Mining your Ps and Qs: Detection of widespread weak keys in network devices", pages 205-220, , <https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf>.
[I-D.irtf-cfrg-bls-signature]
Boneh, D., Gorbunov, S., Wahby, R. S., Wee, H., Wood, C. A., and Z. Zhang, "BLS Signatures", Work in Progress, Internet-Draft, draft-irtf-cfrg-bls-signature-05, , <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-05>.
[ZCASH-REVIEW]
NCC Group, "Zcash Overwinter Consensus and Sapling Cryptography Review", <https://research.nccgroup.com/wp-content/uploads/2020/07/NCC_Group_Zcash2018_Public_Report_2019-01-30_v1.3.pdf>.

Appendix A. BLS12-381 hash_to_curve definition using SHAKE-256

The following defines a hash_to_curve suite [I-D.irtf-cfrg-hash-to-curve] for the BLS12-381 curve for both the G1 and G2 subgroups using the extendable output function (xof) of SHAKE-256 as per the guidance defined in section 8.9 of [I-D.irtf-cfrg-hash-to-curve].

Note the notation used in the below definitions is sourced from [I-D.irtf-cfrg-hash-to-curve].

A.1. BLS12-381 G1

The suite of BLS12381G1_XOF:SHAKE-256_SSWU_RO_ is defined as follows:

* encoding type: hash_to_curve (Section 3 of
                 [@!I-D.irtf-cfrg-hash-to-curve])

* E: y^2 = x^3 + 4

* p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f624
     1eabfffeb153ffffb9feffffffffaaab

* r: 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

* m: 1

* k: 128

* expand_message: expand_message_xof (Section 5.3.2 of
                  [@!I-D.irtf-cfrg-hash-to-curve])

* hash: SHAKE-256

* L: 64

* f: Simplified SWU for AB == 0 (Section 6.6.3 of
     [@!I-D.irtf-cfrg-hash-to-curve])

* Z: 11

*  E': y'^2 = x'^3 + A' * x' + B', where

      -  A' = 0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aef
                d881ac98936f8da0e0f97f5cf428082d584c1d

      -  B' = 0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14f
                cef35ef55a23215a316ceaa5d1cc48e98e172be0

*  iso_map: the 11-isogeny map from E' to E given in Appendix E.2 of
            [@!I-D.irtf-cfrg-hash-to-curve]

*  h_eff: 0xd201000000010001

Note that the h_eff values for this suite are copied from that defined for the BLS12381G1_XMD:SHA-256_SSWU_RO_ suite defined in section 8.8.1 of [I-D.irtf-cfrg-hash-to-curve].

An optimized example implementation of the Simplified SWU mapping to the curve E' isogenous to BLS12-381 G1 is given in Appendix F.2 [I-D.irtf-cfrg-hash-to-curve].

Appendix B. Use Cases

B.1. Non-correlating Security Token

In the most general sense BBS signatures can be used in any application where a cryptographically secured token is required but correlation caused by usage of the token is un-desirable.

For example in protocols like OAuth2.0 the most commonly used form of the access token leverages the JWT format alongside conventional cryptographic primitives such as traditional digital signatures or HMACs. These access tokens are then used by a relying party to prove authority to a resource server during a request. However, because the access token is most commonly sent by value as it was issued by the authorization server (e.g in a bearer style scheme), the access token can act as a source of strong correlation for the relying party. Relevant prior art can be found here.

BBS Signatures due to their unique properties removes this source of correlation but maintains the same set of guarantees required by a resource server to validate an access token back to its relevant authority (note that an approach to signing JSON tokens with BBS that may be of relevance is the JWP format and serialization). In the context of a protocol like OAuth2.0 the access token issued by the authorization server would feature a BBS Signature, however instead of the relying party providing this access token as issued, in their request to a resource server, they generate a unique proof from the original access token and include that in the request instead, thus removing this vector of correlation.

B.2. Improved Bearer Security Token

Bearer based security tokens such as JWT based access tokens used in the OAuth2.0 protocol are a highly popular format for expressing authorization grants. However their usage has several security limitations. Notably a bearer based authorization scheme often has to rely on a secure transport between the authorized party (client) and the resource server to mitigate the potential for a MITM attack or a malicious interception of the access token. The scheme also has to assume a degree of trust in the resource server it is presenting an access token to, particularly when the access token grants more than just access to the target resource server, because in a bearer based authorization scheme, anyone who possesses the access token has authority to what it grants. Bearer based access tokens also suffer from the threat of replay attacks.

Improved schemes around authorization protocols often involve adding a layer of proof of cryptographic key possession to the presentation of an access token, which mitigates the deficiencies highlighted above as well as providing a way to detect a replay attack. However, approaches that involve proof of cryptographic key possession such as DPoP (https://datatracker.ietf.org/doc/html/draft-ietf-oauth-dpop-04) suffer from an increase in protocol complexity. A party requesting authorization must pre-generate appropriate key material, share the public portion of this with the authorization server alongside proving possession of the private portion of the key material. The authorization server must also be-able to accommodate receiving this information and validating it.

BBS Signatures ofter an alternative model that solves the same problems that proof of cryptographic key possession schemes do for bearer based schemes, but in a way that doesn't introduce new up-front protocol complexity. In the context of a protocol like OAuth2.0 the access token issued by the authorization server would feature a BBS Signature, however instead of the client providing this access token as issued, in their request to a resource server, they generate a unique proof from the original access token and include that in the request instead. Because the access token is not shared in a request to a resource server, attacks such as MITM are mitigated. A resource server also obtains the ability to detect a replay attack by ensuring the proof presented is unique.

B.3. Selectively Disclosure Enabled Identity Credentials

BBS signatures when applied to the problem space of identity credentials can help to enhance user privacy. For example a digital drivers license that is cryptographically signed with a BBS signature, allows the holder or subject of the license to disclose different claims from their drivers license to different parties. Furthermore, the unlinkable presentations property of proofs generated by the scheme remove an important possible source of correlation for the holder across multiple presentations.

Appendix C. Additional Test Vectors

NOTE These fixtures are a work in progress and subject to change

C.1. BLS12-381-SHAKE-256 Ciphersuite

C.1.1. Modified Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following message (the first message defined in Section 3.2.2)

c344136d9ab02da4dd5908bbba913ae6f58c2cc844b802a6f811f5fb075f9b80

After is mapped to the first scalar in Section 7.4.1, and with the following signature

a7386ffaa4e70a9a44483adccc202a658e1c1f02190fb95bfd0f826a0188d73ab910c556
fb3c1d9e212dea3c5e9989271a5e578c4625d290a0e7f2355eabe7584af5eb822c72319e
588b2c20cd1e8256698d6108f599c2e48cf1be8e4ebfaf7ae397a5733a498d3d466b843c
027311bb

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to the message value being different from what was signed

C.1.2. Extra Unsigned Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following messages (the two first messages defined in Section 3.2.2)

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

87a8bd656d49ee07b8110e1d8fd4f1dcef6fb9bc368c492d9bc8c4f98a739ac6

After they are mapped to the first 2 scalars in Section 7.4.1, and with the following signature (which is a signature to only the first of the above two messages)

a7386ffaa4e70a9a44483adccc202a658e1c1f02190fb95bfd0f826a0188d73ab910c556
fb3c1d9e212dea3c5e9989271a5e578c4625d290a0e7f2355eabe7584af5eb822c72319e
588b2c20cd1e8256698d6108f599c2e48cf1be8e4ebfaf7ae397a5733a498d3d466b843c
027311bb

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to an additional message being supplied that was not signed.

C.1.3. Missing Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following messages (the two first messages defined in Section 3.2.2)

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

87a8bd656d49ee07b8110e1d8fd4f1dcef6fb9bc368c492d9bc8c4f98a739ac6

After they are mapped to the first 2 scalars in Section 7.4.1, and with the following signature (which is a signature on all the messages defined in Section 3.2.2)

ae0587beb6b307f847eaf654f74177de4689b46c6d2b3eca6a6a80c798db78b0ccc25196
6debb500ec7fee8ca382bcc925860a0030570b2b56eb39868215b3b1ca1ab1ad9cdd5bac
cc8825f8133f12a4288c875e7f1aedc5861d7f3e45542e456425c632c9a82f4cc0b237e3
b603b1b6

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to missing messages that were originally present during the signing.

C.1.4. Reordered Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following messages (re-ordering of the messages defined in Section 3.2.2)

c344136d9ab02da4dd5908bbba913ae6f58c2cc844b802a6f811f5fb075f9b80

7372e9daa5ed31e6cd5c825eac1b855e84476a1d94932aa348e07b7320912416

77fe97eb97a1ebe2e81e4e3597a3ee740a66e9ef2412472c23364568523f8b91

496694774c5604ab1b2544eababcf0f53278ff5040c1e77c811656e8220417a2

515ae153e22aae04ad16f759e07237b43022cb1ced4c176e0999c6a8ba5817cc

d183ddc6e2665aa4e2f088af9297b78c0d22b4290273db637ed33ff5cf703151

ac55fb33a75909edac8994829b250779298aa75d69324a365733f16c333fa943

96012096adda3f13dd4adbe4eea481a4c4b5717932b73b00e31807d3c5894b90

87a8bd656d49ee07b8110e1d8fd4f1dcef6fb9bc368c492d9bc8c4f98a739ac6

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

After they are mapped to the corresponding scalars in Section 7.4.1, and with the following signature

ae0587beb6b307f847eaf654f74177de4689b46c6d2b3eca6a6a80c798db78b0ccc25196
6debb500ec7fee8ca382bcc925860a0030570b2b56eb39868215b3b1ca1ab1ad9cdd5bac
cc8825f8133f12a4288c875e7f1aedc5861d7f3e45542e456425c632c9a82f4cc0b237e3
b603b1b6

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to messages being re-ordered from the order in which they were signed

C.1.5. Wrong Public Key Signature

Using the following header

11223344556677889900aabbccddeeff

And the messages as defined in Section 3.2.2, mapped to the scalars in Section 7.4.1 and with the following signature

ae0587beb6b307f847eaf654f74177de4689b46c6d2b3eca6a6a80c798db78b0ccc25196
6debb500ec7fee8ca382bcc925860a0030570b2b56eb39868215b3b1ca1ab1ad9cdd5bac
cc8825f8133f12a4288c875e7f1aedc5861d7f3e45542e456425c632c9a82f4cc0b237e3
b603b1b6

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to public key used to verify is in-correct

C.1.6. Wrong Header Signature

Using the following header

ffeeddccbbaa00998877665544332211

And the messages as defined in Section 3.2.2, mapped to the scalars in Section 7.4.1 and with the following signature

ae0587beb6b307f847eaf654f74177de4689b46c6d2b3eca6a6a80c798db78b0ccc25196
6debb500ec7fee8ca382bcc925860a0030570b2b56eb39868215b3b1ca1ab1ad9cdd5bac
cc8825f8133f12a4288c875e7f1aedc5861d7f3e45542e456425c632c9a82f4cc0b237e3
b603b1b6

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to header value being modified from what was originally signed

C.1.7. Hash to Scalar Test Vectors

Using the following input message,

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

And the default dst defined in hash_to_scalar, i.e.,

4242535f424c53313233383147315f584f463a5348414b452d3235365f535357555f524f
5f4832535f

We get the following scalar, encoded with I2OSP and represented in big endian order,

619db5f43cc92d3f5bd71502b99791bc1022c3eced4f1e3058a9c191af0118a4

C.2. BLS12-381-SHA-256 Ciphersuite

C.2.1. Modified Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following message (the first message defined in Section 3.2.2)

c344136d9ab02da4dd5908bbba913ae6f58c2cc844b802a6f811f5fb075f9b80

After is maped to the first scalar in Section 7.5.1, and with the following signature

8fb17415378ec4462bc167be75583989e0528913da142239848ae88309805bfb3656bcff
322e5d8fd1a7e40a660a62266099f27fa81ff5010443f36285f6f0758e4d701c444b2044
7cded906a3f2001714087f165f760369b901ccbe5173438b32ad195b005e2747492cf002
cf51e498

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to the message value being different from what was signed.

C.2.2. Extra Unsigned Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following messages (the two first messages defined in Section 3.2.2)

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

87a8bd656d49ee07b8110e1d8fd4f1dcef6fb9bc368c492d9bc8c4f98a739ac6

After they are mapped to the first 2 scalars in Section 7.5.1, and with the following signature (which is a signature to only the first of the above two messages)

8fb17415378ec4462bc167be75583989e0528913da142239848ae88309805bfb3656bcff
322e5d8fd1a7e40a660a62266099f27fa81ff5010443f36285f6f0758e4d701c444b2044
7cded906a3f2001714087f165f760369b901ccbe5173438b32ad195b005e2747492cf002
cf51e498

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to an additional message being supplied that was not signed.

C.2.3. Missing Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following messages (the two first messages defined in Section 3.2.2)

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

87a8bd656d49ee07b8110e1d8fd4f1dcef6fb9bc368c492d9bc8c4f98a739ac6

After they are mapped to the first 2 scalars in Section 7.5.1, and with the following signature (which is a signature on all the messages defined in Section 3.2.2)

b058678021dba2313c65fadc469eb4f030264719e40fb93bbf68bdf79079317a0a361932
88b7dcb983fae0bc3e4c077f145f99a66794c5d0510cb0e12c0441830817822ad4ba7406
8eb7f34eb11ce3ee606d86160fecd844dda9d04bed759a676b0c8868d3f97fbe2e8b5741
69bd73a3

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to missing messages that were originally present during the signing.

C.2.4. Reordered Message Signature

Using the following header

11223344556677889900aabbccddeeff

And the following messages (re-ordering of the messages defined in Section 3.2.2)

c344136d9ab02da4dd5908bbba913ae6f58c2cc844b802a6f811f5fb075f9b80

7372e9daa5ed31e6cd5c825eac1b855e84476a1d94932aa348e07b7320912416

77fe97eb97a1ebe2e81e4e3597a3ee740a66e9ef2412472c23364568523f8b91

496694774c5604ab1b2544eababcf0f53278ff5040c1e77c811656e8220417a2

515ae153e22aae04ad16f759e07237b43022cb1ced4c176e0999c6a8ba5817cc

d183ddc6e2665aa4e2f088af9297b78c0d22b4290273db637ed33ff5cf703151

ac55fb33a75909edac8994829b250779298aa75d69324a365733f16c333fa943

96012096adda3f13dd4adbe4eea481a4c4b5717932b73b00e31807d3c5894b90

87a8bd656d49ee07b8110e1d8fd4f1dcef6fb9bc368c492d9bc8c4f98a739ac6

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

After they are mapped to the corresponding scalars in Section 7.5.1, and with the following signature

b058678021dba2313c65fadc469eb4f030264719e40fb93bbf68bdf79079317a0a361932
88b7dcb983fae0bc3e4c077f145f99a66794c5d0510cb0e12c0441830817822ad4ba7406
8eb7f34eb11ce3ee606d86160fecd844dda9d04bed759a676b0c8868d3f97fbe2e8b5741
69bd73a3

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to messages being re-ordered from the order in which they were signed.

C.2.5. Wrong Public Key Signature

Using the following header

11223344556677889900aabbccddeeff

And the messages as defined in Section 3.2.2, mapped to the scalars in Section 7.5.1 and with the following signature

b058678021dba2313c65fadc469eb4f030264719e40fb93bbf68bdf79079317a0a361932
88b7dcb983fae0bc3e4c077f145f99a66794c5d0510cb0e12c0441830817822ad4ba7406
8eb7f34eb11ce3ee606d86160fecd844dda9d04bed759a676b0c8868d3f97fbe2e8b5741
69bd73a3

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to public key used to verify is in-correct.

C.2.6. Wrong Header Signature

Using the following header

ffeeddccbbaa00998877665544332211

And the messages as defined in Section 3.2.2, mapped to the scalars in Section 7.5.1 and with the following signature

b058678021dba2313c65fadc469eb4f030264719e40fb93bbf68bdf79079317a0a361932
88b7dcb983fae0bc3e4c077f145f99a66794c5d0510cb0e12c0441830817822ad4ba7406
8eb7f34eb11ce3ee606d86160fecd844dda9d04bed759a676b0c8868d3f97fbe2e8b5741
69bd73a3

Along with the PK value as defined in Section 7.2 as inputs into the Verify operation should fail signature validation due to header value being modified from what was originally signed.

C.2.7. Hash to Scalar Test Vectors

Using the following input message,

9872ad089e452c7b6e283dfac2a80d58e8d0ff71cc4d5e310a1debdda4a45f02

And the default dst defined in hash_to_scalar, i.e.,

4242535f424c53313233383147315f584d443a5348412d3235365f535357555f524f5f48
32535f

We get the following scalar, encoded with I2OSP and represented in big endian order,

669e7db2fcd926d6ec6ff14cbb3143f50cce0242627f1389d58b5cccbc0ef927

Appendix D. Proof Generation and Verification Algorithmic Explanation

The following section provides an explanation of how the ProofGen and ProofVerify operations work.

Let the prover be in possession of a BBS signature (A, e, s) on messages msg_1, ..., msg_L and a domain value (see Sign). Let A = B * (1/(e + SK)) where SK the signer's secret key and,

B = P1 + Q_1 * s + Q_2 * domain + H_1 * msg_1 + ... + H_L * msg_L

Let (i1, ..., iR) be the indexes of generators corresponding to messages the prover wants to disclose and (j1, ..., jU) be the indexes corresponding to undisclosed messages (i.e., (j1, ..., jU) = range(1, L) \ (i1, ..., iR)). To prove knowledge of a signature on the disclosed messages, work as follows,

Note that the verifier will know the elements in the left side of the above equations (i.e., C1 and C2) but not in the right side (i.e., s', r3 and the undisclosed messages: msg_j1, ..., msg_jU). However, using the nizk, the prover can convince the verifier that they (the prover) know the elements that satisfy those equations, without disclosing them. Then, if both EQ1 and EQ2 hold, and e(A', PK) = e(Abar, P2), an extractor can return a valid BBS signature from the signer's SK, on the disclosed messages. The proof returned is (A', Abar, D, nizk). To validate the proof, a verifier checks that e(A', PK) = e(Abar, P2) and verifies the nizk. Validating the proof, will guarantee the authenticity and integrity of the disclosed messages, as well as ownership of the undisclosed messages and of the signature.

Appendix E. Document History

-00

-01

-02

Authors' Addresses

Tobias Looker
MATTR
Vasilis Kalos
MATTR
Andrew Whitehead
Portage
Mike Lodder
CryptID