Internet DRAFT - draft-boneh-bls-signature
draft-boneh-bls-signature
CFRG D. Boneh
Internet-Draft Stanford University
Expires: August 12, 2019 S. Gorbunov
Algorand and University of Waterloo
H. Wee
Algorand and ENS, Paris
Z. Zhang
Algorand
February 8, 2019
BLS Signature Scheme
draft-boneh-bls-signature-00
Abstract
The BLS signature scheme was introduced by Boneh-Lynn-Shacham in
2001. The signature scheme relies on pairing-friendly curves and
supports non-interactive aggregation properties. That is, given a
collection of signatures (sigma_1, ..., sigma_n), anyone can produce
a short signature (sigma) that authenticates the entire collection.
BLS signature scheme is simple, efficient and can be used in a
variety of network protocols and systems to compress signatures or
certificate chains. This document specifies the BLS signature and
the aggregation algorithms.
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 August 12, 2019.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
Boneh, et al. Expires August 12, 2019 [Page 1]
Internet-Draft BLS-signature February 2019
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Signature Scheme Algorithms and Properties . . . . . . . 4
1.2.1. Aggregation . . . . . . . . . . . . . . . . . . . . . 4
1.2.2. Security . . . . . . . . . . . . . . . . . . . . . . 5
2. BLS Signature . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Preliminaries . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Keygen: Key Generation . . . . . . . . . . . . . . . . . 8
2.3. Sign: Signature Generation . . . . . . . . . . . . . . . 8
2.4. Verify: Signature Verification . . . . . . . . . . . . . 8
2.5. Aggregate . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5.1. Verify-Aggregated-1 . . . . . . . . . . . . . . . . . 9
2.5.2. Verify-Aggregated-n . . . . . . . . . . . . . . . . . 9
2.5.3. Implementation optimizations . . . . . . . . . . . . 9
2.6. Auxiliary Functions . . . . . . . . . . . . . . . . . . . 9
2.6.1. Preliminaries . . . . . . . . . . . . . . . . . . . . 10
2.6.2. Type conversions . . . . . . . . . . . . . . . . . . 10
2.6.3. Hash to groups . . . . . . . . . . . . . . . . . . . 14
2.7. Security analysis . . . . . . . . . . . . . . . . . . . . 15
3. Security Considerations . . . . . . . . . . . . . . . . . . . 15
3.1. Verifying public keys . . . . . . . . . . . . . . . . . . 15
3.2. Skipping membership check . . . . . . . . . . . . . . . . 15
3.3. Side channel attacks . . . . . . . . . . . . . . . . . . 15
3.4. Randomness considerations . . . . . . . . . . . . . . . . 16
3.5. Implementing the hash function . . . . . . . . . . . . . 16
4. Implementation Status . . . . . . . . . . . . . . . . . . . . 16
5. Related Standards . . . . . . . . . . . . . . . . . . . . . . 16
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
7. Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . 17
8. Appendix B. Reference . . . . . . . . . . . . . . . . . . . . 17
9.1. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18
Boneh, et al. Expires August 12, 2019 [Page 2]
Internet-Draft BLS-signature February 2019
1. Introduction
A signature scheme is a fundamental cryptographic primitive used on
the Internet that is used to protect 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:
1. The public key and the signatures are encoded as single group
elements.
2. Verification requires 2 pairing operations.
3. A collection of signatures (sigma_1, ..., sigma_n) can be
compressed into a single signature (sigma). 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, we believe the scheme will find very
interesting applications. The immediate applications include
compressing signature chains in Public Key Infrastructure (PKI) and
in the 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.
In addition, the BLS signature scheme is already integrated into
major blockchain projects such as Ethereum, Algorand, Chia and
Dfinity. 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.
1.1. Terminology
The following terminology is used through this document:
o SK: The private key for the signature scheme.
o PK: The public key for the signature scheme.
Boneh, et al. Expires August 12, 2019 [Page 3]
Internet-Draft BLS-signature February 2019
o msg: The input to be signed by the signature scheme.
o sigma : The digital signature output.
o Signer: The Signer generates a pair (SK, PK), publishes PK for
everyone to see, but keeps the private key SK.
o Verifier: The Verifier holds a public key PK. It receives (msg,
sigma) that it wishes to verify.
o Aggregator: The Aggregator receives a collection of signatures
(sigma_1, ..., sigma_n) that it wishes to compress into a short
signature.
1.2. Signature Scheme Algorithms and Properties
A signature scheme comes with a key generation algorithm that
generates a public key PK and a private key SK.
The Signer, given an input msg, uses the private key SK to obtain and
output a signature sigma.
sigma = Sign(SK, msg)
The signing algorithm may be deterministic or randomized, depending
on the scheme. Looking ahead, BLS instantiates a deterministic
signing algorithm.
The signature sigma allows a Verifier holding the public key PK to
verify that sigma is indeed produced by the signer holding the
associated secret key. Thus, the digital scheme also comes with an
algorithm
Verify(PK, msg, sigma)
that outputs VALID if sigma is a valid signature of msg, and INVALID
otherwise.
We require that PK, sigma and msg are octet strings.
1.2.1. Aggregation
An aggregatable signature scheme includes an algorithm that allows to
compress a collection of signatures into a short signature.
sigma = Aggregate((PK_1, sigma_1), ..., (PK_n, sigma_n))
Boneh, et al. Expires August 12, 2019 [Page 4]
Internet-Draft BLS-signature February 2019
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, msg_1), ..., (PK_n, msg_n), sigma)
that outputs VALID if sigma is a valid aggregated signature of
messages msg_1, ..., msg_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, msg_1 = msg_2 = ... = msg_n.
Verify-Aggregated(PK_1, ..., PK_n, msg, sigma)
1.2.2. Security
1.2.2.1. Message Unforgeability
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 msg to obtain its corresponding signature sigma. Eventually
the adversary outputs a pair (msg', sigma').
Unforgeability means no adversary can produce a pair (msg', sigma')
for a message msg' which he never queried the challenger and
Verify(PK, msg, sigma) outputs VALID.
1.2.2.2. Strong Message Unforgeability
In the strong unforgeability game, the game proceeds as above, except
no adversary should be able to produce a pair (msg', sigma') that
verifies (i.e. Verify(PK, msg, sigma) outputs VALID) given that he
never queried the challenger on msg', or if he did query and obtained
a reply sigma, then sigma != sigma'.
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.
Boneh, et al. Expires August 12, 2019 [Page 5]
Internet-Draft BLS-signature February 2019
1.2.2.3. Aggregation Unforgeability
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 msg to obtain its corresponding signature sigma. Eventually
the adversary outputs a sequence ((PK_1, msg_1), ..., (PK_n, msg_n),
(PK, msg), sigma).
Aggregation unforgeability means that no adversary can produce a
sequence where it did not query the challenger on the message msg,
and Verify-Aggregated((PK_1, msg_1), ..., (PK_n, msg_n), (PK, msg),
sigma) outputs VALID.
We note that aggregation unforgeability implies message
unforgeability.
TODO: We may also consider a strong aggregation unforgeability
property.
2. BLS Signature
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. Such curves are described in [I-D.pairing-friendly-
curves], one of which is BLS12-381.
There are two variants of the scheme:
1. (minimizing signature size) Put signatures in G1 and public keys
in G2, 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.
2. (minimizing public key size) Put public keys in G1 and signatures
in G2. 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.
Boneh, et al. Expires August 12, 2019 [Page 6]
Internet-Draft BLS-signature February 2019
2.1. Preliminaries
Notation and primitives used:
o E1, E2 - elliptic curves (EC) defined over a field
o P1, P2 - elements of E1,E2 of prime order r
o G1, G2 - prime-order subgroups of E1, E2 generated by P1, P2
o GT - order r subgroup of the multiplicative group over a field
o We require an efficient pairing e : (G1, G2) -> GT that is
bilinear and non-degenerate.
o 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].
o Field operations in GT are written in multiplicative notation,
with a*b denoting field element multiplication.
o || - octet string concatenation
o suite_string - an identifier for the ciphersuite. May 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:
o int_to_string(a, len) - conversion of nonnegative integer a to
octet string of length len.
o string_to_int(a_string) - conversion of octet string a_string to
nonnegative integer.
o E1_to_string - conversion of E1 point to octet string
o 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
o hash_to_G1 - cryptographic hashing of octet string to G1 element.
Must return a valid G1 element. Specified in
Section {{auxiliary}}.
Boneh, et al. Expires August 12, 2019 [Page 7]
Internet-Draft BLS-signature February 2019
2.2. Keygen: Key Generation
Output: PK, SK
1. SK = x, chosen as a random integer in the range 1 and r-1
2. PK = x*P2
3. Output PK, SK
2.3. Sign: Signature Generation
Input: SK = x, msg Output: sigma
1. Input a secret key SK = x and a message digest msg
2. H = hash_to_G1(suite_string, msg)
3. Gamma = x*H
4. sigma = E1_to_string(Gamma)
5. Output sigma
2.4. Verify: Signature Verification
Input: PK, msg, sigma Output: "VALID" or "INVALID"
1. H = hash_to_G1(suite_string, msg)
2. Gamma = string_to_E1(sigma)
3. If Gamma is "INVALID", output "INVALID" and stop
4. If r*Gamma != 0, output "INVALID" and stop
5. Compute c = e(Gamma, P2)
6. Compute c' = e(H, PK)
7. If c and c' are equal, output "VALID", else output "INVALID"
2.5. Aggregate
Input: (PK_1, sigma_1), ..., (PK_n, sigma_n) Output: sigma
1. Output sigma = sigma_1 + sigma_2 + ... + sigma_n
Boneh, et al. Expires August 12, 2019 [Page 8]
Internet-Draft BLS-signature February 2019
2.5.1. Verify-Aggregated-1
Input: (PK_1, ..., PK_n), msg, sigma Output: "VALID" or "INVALID"
1. PK' = PK_1 + ... + PK_n
2. Output Verify(PK', msg, sigma)
2.5.2. Verify-Aggregated-n
Input: (PK_1, msg_1), ..., (PK_n, msg_n), sigma
Output: "VALID" or "INVALID"
1. H_i = hash_to_G1(suite_string, msg_i)
2. Gamma = string_to_E1(sigma)
3. If Gamma is "INVALID", output "INVALID" and stop
4. If r*Gamma != 0, output "INVALID" and stop
5. Compute c = e(Gamma, P2)
6. Compute c' = e(H_1, PK_1) * ... * e(H_n, PK_n)
7. If c and c' are equal, output "VALID", else output "INVALID"
2.5.3. Implementation optimizations
There are several optimizations we should use to speed up
verification. First, we can use multi-pairings instead of a normal
pairing. Roughly speaking, this means that we can reuse the "final
exponentiation" step in all of the pairing operations. In addition,
we can carry out pre-computation on the public keys for aggregate
verification.
2.6. Auxiliary Functions
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.)
Boneh, et al. Expires August 12, 2019 [Page 9]
Internet-Draft BLS-signature February 2019
2.6.1. Preliminaries
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
o the first bit of s_1 indicates whether E is the point at infinity
o the second bit of s_1 indicates whether the point is (x,y) or (x,-
y)
o the first two bits of s_2, ..., s_k are 00
o the x-coordinate is specified by the last log(p) bits of s_1, ...,
s_k
In fact, we will pad each substring with 0s so that the length of
each substring is a multiple of 8.
This section uses the following constants:
o pbits: the number of bits to represent integers modulo p.
o padded_pbits: the smallest multiple of 8 that is greater than
pbits+2.
o padlen: padded_pbits - padlen
+---------+-------+--------------+--------+
| curve | pbits | padded_pbits | padlen |
+---------+-------+--------------+--------+
| BLS-381 | 381 | 384 | 3 |
+---------+-------+--------------+--------+
2.6.2. Type conversions
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
Boneh, et al. Expires August 12, 2019 [Page 10]
Internet-Draft BLS-signature February 2019
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
o 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).
2.6.2.1. curve-to-string
Input:
input_string - a point P = (x, y) on the curve
Output:
a string of k * padded_pbits
Steps:
1. If P is the point at infinity, output 0b1000...0
2. Parse y as y_1, ..., y_k; set y_bit as y_1 mod 2
3. Parse x as x_1, ..., x_k
4. set the substring s_1 = 0 | y_bit | padlen-2 of 0s |
int_to_string(x_1)
5. set substrings s_i = padlen of 0s | int_to_string(x_i) for
2<=i<=k
6. Output the string s_1 | s_2 | ... | s_k
Boneh, et al. Expires August 12, 2019 [Page 11]
Internet-Draft BLS-signature February 2019
2.6.2.2. string-to-curve
The algorithm takes as follows:
Input:
input_string - a single octet string.
Output:
Either a point P on the curve, or INVALID
Steps:
1. If length(input_string) is < padded_pbits/8 bytes, lead pad
input_string with 0s;
2. If length(input_string) is not a multiple of padded_pbits/8
bytes, tail pad with 0, ..., 0;
3. Parse input_string as a vector of substrings s_1, ..., s_k
4. b = s_1[0]; i.e., the first byte of the first substring;
5. If the first bit of b is 1, return P = 0 (the point at infinity)
6. Set y_bit to be the second bit of b and then set the second bit
of b to 0
7. If the third to plen bits of input_string are not 0, return
INVALID
8. Set x_1 = string_to_int(s_1)
1. if x_1 > p then return INVALID
9. for i in [2 ... k]
1. b = s_i[0]
2. if top plen bits of b is not 0, return INVALID
3. set x_i = string_to_int(s_i)
1. if x_1 > p then return INVALID
10. Set x= (x_1, ..., x_k)
Boneh, et al. Expires August 12, 2019 [Page 12]
Internet-Draft BLS-signature February 2019
11. 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
12. 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.
2.6.2.3. alt-str-to-curve
The algorithm takes as follows:
Input:
input_string - a single octet string.
Output:
Either a point P on the curve, or INVALID
Steps:
1. If length(input_string) is < padded_pbits/8 bytes, lead pad
input_string with 0s;
2. If length(input_string) is not a multiple of 48 bytes, tail pad
with 0, ..., 0s;
3. Parse input_string as a vector of substrings s_1, ..., s_k
4. Set the first padlen bits except for the second bit of s_1[0] to
0
5. Set the first padlen bits for s_2[0], ..., s_k[0] to 0
6. call string_to_curve(input_string)
Boneh, et al. Expires August 12, 2019 [Page 13]
Internet-Draft BLS-signature February 2019
2.6.3. Hash to groups
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:
1. ctr = 0
2. one_string = 0x01 = int_to_string(1, 1), a single octet with
value 1
3. H = "INVALID"
4. While H is "INVALID" or H is EC point at infinity:
1. ctr_string = int_to_string(ctr, 1)
2. hash_string = Hash(suite_string || one_string ||
alpha_string || ctr_string)
3. H = alt_str_to_curve(hash_string)
4. If H is not "INVALID" and cofactor > 1, set H = cofactor * H
5. ctr = ctr + 1
Boneh, et al. Expires August 12, 2019 [Page 14]
Internet-Draft BLS-signature February 2019
5. 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.
2.7. Security analysis
The BLS signature scheme achieves strong message unforgeability and
aggregation unforgeability under the co-CDH assumption, namely that
given P1, a_P1, P2, b_P2, it is hard to compute {ab}*P1. [BLS01,
BGLS03]
3. Security Considerations
3.1. Verifying public keys
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 would further require that users prove
knowledge of the corresponding secret key during registration to
prevent rogue key attacks.
TBA: additional discussion on this, e.g. [Ristenpart-Yilek 06], and
alternative mechanisms for securing aggregation against rogue key
attacks, e.g. [Boneh-Drijvers-Neven 18]; there, pre-processing
public keys would speed up verification.
3.2. Skipping membership check
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, a_P1, P2, b_P2, it is hard to compute U in E1 such that
e(U,P2) = e(a_P1, b_P2).
3.3. Side channel attacks
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.
Boneh, et al. Expires August 12, 2019 [Page 15]
Internet-Draft BLS-signature February 2019
3.4. Randomness considerations
BLS signatures are deterministic. This protects against attacks
arising from signing with bad randomness.
3.5. Implementing the hash function
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. <!-- At the moment, hashing onto G1 is
typically implemented by hashing into E1 and then multiplying by the
cofactor; this needs to be taken into account in the security proof
(namely, the reduction needs to simulate the corresponding E1
element).-->
4. Implementation Status
There are currently several implementations of BLS signatures using
the BLS12-381 curve.
o Algorand: TBA
o Chia: spec [1] python/C++ [2]. 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.
o Dfinity: go [3] BLS [4]. The current implementations do not seem
to implement the membership check.
o Ethereum 2.0: spec [5]
5. Related Standards
o Pairing-friendly curves draft-yonezawa-pairing-friendly-curves [6]
o Pairing-based Identity-Based Encryption IEEE 1363.3 [7].
o Identity-Based Cryptography Standard rfc5901 [8].
o Hashing to Elliptic Curves draft-irtf-cfrg-hash-to-curve-02 [9],
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).)
Boneh, et al. Expires August 12, 2019 [Page 16]
Internet-Draft BLS-signature February 2019
o Verifiable random functions draft-irtf-cfrg-vrf-03 [10].
Section 5.4.1 also discusses instantiations for H.
o EdDSA rfc8032 [11]
6. IANA Considerations
This document does not make any requests of IANA.
7. Appendix A. Test Vectors
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.
8. Reference
8.1. Normative References
[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.
[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.
8.2. Informative References
9. References
9.1. URIs
[1] https://github.com/Chia-Network/bls-signatures/blob/master/
SPEC.md
[2] https://github.com/Chia-Network/bls-signatures
[3] https://github.com/dfinity/go-dfinity-crypto
[4] https://github.com/dfinity/bls
[5] https://github.com/ethereum/eth2.0-specs/blob/master/specs/
bls_signature.md
Boneh, et al. Expires August 12, 2019 [Page 17]
Internet-Draft BLS-signature February 2019
[6] https://tools.ietf.org/html/draft-yonezawa-pairing-friendly-
curves-00
[7] https://ieeexplore.ieee.org/document/6662370
[8] https://tools.ietf.org/html/rfc5091
[9] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-02
[10] https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03
[11] https://tools.ietf.org/html/rfc8032
Authors' Addresses
Dan Boneh
Stanford University
USA
Email: dabo@cs.stanford.edu
Sergey Gorbunov
Algorand and University of Waterloo
Boston, MA
USA
Email: sgorbunov@uwaterloo.ca
Hoeteck Wee
Algorand and ENS, Paris
Boston, MA
USA
Email: hoeteck.wee@ens.fr
Zhenfei Zhang
Algorand
Boston, MA
USA
Email: zhenfei@algorand.com
Boneh, et al. Expires August 12, 2019 [Page 18]
