%%% Title = "draft-boneh-bls-signature-00.txt" abbrev = "BLS-signature" category = "info" docName = "draft-boneh-bls-signature-00.txt" ipr= "trust200902" workgroup = "CFRG"
date = 2019-02-08
[[author]] initials="D." surname="Boneh" fullname="Dan Boneh" organization="Stanford University" [author.address] email = "" [author.address.postal] city = "" country = "USA" [[author]] initials="S." surname="Gorbunov" fullname="Sergey Gorbunov" organization="Algorand and University of Waterloo" [author.address] email = "[email protected]" [author.address.postal] city = "Boston, MA" country = "USA" [[author]] initials="H." surname="Wee" fullname="Hoeteck Wee" organization="Algorand and ENS, Paris" [author.address] email = "[email protected]" [author.address.postal] city = "Boston, MA" country = "USA" [[author]] initials="Z." surname="Zhang" fullname="Zhenfei Zhang" organization="Algorand" [author.address] email = "[email protected]" [author.address.postal] city = "Boston, MA" country = "USA" %%%
.# Abstract
BLS is a digital signature scheme with compression properties. With a given set of signatures (sig_1, ..., sig_n) anyone can produce a compressed signature sig_compressed. The same is true for a set of private keys or public keys, while keeping the connection between sets (a compressed public key is associated to its compressed public key). Furthermore, the BLS signature scheme is deterministic, non-malleable, and efficient. Its simplicity and cryptographic properties allows it to be useful in a variety of use-cases, specifically when minimal storage space or bandwidth are required.
{mainmatter}
A signature scheme is a fundamental cryptographic primitive used on the Internet and beyond that is used to protect authenticity and integrity of communication. Only holder of the secret key can sign messages, but anyone can verify the signature using the associated public key.
Signature schemes are used in point-to-point secure communication protocols, PKI, remote connections, etc. Designing efficient and secure digital signature is very important for these applications.
This document describes the BLS signature scheme. The scheme enjoys a variety of important efficiency properties:
- The public key and the signatures are encoded as single group elements.
- Verification requires 2 pairing operations.
- A collection of signatures (signature_1, ..., signature_n) can be compressed into a single signature (signature). Moreover, the compressed signature can be verified using only n+1 pairings (as opposed to 2n pairings, when verifying naively n signatures).
Given the above properties,
the scheme enables many interesting applications. The immediate applications include
-
authentication and integrity for Public Key Infrastructure (PKI) and blockchains.
- The usage is similar to classical digital signatures, such as ECDSA.
-
compressing signature chains for PKI and Secure Border Gateway Protocol (SBGP).
- Concretely, in a PKI signature chain of depth n, we have n signatures by n certificate authorities on n distinct certificates. Similarly, in SBGP, each router receives a list of n signatures attesting to a path of length n in the network. In both settings, using the BLS signature scheme would allow us to compress the n signatures into a single signature.
-
consensus protocols for blockchains.
- There, BLS signatures are used for authenticating transactions as well as votes during the consensus protocol, and the use of aggregation significantly reduces the bandwidth and storage requirements.
The following comparison assumes BLS signatures with curve BLS12-381, targeting 128 bits security.
For 128 bits security, ECDSA takes 37 and 79 micro-seconds to sign and verify a signature on a typical laptop. In comparison, for the same level of security, BLS takes 370 and 2700 micro-seconds to sign and verify a signature.
In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes for signatures; while BLS uses 96 bytes for public keys, and 48 bytes for signatures. Alternatively, BLS can also be instantiated with 48 bytes of public keys and 96 bytes of signatures. BLS also allows for signature compression. In other words, a single signature is sufficient to anthenticate multiple messages and public keys.
The following terminology is used through this document:
-
SK: The private key for the signature scheme.
-
PK: The public key for the signature scheme.
-
message: The input to be signed by the signature scheme.
-
signature: The digital signature output.
-
compression: Given a list of signatures for a list of messages and public keys, generate a new signature that authenticates the same list of messages and public keys.
Like most signature schemes, BLS comes with the following API:
-
a key generation algorithm that generates a public key PK and a private key SK
KeyGen() -> PK, SK -
a sign algorithm that generates a deterministic signature for a message and a secret key
Sign(SK, message) -> signature
- a verification algorithm that outputs VALID if signature is a valid signature of message, and INVALID otherwise.
Verify(PK, message, signature) -> VALID or INVALID
We require that SK, PK, signature and message are octet strings.
An aggregatable signature scheme includes an algorithm that allows to compress a collection of signatures into a short signature.
Aggregate((PK_1, signature_1), ..., (PK_n, signature_n)) -> signature
Note that the aggregator does not need to know the messages corresponding to individual signatures.
The scheme also includes an algorithm to verify an aggregated signature, given a collection of corresponding public keys, the aggregated signature, and one or more messages.
Verify-Aggregated((PK_1, message_1), ..., (PK_n, message_n), signature) -> VALID or INVALID
that outputs VALID if signature is a valid aggregated signature of messages message_1, ..., message_n, and INVALID otherwise.
The verification algorithm may also accept a simpler interface that allows to verify an aggregate signature of the same message. That is, message_1 = message_2 = ... = message_n.
Verify-Aggregated(PK_1, ..., PK_n, message, signature) -> VALID or INVALID
This draft has the following dependencies:
- it relies on the [I-D.irtf-cfrg-hash-to-curve] for methods to convert binary strings into group elements
- it relies on [I-D.pairing-friendly-curves] for pairings and related operations.
BLS signatures require pairing-friendly curves given by e : G1 x G2 -> GT, where G1, G2 are prime-order subgroups of elliptic curve groups E1, E2. This draft suggests to use curve BLS12-381 as described in [I-D.pairing-friendly-curves]. Support of other curves SHALL be defined in extensions or future versions of this draft, or in separate documents.
There are two variants of the scheme:
-
(minimizing signature size) Use G1 to host data types of signatures and G2 for public keys, where G1/E1 has the more compact representation. For instance, when instantiated with the pairing-friendly curve BLS12-381, this yields signature size of 48 bytes, whereas the ECDSA signature over curve25519 has a signature size of 64 byes.
-
(minimizing public key size) Use G1 to host data types of public keys and G2 for signatures. This latter case comes up when we do signature aggregation, where most of the communication costs come from public keys. This is particularly relevant in applications such as blockchains and compressing certificate chains, where the goal is to minimize the total size of multiple public keys and aggregated signatures.
The rest of the write-up assumes the first variant. It is straightforward to obtain algorithms for the second variant from those of the first variant where we simply swap G1,E1 with G2,E2 respectively.
Notation and primitives used:
-
E1, E2 - elliptic curves (EC) defined over a field
-
P1, P2 - elements of E1,E2 of prime order r
-
G1, G2 - prime-order subgroups of E1, E2 generated by P1, P2
-
GT - order r subgroup of the multiplicative group over a field
-
We require an efficient pairing: (G1, G2) -> GT that is bilinear and non-degenerate.
-
Elliptic curve operations in E1 and E2 are written in additive notation, with P+Q denoting point addition and x*P denoting scalar multiplication of a point P by a scalar x.
TBD: [I-D.pairing-friendly-curves] uses the notation x[P].
-
Field operations in GT are written in multiplicative notation, with a*b denoting field element multiplication.
-
|| - octet string concatenation
-
domain_separator - an identifier for the ciphersuite. In current draft "BLS12_381-SHA384-try_and_increment". Future identifiers MUST include an identifier of the curve, for example BLS12-381, an identifier of the hash function, for example SHA512, and the algorithm in use, for example, try-and-increment.
Type conversions:
-
int_to_string(a, len) - conversion of nonnegative integer a to octet string of length len.
-
string_to_int(a_string) - conversion of octet string a_string to nonnegative integer.
-
E1_to_string - conversion of E1 point to octet string
-
string_to_E1 - conversion of octet string to E1 point. Returns INVALID if the octet string does not convert to a valid E1 point.
Hashing Algorithms
- hash_to_G1 - cryptographic hashing of octet string to G1 element. Must return a valid G1 element. Specified in Section {{auxiliary}}.
Output: PK, SK
- SK = x, chosen as a random integer in the range 1 and r-1
- PK = x*P2
- Output PK, SK
Input: SK = x, message Output: signature
- Input a secret key SK = x and a message digest message
- H = hash_to_G1(suite_string, message)
- Gamma = x*H
- signature = E1_to_string(Gamma)
- Output signature
Input: PK, message, signature Output: "VALID" or "INVALID"
- H = hash_to_G1(suite_string, message)
- Gamma = string_to_E1(signature)
- If Gamma is "INVALID", output "INVALID" and stop
- If r*Gamma != 0, output "INVALID" and stop
- Compute c = pairing(Gamma, P2)
- Compute c' = pairing(H, PK)
- If c and c' are equal, output "VALID", else output "INVALID"
The following algorithm works for both the same message aggregation and different message aggregation.
Input: (PK_1, signature_1), ..., (PK_n, signature_n) Output: signature
- Output signature = E1_to_string(string_to_E1(signature_1) + ... + string_to_E1(signature_n))
Input: (PK_1, ..., PK_n), message, signature Output: "VALID" or "INVALID"
- PK' = PK_1 + ... + PK_n
- Output Verify(PK', message, signature)
Input: (PK_1, message_1), ..., (PK_n, message_n), signature
Output: "VALID" or "INVALID"
- H_i = hash_to_G1(suite_string, message_i)
- Gamma = string_to_E1(signature)
- If Gamma is "INVALID", output "INVALID" and stop
- If r*Gamma != 0, output "INVALID" and stop
- Compute c = pairing(Gamma, P2)
- Compute c' = pairing(H_1, PK_1) * ... * pairing(H_n, PK_n)
- If c and c' are equal, output "VALID", else output "INVALID"
Here, we describe the auxiliary functions relating to serialization and hashing to the elliptic curves E, where E may be E1 or E2.
(Authors' note: this section is extremely preliminary and we anticipate substantial updates pending feedback from the community. We describe a generic approach for hashing, in order to cover hashing into curves defined over prime power extension fields, which are not covered in [I-D.irtf-cfrg-hash-to-curve]. We expect to support several different hashing algorithms specified via the suite_string.)
In all the pairing-friendly curves, E is defined over a field GF(p^k). We also assume an explicit isomorphism that allows us to treat GF(p^k) as GF(p). In most of the curves in [I-D.pairing-friendly-curves], we have k=1 for E1 and k=2 for E2.
Each point (x,y) on E can be specified by the x-coordinate in GP(p)^k plus a single bit to determine whether the point is (x,y) or (x,-y), thus requiring k log(p) + 1 bits [I-D.irtf-cfrg-hash-to-curve].
Concretely, we encode a point (x,y) on E as a string comprising k substrings s_1, ..., s_k each of length log(p)+2 bits, where
- the first bit of s_1 indicates whether E is the point at infinity
- the second bit of s_1 indicates whether the point is (x,y) or (x,-y)
- the first two bits of s_2, ..., s_k are 00
- the x-coordinate is specified by the last log(p) bits of s_1, ..., s_k
In fact, we will pad each substring with 0 bits so that the length of each substring is a multiple of 8 bits.
This section uses the following constants:
- pbits: the number of bits to represent integers modulo p.
- padded_pbits: the smallest multiple of 8 that is greater than pbits+2.
- padlen: padded_pbits - padlen
| curve | pbits | padded_pbits | padlen |
|---|---|---|---|
| BLS-381 | 381 | 384 | 3 |
In general we view a string str as a vector of substrings s_1, ... s_k for k >= 1; each substring is of padded_pbits bits; and k is set properly according to the individual curve. For example, for BLS12-381 curve, k=1 for E1 and 2 for E2. If the input string is not a multiple of padded_pbits, we tail pad the string to meet the correct length.
A string that encodes an E1/E2 point may have the following structure:
-
for the first substring s_1
- the first bit indicates if the point is the point at infinity
- the second bit is either 0 or 1, denoted by y_bit
- the third to padlen bits are 0
-
for the rest substrings s_2, ... s_k
- the first padlen bits are 0s
TBD: some implementation uses an additional leading bit to indicate the string is in a compressed form (give x coordinate and the parity/sign of y coordinate) or in an uncompressed form (give both x and y coordinate).
Input:
input_string - a point P = (x, y) on the curve
Output:
a string of k * padded_pbits
Steps:
- If P is the point at infinity, output 0b1000...0
- Parse y as y_1, ..., y_k; set y_bit as y_1 mod 2
- Parse x as x_1, ..., x_k
- set the substring s_1 = 0 | y_bit | padlen-2 of 0s | int_to_string(x_1)
- set substrings s_i = padlen of 0s | int_to_string(x_i) for 2<=i<=k
- Output the string s_1 | s_2 | ... | s_k
The algorithm takes as follows:
Input:
input_string - a single octet string.
Output:
Either a point P on the curve, or INVALID
Steps:
-
If length(input_string) is < padded_pbits/8 bytes, lead pad input_string with 0s;
-
If length(input_string) is not a multiple of padded_pbits/8 bytes, tail pad with 0, ..., 0;
-
Parse input_string as a vector of substrings s_1, ..., s_k
-
b = s_1[0]; i.e., the first byte of the first substring;
-
If the first bit of b is 1, return P = 0 (the point at infinity)
-
Set y_bit to be the second bit of b and then set the second bit of b to 0
-
If the third to plen bits of input_string are not 0, return INVALID
-
Set x_1 = string_to_int(s_1)
- if x_1 > p then return INVALID
-
for i in [2 ... k]
- b = s_i[0]
- if top plen bits of b is not 0, return INVALID
- set x_i = string_to_int(s_i)
- if x_1 > p then return INVALID
-
Set x= (x_1, ..., x_k)
-
solve for y so that (x, y) satisfies elliptic curve equation;
- output INVALID if equation is not solvable with x
- parse y as (y_1, ..., y_k)
- if solutions exist, there should be a pair of ys where y_1-s differ by parity
- set y to be the solution where y_1 is odd if y_bit = 1
- set y to be the solution where y_1 is even if y_bit = 0
-
output P = (x, y) as a curve point.
TBD: check the parity property remains true for E2. The Chia and Etherum implementations use lexicographic ordering.
The algorithm takes as follows:
Input:
input_string - a single octet string.
Output:
Either a point P on the curve, or INVALID
Steps:
-
If length(input_string) is < padded_pbits/8 bytes, lead pad input_string with 0s;
-
If length(input_string) is not a multiple of 48 bytes, tail pad with 0, ..., 0s;
-
Parse input_string as a vector of substrings s_1, ..., s_k
-
Set the first padlen bits except for the second bit of s_1[0] to 0
-
Set the first padlen bits for s_2[0], ..., s_k[0] to 0
-
call string_to_curve(input_string)
Note: this section will be removed in later versions. We will refer to
[I-D.irtf-cfrg-hash-to-curve] once it is updated with methods for hash into
pairing friendly curves. The rest of the material are for information only.
The following hash_to_G1_try_and_increment algorithm implements hash_to_G1 in a simple and generic way that works for any pairing-friendly curve. It follows the try-and-increment approach [I-D.irtf-cfrg-hash-to-curve] and uses alt_str_to_curve as a subroutine. The running depends on alpha_string, and for the appropriate instantiations, is expected to find a valid G1 element after approximately two attempts (i.e., when ctr=1) on average.
The following pseudocode is adapted from draft-irtf-cfrg-vrf-03 Section 5.4.1.1.
Recall that cofactor = |E1|/|G1|. This algorithm also uses a hash functions that hashes arbitrary strings into strings of 384 bits.
hash_to_G1_try_and_increment(suite_string, alpha_string)
input:
suite_string - an identifier to indicate the curves and a hash function
that outputs k*padded_pbits bits
alpha_string - the input string to be hashed
Output:
H - hashed value, a point in G1
Steps:
-
ctr = 0
-
one_string = 0x01 = int_to_string(1, 1), a single octet with value 1
-
H = "INVALID"
-
While H is "INVALID" or H is EC point at infinity:
-
ctr_string = int_to_string(ctr, 1)
-
hash_string = Hash(suite_string || one_string || alpha_string || ctr_string)
-
H = alt_str_to_curve(hash_string)
-
If H is not "INVALID" and cofactor > 1, set H = cofactor * H
-
ctr = ctr + 1
-
-
Output H
Note that this hash to group function will never hash into the point at infinity. This does not affect the security since the output distribution is statistically indistinguishable from the uniform distribution over the group.
The following g1_membership_test and g1_membership_test algorithms is to check if a E1 or E2 point is in the correct prime subgroup. Example:
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
for curve BLS12-381.
g1_membership_test(input_point)
input:
input_point - a point P = (x, y) on the curve E1
Output:
"VALID" if P is in G1; "INVALID" otherwise
Steps:
- r = order of group G1
- if r * P == 1 return "VALID", otherwise, return "INVALID"
g2_membership_test(input_point)
input:
input_point - a point P = (x, y) on the curve E2
Output:
"VALID" if P is in G2; "INVALID" otherwise
Steps:
- r = order of group G2
- if r * P == 1 return "VALID", otherwise, return "INVALID"
When users register a public key, we should ensure that it is well-formed. This requires a G2 membership test. In applications where we use aggregation, we need to enforce security against rogue key attacks Boneh-Drijvers-Neven 18a. This can be achieved in one of three ways:
-
Message augmentation: pk = g^sk, sig = H(pk, m)^sk (BGLS, Bellare-Namprempre-Neven 07).
-
Proof of possession: pk = ( u=g^sk, H'(u)^sk ), sig = H(m)^sk (see concrete mechanisms in [Ristenpart-Yilek 06])
-
Linear combination: agg = sig_1^t_1 ... sig_n^t_n (see Boneh-Drijvers-Neven 18b; there, pre-processing public keys would speed up verification.)
Several existing implementations skip step 4 (membership in G1) in Verify. In this setting, the BLS signature remains unforgeable (but not strongly unforgeable) under a stronger assumption:
given P1, aP1, P2, bP2, it is hard to compute U in E1 such that pairing(U,P2) = pairing(aP1, bP2).
It is important to protect the secret key in implementations of the signing algorithm. We can protect against some side-channel attacks by 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. To achieve this, we require that point multiplication in G1 should run in constant time with respect to the scalar.
BLS signatures are deterministic. This protects against attacks arising from signing with bad randomness, for example, the nounce reusing attack in ECDSA [HDWH 12].
The security analysis models the hash function H as a random oracle, and it is crucial that we implement H using a cryptographically secure hash function.
This section will be removed in the final version of the draft. There are currently several implementations of BLS signatures using the BLS12-381 curve.
-
Algorand: TBA
-
Chia: spec python/C++. Here, they are swapping G1 and G2 so that the public keys are small, and the benefits of avoiding a membership check during signature verification would even be more substantial. The current implementation does not seem to implement the membership check. Chia uses the Fouque-Tibouchi hashing to the curve, which can be done in constant time.
-
Dfinity: go BLS. The current implementations do not seem to implement the membership check.
-
Ethereum 2.0: spec
-
Pairing-friendly curves draft-yonezawa-pairing-friendly-curves
-
Pairing-based Identity-Based Encryption IEEE 1363.3.
-
Identity-Based Cryptography Standard rfc5901.
-
Hashing to Elliptic Curves draft-irtf-cfrg-hash-to-curve-02, in order to implement the hash function H. The current draft does not cover pairing-friendly curves, where we need to handle curves over prime power extension fields GF(p^k).
-
Verifiable random functions draft-irtf-cfrg-vrf-03. Section 5.4.1 also discusses instantiations for H.
-
EdDSA rfc8032
TBA: (i) test vectors for both variants of the signature scheme (signatures in G2 instead of G1) , (ii) test vectors ensuring membership checks, (iii) intermediate computations ctr, hm.
Consider the following game between an adversary and a challenger. The challenger generates a key-pair (PK, SK) and gives PK to the adversary. The adversary may repeatedly query the challenger on any message message to obtain its corresponding signature signature. Eventually the adversary outputs a pair (message', signature').
Unforgeability means no adversary can produce a pair (message', signature') for a message message' which he never queried the challenger and Verify(PK, message, signature) outputs VALID.
In the strong unforgeability game, the game proceeds as above, except no adversary should be able to produce a pair (message', signature') that verifies (i.e. Verify(PK, message, signature) outputs VALID) given that he never queried the challenger on message', or if he did query and obtained a reply signature, then signature != signature'.
More informally, the strong unforgeability means that no adversary can produce a different signature (not provided by the challenger) on a message which he queried before.
Consider the following game between an adversary and a challenger. The challenger generates a key-pair (PK, SK) and gives PK to the adversary. The adversary may repeatedly query the challenger on any message message to obtain its corresponding signature signature. Eventually the adversary outputs a sequence ((PK_1, message_1), ..., (PK_n, message_n), (PK, message), signature).
Aggregation unforgeability means that no adversary can produce a sequence where it did not query the challenger on the message message, and Verify-Aggregated((PK_1, message_1), ..., (PK_n, message_n), (PK, message), signature) outputs VALID.
We note that aggregation unforgeability implies message unforgeability.
TODO: We may also consider a strong aggregation unforgeability property.
The BLS signature scheme achieves strong message unforgeability and aggregation unforgeability under the co-CDH assumption, namely that given P1, aP1, P2, bP2, it is hard to compute {ab}*P1. [BLS01, BGLS03]
[BLS 01] Dan Boneh, Ben Lynn, Hovav Shacham: Short Signatures from the Weil Pairing. ASIACRYPT 2001: 514-532.
[BGLS 03] Dan Boneh, Craig Gentry, Ben Lynn, Hovav Shacham: Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. EUROCRYPT 2003: 416-432.
[HDWH 12] Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: "Mining your Ps and Qs: Detection of widespread weak keys in network devices.", USENIX 2012.
[I-D.irtf-cfrg-hash-to-curve] S. Scott, N. Sullivan, and C. Wood: "Hashing to Elliptic Curves", draft-irtf-cfrg-hash-to-curve-01 (work in progress), July 2018.
[I-D.pairing-friendly-curves] S. Yonezawa, S. Chikara, T. Kobayashi, T. Saito: "Pairing-Friendly Curves", draft-yonezawa-pairing-friendly-curves-00, Jan 2019.