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]