idnits 2.17.1 draft-boneh-bls-signature-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 17) being 60 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There is 1 instance of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 8, 2019) is 1902 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'P' is mentioned on line 300, but not defined -- Looks like a reference, but probably isn't: '0' on line 608 == Missing Reference: 'Ristenpart-Yilek 06' is mentioned on line 684, but not defined == Missing Reference: 'Boneh-Drijvers-Neven 18' is mentioned on line 686, but not defined -- Looks like a reference, but probably isn't: '1' on line 795 -- Looks like a reference, but probably isn't: '2' on line 798 -- Looks like a reference, but probably isn't: '3' on line 800 -- Looks like a reference, but probably isn't: '4' on line 802 -- Looks like a reference, but probably isn't: '5' on line 804 -- Looks like a reference, but probably isn't: '6' on line 807 -- Looks like a reference, but probably isn't: '7' on line 810 -- Looks like a reference, but probably isn't: '8' on line 812 -- Looks like a reference, but probably isn't: '9' on line 814 -- Looks like a reference, but probably isn't: '10' on line 816 -- Looks like a reference, but probably isn't: '11' on line 818 == Unused Reference: 'BLS 01' is defined on line 774, but no explicit reference was found in the text == Unused Reference: 'BGLS 03' is defined on line 777, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'BLS 01' -- Possible downref: Non-RFC (?) normative reference: ref. 'BGLS 03' == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-01 ** Downref: Normative reference to an Informational draft: draft-irtf-cfrg-hash-to-curve (ref. 'I-D.irtf-cfrg-hash-to-curve') == Outdated reference: A later version (-02) exists of draft-yonezawa-pairing-friendly-curves-00 ** Downref: Normative reference to an Experimental draft: draft-yonezawa-pairing-friendly-curves (ref. 'I-D.pairing-friendly-curves') Summary: 3 errors (**), 0 flaws (~~), 10 warnings (==), 15 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG D. Boneh 3 Internet-Draft Stanford University 4 Expires: August 12, 2019 S. Gorbunov 5 Algorand and University of Waterloo 6 H. Wee 7 Algorand and ENS, Paris 8 Z. Zhang 9 Algorand 10 February 8, 2019 12 BLS Signature Scheme 13 draft-boneh-bls-signature-00 15 Abstract 17 The BLS signature scheme was introduced by Boneh-Lynn-Shacham in 18 2001. The signature scheme relies on pairing-friendly curves and 19 supports non-interactive aggregation properties. That is, given a 20 collection of signatures (sigma_1, ..., sigma_n), anyone can produce 21 a short signature (sigma) that authenticates the entire collection. 22 BLS signature scheme is simple, efficient and can be used in a 23 variety of network protocols and systems to compress signatures or 24 certificate chains. This document specifies the BLS signature and 25 the aggregation algorithms. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on August 12, 2019. 44 Copyright Notice 46 Copyright (c) 2019 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (https://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 62 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 63 1.2. Signature Scheme Algorithms and Properties . . . . . . . 4 64 1.2.1. Aggregation . . . . . . . . . . . . . . . . . . . . . 4 65 1.2.2. Security . . . . . . . . . . . . . . . . . . . . . . 5 66 2. BLS Signature . . . . . . . . . . . . . . . . . . . . . . . . 6 67 2.1. Preliminaries . . . . . . . . . . . . . . . . . . . . . . 7 68 2.2. Keygen: Key Generation . . . . . . . . . . . . . . . . . 8 69 2.3. Sign: Signature Generation . . . . . . . . . . . . . . . 8 70 2.4. Verify: Signature Verification . . . . . . . . . . . . . 8 71 2.5. Aggregate . . . . . . . . . . . . . . . . . . . . . . . . 8 72 2.5.1. Verify-Aggregated-1 . . . . . . . . . . . . . . . . . 9 73 2.5.2. Verify-Aggregated-n . . . . . . . . . . . . . . . . . 9 74 2.5.3. Implementation optimizations . . . . . . . . . . . . 9 75 2.6. Auxiliary Functions . . . . . . . . . . . . . . . . . . . 9 76 2.6.1. Preliminaries . . . . . . . . . . . . . . . . . . . . 10 77 2.6.2. Type conversions . . . . . . . . . . . . . . . . . . 10 78 2.6.3. Hash to groups . . . . . . . . . . . . . . . . . . . 14 79 2.7. Security analysis . . . . . . . . . . . . . . . . . . . . 15 80 3. Security Considerations . . . . . . . . . . . . . . . . . . . 15 81 3.1. Verifying public keys . . . . . . . . . . . . . . . . . . 15 82 3.2. Skipping membership check . . . . . . . . . . . . . . . . 15 83 3.3. Side channel attacks . . . . . . . . . . . . . . . . . . 15 84 3.4. Randomness considerations . . . . . . . . . . . . . . . . 16 85 3.5. Implementing the hash function . . . . . . . . . . . . . 16 86 4. Implementation Status . . . . . . . . . . . . . . . . . . . . 16 87 5. Related Standards . . . . . . . . . . . . . . . . . . . . . . 16 88 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 89 7. Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . 17 90 8. Appendix B. Reference . . . . . . . . . . . . . . . . . . . . 17 91 9.1. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 17 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 94 1. Introduction 96 A signature scheme is a fundamental cryptographic primitive used on 97 the Internet that is used to protect integrity of communication. 98 Only holder of the secret key can sign messages, but anyone can 99 verify the signature using the associated public key. 101 Signature schemes are used in point-to-point secure communication 102 protocols, PKI, remote connections, etc. Designing efficient and 103 secure digital signature is very important for these applications. 105 This document describes the BLS signature scheme. The scheme enjoys 106 a variety of important efficiency properties: 108 1. The public key and the signatures are encoded as single group 109 elements. 111 2. Verification requires 2 pairing operations. 113 3. A collection of signatures (sigma_1, ..., sigma_n) can be 114 compressed into a single signature (sigma). Moreover, the 115 compressed signature can be verified using only n+1 pairings (as 116 opposed to 2n pairings, when verifying naively n signatures). 118 Given the above properties, we believe the scheme will find very 119 interesting applications. The immediate applications include 120 compressing signature chains in Public Key Infrastructure (PKI) and 121 in the Secure Border Gateway Protocol (SBGP). Concretely, in a PKI 122 signature chain of depth n, we have n signatures by n certificate 123 authorities on n distinct certificates. Similarly, in SBGP, each 124 router receives a list of n signatures attesting to a path of length 125 n in the network. In both settings, using the BLS signature scheme 126 would allow us to compress the n signatures into a single signature. 128 In addition, the BLS signature scheme is already integrated into 129 major blockchain projects such as Ethereum, Algorand, Chia and 130 Dfinity. There, BLS signatures are used for authenticating 131 transactions as well as votes during the consensus protocol, and the 132 use of aggregation significantly reduces the bandwidth and storage 133 requirements. 135 1.1. Terminology 137 The following terminology is used through this document: 139 o SK: The private key for the signature scheme. 141 o PK: The public key for the signature scheme. 143 o msg: The input to be signed by the signature scheme. 145 o sigma : The digital signature output. 147 o Signer: The Signer generates a pair (SK, PK), publishes PK for 148 everyone to see, but keeps the private key SK. 150 o Verifier: The Verifier holds a public key PK. It receives (msg, 151 sigma) that it wishes to verify. 153 o Aggregator: The Aggregator receives a collection of signatures 154 (sigma_1, ..., sigma_n) that it wishes to compress into a short 155 signature. 157 1.2. Signature Scheme Algorithms and Properties 159 A signature scheme comes with a key generation algorithm that 160 generates a public key PK and a private key SK. 162 The Signer, given an input msg, uses the private key SK to obtain and 163 output a signature sigma. 165 sigma = Sign(SK, msg) 167 The signing algorithm may be deterministic or randomized, depending 168 on the scheme. Looking ahead, BLS instantiates a deterministic 169 signing algorithm. 171 The signature sigma allows a Verifier holding the public key PK to 172 verify that sigma is indeed produced by the signer holding the 173 associated secret key. Thus, the digital scheme also comes with an 174 algorithm 176 Verify(PK, msg, sigma) 178 that outputs VALID if sigma is a valid signature of msg, and INVALID 179 otherwise. 181 We require that PK, sigma and msg are octet strings. 183 1.2.1. Aggregation 185 An aggregatable signature scheme includes an algorithm that allows to 186 compress a collection of signatures into a short signature. 188 sigma = Aggregate((PK_1, sigma_1), ..., (PK_n, sigma_n)) 190 Note that the aggregator does not need to know the messages 191 corresponding to individual signatures. 193 The scheme also includes an algorithm to verify an aggregated 194 signature, given a collection of corresponding public keys, the 195 aggregated signature, and one or more messages. 197 Verify-Aggregated((PK_1, msg_1), ..., (PK_n, msg_n), sigma) 199 that outputs VALID if sigma is a valid aggregated signature of 200 messages msg_1, ..., msg_n, and INVALID otherwise. 202 The verification algorithm may also accept a simpler interface that 203 allows to verify an aggregate signature of the same message. That 204 is, msg_1 = msg_2 = ... = msg_n. 206 Verify-Aggregated(PK_1, ..., PK_n, msg, sigma) 208 1.2.2. Security 210 1.2.2.1. Message Unforgeability 212 Consider the following game between an adversary and a challenger. 213 The challenger generates a key-pair (PK, SK) and gives PK to the 214 adversary. The adversary may repeatedly query the challenger on any 215 message msg to obtain its corresponding signature sigma. Eventually 216 the adversary outputs a pair (msg', sigma'). 218 Unforgeability means no adversary can produce a pair (msg', sigma') 219 for a message msg' which he never queried the challenger and 220 Verify(PK, msg, sigma) outputs VALID. 222 1.2.2.2. Strong Message Unforgeability 224 In the strong unforgeability game, the game proceeds as above, except 225 no adversary should be able to produce a pair (msg', sigma') that 226 verifies (i.e. Verify(PK, msg, sigma) outputs VALID) given that he 227 never queried the challenger on msg', or if he did query and obtained 228 a reply sigma, then sigma != sigma'. 230 More informally, the strong unforgeability means that no adversary 231 can produce a different signature (not provided by the challenger) on 232 a message which he queried before. 234 1.2.2.3. Aggregation Unforgeability 236 Consider the following game between an adversary and a challenger. 237 The challenger generates a key-pair (PK, SK) and gives PK to the 238 adversary. The adversary may repeatedly query the challenger on any 239 message msg to obtain its corresponding signature sigma. Eventually 240 the adversary outputs a sequence ((PK_1, msg_1), ..., (PK_n, msg_n), 241 (PK, msg), sigma). 243 Aggregation unforgeability means that no adversary can produce a 244 sequence where it did not query the challenger on the message msg, 245 and Verify-Aggregated((PK_1, msg_1), ..., (PK_n, msg_n), (PK, msg), 246 sigma) outputs VALID. 248 We note that aggregation unforgeability implies message 249 unforgeability. 251 TODO: We may also consider a strong aggregation unforgeability 252 property. 254 2. BLS Signature 256 BLS signatures require pairing-friendly curves given by e : G1 x G2 257 -> GT, where G1, G2 are prime-order subgroups of elliptic curve 258 groups E1, E2. Such curves are described in [I-D.pairing-friendly- 259 curves], one of which is BLS12-381. 261 There are two variants of the scheme: 263 1. (minimizing signature size) Put signatures in G1 and public keys 264 in G2, where G1/E1 has the more compact representation. For 265 instance, when instantiated with the pairing-friendly curve 266 BLS12-381, this yields signature size of 48 bytes, whereas the 267 ECDSA signature over curve25519 has a signature size of 64 byes. 269 2. (minimizing public key size) Put public keys in G1 and signatures 270 in G2. This latter case comes up when we do signature 271 aggregation, where most of the communication costs come from 272 public keys. This is particularly relevant in applications such 273 as blockchains and compressing certificate chains, where the goal 274 is to minimize the total size of multiple public keys and 275 aggregated signatures. 277 The rest of the write-up assumes the first variant. It is 278 straightforward to obtain algorithms for the second variant from 279 those of the first variant where we simply swap G1,E1 with G2,E2 280 respectively. 282 2.1. Preliminaries 284 Notation and primitives used: 286 o E1, E2 - elliptic curves (EC) defined over a field 288 o P1, P2 - elements of E1,E2 of prime order r 290 o G1, G2 - prime-order subgroups of E1, E2 generated by P1, P2 292 o GT - order r subgroup of the multiplicative group over a field 294 o We require an efficient pairing e : (G1, G2) -> GT that is 295 bilinear and non-degenerate. 297 o Elliptic curve operations in E1 and E2 are written in additive 298 notation, with P+Q denoting point addition and x*P denoting scalar 299 multiplication of a point P by a scalar x. 300 TBD: [I-D.pairing-friendly-curves] uses the notation x[P]. 302 o Field operations in GT are written in multiplicative notation, 303 with a*b denoting field element multiplication. 305 o || - octet string concatenation 307 o suite_string - an identifier for the ciphersuite. May include an 308 identifier of the curve, for example BLS12-381, an identifier of 309 the hash function, for example SHA512, and the algorithm in use, 310 for example, try-and-increment. 312 Type conversions: 314 o int_to_string(a, len) - conversion of nonnegative integer a to 315 octet string of length len. 317 o string_to_int(a_string) - conversion of octet string a_string to 318 nonnegative integer. 320 o E1_to_string - conversion of E1 point to octet string 322 o string_to_E1 - conversion of octet string to E1 point. Returns 323 INVALID if the octet string does not convert to a valid E1 point. 325 Hashing Algorithms 327 o hash_to_G1 - cryptographic hashing of octet string to G1 element. 328 Must return a valid G1 element. Specified in 329 Section {{auxiliary}}. 331 2.2. Keygen: Key Generation 333 Output: PK, SK 335 1. SK = x, chosen as a random integer in the range 1 and r-1 337 2. PK = x*P2 339 3. Output PK, SK 341 2.3. Sign: Signature Generation 343 Input: SK = x, msg Output: sigma 345 1. Input a secret key SK = x and a message digest msg 347 2. H = hash_to_G1(suite_string, msg) 349 3. Gamma = x*H 351 4. sigma = E1_to_string(Gamma) 353 5. Output sigma 355 2.4. Verify: Signature Verification 357 Input: PK, msg, sigma Output: "VALID" or "INVALID" 359 1. H = hash_to_G1(suite_string, msg) 361 2. Gamma = string_to_E1(sigma) 363 3. If Gamma is "INVALID", output "INVALID" and stop 365 4. If r*Gamma != 0, output "INVALID" and stop 367 5. Compute c = e(Gamma, P2) 369 6. Compute c' = e(H, PK) 371 7. If c and c' are equal, output "VALID", else output "INVALID" 373 2.5. Aggregate 375 Input: (PK_1, sigma_1), ..., (PK_n, sigma_n) Output: sigma 377 1. Output sigma = sigma_1 + sigma_2 + ... + sigma_n 379 2.5.1. Verify-Aggregated-1 381 Input: (PK_1, ..., PK_n), msg, sigma Output: "VALID" or "INVALID" 383 1. PK' = PK_1 + ... + PK_n 385 2. Output Verify(PK', msg, sigma) 387 2.5.2. Verify-Aggregated-n 389 Input: (PK_1, msg_1), ..., (PK_n, msg_n), sigma 390 Output: "VALID" or "INVALID" 392 1. H_i = hash_to_G1(suite_string, msg_i) 394 2. Gamma = string_to_E1(sigma) 396 3. If Gamma is "INVALID", output "INVALID" and stop 398 4. If r*Gamma != 0, output "INVALID" and stop 400 5. Compute c = e(Gamma, P2) 402 6. Compute c' = e(H_1, PK_1) * ... * e(H_n, PK_n) 404 7. If c and c' are equal, output "VALID", else output "INVALID" 406 2.5.3. Implementation optimizations 408 There are several optimizations we should use to speed up 409 verification. First, we can use multi-pairings instead of a normal 410 pairing. Roughly speaking, this means that we can reuse the "final 411 exponentiation" step in all of the pairing operations. In addition, 412 we can carry out pre-computation on the public keys for aggregate 413 verification. 415 2.6. Auxiliary Functions 417 Here, we describe the auxiliary functions relating to serialization 418 and hashing to the elliptic curves E, where E may be E1 or E2. 420 (Authors' note: this section is extremely preliminary and we 421 anticipate substantial updates pending feedback from the community. 422 We describe a generic approach for hashing, in order to cover hashing 423 into curves defined over prime power extension fields, which are not 424 covered in [I-D.irtf-cfrg-hash-to-curve]. We expect to support 425 several different hashing algorithms specified via the suite_string.) 427 2.6.1. Preliminaries 429 In all the pairing-friendly curves, E is defined over a field 430 GF(p^k). We also assume an explicit isomorphism that allows us to 431 treat GF(p^k) as GF(p). In most of the curves in [I-D.pairing- 432 friendly-curves], we have k=1 for E1 and k=2 for E2. 434 Each point (x,y) on E can be specified by the x-coordinate in GP(p)^k 435 plus a single bit to determine whether the point is (x,y) or (x,-y), 436 thus requiring k log(p) + 1 bits [I-D.irtf-cfrg-hash-to-curve]. 438 Concretely, we encode a point (x,y) on E as a string comprising k 439 substrings s_1, ..., s_k each of length log(p)+2 bits, where 441 o the first bit of s_1 indicates whether E is the point at infinity 443 o the second bit of s_1 indicates whether the point is (x,y) or (x,- 444 y) 446 o the first two bits of s_2, ..., s_k are 00 448 o the x-coordinate is specified by the last log(p) bits of s_1, ..., 449 s_k 451 In fact, we will pad each substring with 0s so that the length of 452 each substring is a multiple of 8. 454 This section uses the following constants: 456 o pbits: the number of bits to represent integers modulo p. 458 o padded_pbits: the smallest multiple of 8 that is greater than 459 pbits+2. 461 o padlen: padded_pbits - padlen 463 +---------+-------+--------------+--------+ 464 | curve | pbits | padded_pbits | padlen | 465 +---------+-------+--------------+--------+ 466 | BLS-381 | 381 | 384 | 3 | 467 +---------+-------+--------------+--------+ 469 2.6.2. Type conversions 471 In general we view a string str as a vector of substrings s_1, ... 472 s_k for k >= 1; each substring is of padded_pbits bits; and k is set 473 properly according to the individual curve. For example, for 474 BLS12-381 curve, k=1 for E1 and 2 for E2. If the input string is not 475 a multiple of padded_pbits, we tail pad the string to meet the 476 correct length. 478 A string that encodes an E1/E2 point may have the following 479 structure: * for the first substring s_1 * the first bit indicates if 480 the point is the point at infinity * the second bit is either 0 or 1, 481 denoted by y_bit * the third to padlen bits are 0 483 o for the rest substrings s_2, ... s_k 485 * the first padlen bits are 0s 487 TBD: some implementation uses an additional leading bit to indicate 488 the string is in a compressed form (give x coordinate and the parity/ 489 sign of y coordinate) or in an uncompressed form (give both x and y 490 coordinate). 492 2.6.2.1. curve-to-string 494 Input: 496 input_string - a point P = (x, y) on the curve 498 Output: 500 a string of k * padded_pbits 502 Steps: 504 1. If P is the point at infinity, output 0b1000...0 506 2. Parse y as y_1, ..., y_k; set y_bit as y_1 mod 2 508 3. Parse x as x_1, ..., x_k 510 4. set the substring s_1 = 0 | y_bit | padlen-2 of 0s | 511 int_to_string(x_1) 513 5. set substrings s_i = padlen of 0s | int_to_string(x_i) for 514 2<=i<=k 516 6. Output the string s_1 | s_2 | ... | s_k 518 2.6.2.2. string-to-curve 520 The algorithm takes as follows: 522 Input: 524 input_string - a single octet string. 526 Output: 528 Either a point P on the curve, or INVALID 530 Steps: 532 1. If length(input_string) is < padded_pbits/8 bytes, lead pad 533 input_string with 0s; 535 2. If length(input_string) is not a multiple of padded_pbits/8 536 bytes, tail pad with 0, ..., 0; 538 3. Parse input_string as a vector of substrings s_1, ..., s_k 540 4. b = s_1[0]; i.e., the first byte of the first substring; 542 5. If the first bit of b is 1, return P = 0 (the point at infinity) 544 6. Set y_bit to be the second bit of b and then set the second bit 545 of b to 0 547 7. If the third to plen bits of input_string are not 0, return 548 INVALID 550 8. Set x_1 = string_to_int(s_1) 552 1. if x_1 > p then return INVALID 554 9. for i in [2 ... k] 556 1. b = s_i[0] 558 2. if top plen bits of b is not 0, return INVALID 560 3. set x_i = string_to_int(s_i) 562 1. if x_1 > p then return INVALID 564 10. Set x= (x_1, ..., x_k) 565 11. solve for y so that (x, y) satisfies elliptic curve equation; 567 * output INVALID if equation is not solvable with x 569 * parse y as (y_1, ..., y_k) 571 * if solutions exist, there should be a pair of ys where y_1-s 572 differ by parity 574 * set y to be the solution where y_1 is odd if y_bit = 1 576 * set y to be the solution where y_1 is even if y_bit = 0 578 12. output P = (x, y) as a curve point. 580 TBD: check the parity property remains true for E2. The Chia and 581 Etherum implementations use lexicographic ordering. 583 2.6.2.3. alt-str-to-curve 585 The algorithm takes as follows: 587 Input: 589 input_string - a single octet string. 591 Output: 593 Either a point P on the curve, or INVALID 595 Steps: 597 1. If length(input_string) is < padded_pbits/8 bytes, lead pad 598 input_string with 0s; 600 2. If length(input_string) is not a multiple of 48 bytes, tail pad 601 with 0, ..., 0s; 603 3. Parse input_string as a vector of substrings s_1, ..., s_k 605 4. Set the first padlen bits except for the second bit of s_1[0] to 606 0 608 5. Set the first padlen bits for s_2[0], ..., s_k[0] to 0 610 6. call string_to_curve(input_string) 612 2.6.3. Hash to groups 614 The following hash_to_G1_try_and_increment algorithm implements 615 hash_to_G1 in a simple and generic way that works for any pairing- 616 friendly curve. It follows the try-and-increment approach [I-D.irtf- 617 cfrg-hash-to-curve] and uses alt_str_to_curve as a subroutine. The 618 running depends on alpha_string, and for the appropriate 619 instantiations, is expected to find a valid G1 element after 620 approximately two attempts (i.e., when ctr=1) on average. 622 The following pseudocode is adapted from draft-irtf-cfrg-vrf-03 623 Section 5.4.1.1. 625 Recall that cofactor = |E1|/|G1|. This algorithm also uses a hash 626 functions that hashes arbitrary strings into strings of 384 bits. 628 hash_to_G1_try_and_increment(suite_string, alpha_string) 630 input: suite_string - an identifier to indicate the curves and a hash 631 function that outputs k*padded_pbits bits alpha_string - the input 632 string to be hashed 634 Output: 636 H - hashed value, a point in G1 638 Steps: 640 1. ctr = 0 642 2. one_string = 0x01 = int_to_string(1, 1), a single octet with 643 value 1 645 3. H = "INVALID" 647 4. While H is "INVALID" or H is EC point at infinity: 649 1. ctr_string = int_to_string(ctr, 1) 651 2. hash_string = Hash(suite_string || one_string || 652 alpha_string || ctr_string) 654 3. H = alt_str_to_curve(hash_string) 656 4. If H is not "INVALID" and cofactor > 1, set H = cofactor * H 658 5. ctr = ctr + 1 660 5. Output H 662 Note that this hash to group function will never hash into the point 663 at infinity. This does not affect the security since the output 664 distribution is statistically indistinguishable from the uniform 665 distribution over the group. 667 2.7. Security analysis 669 The BLS signature scheme achieves strong message unforgeability and 670 aggregation unforgeability under the co-CDH assumption, namely that 671 given P1, a_P1, P2, b_P2, it is hard to compute {ab}*P1. [BLS01, 672 BGLS03] 674 3. Security Considerations 676 3.1. Verifying public keys 678 When users register a public key, we should ensure that it is well- 679 formed. This requires a G2 membership test. In applications where 680 we use aggregation, we would further require that users prove 681 knowledge of the corresponding secret key during registration to 682 prevent rogue key attacks. 684 TBA: additional discussion on this, e.g. [Ristenpart-Yilek 06], and 685 alternative mechanisms for securing aggregation against rogue key 686 attacks, e.g. [Boneh-Drijvers-Neven 18]; there, pre-processing 687 public keys would speed up verification. 689 3.2. Skipping membership check 691 Several existing implementations skip step 4 (membership in G1) in 692 Verify. In this setting, the BLS signature remains unforgeable (but 693 not strongly unforgeable) under a stronger assumption: 695 given P1, a_P1, P2, b_P2, it is hard to compute U in E1 such that 696 e(U,P2) = e(a_P1, b_P2). 698 3.3. Side channel attacks 700 It is important to protect the secret key in implementations of the 701 signing algorithm. We can protect against some side-channel attacks 702 by ensuring that the implementation executes exactly the same 703 sequence of instructions and performs exactly the same memory 704 accesses, for any value of the secret key. To achieve this, we 705 require that point multiplication in G1 should run in constant time 706 with respect to the scalar. 708 3.4. Randomness considerations 710 BLS signatures are deterministic. This protects against attacks 711 arising from signing with bad randomness. 713 3.5. Implementing the hash function 715 The security analysis models the hash function H as a random oracle, 716 and it is crucial that we implement H using a cryptographically 717 secure hash function. 723 4. Implementation Status 725 There are currently several implementations of BLS signatures using 726 the BLS12-381 curve. 728 o Algorand: TBA 730 o Chia: spec [1] python/C++ [2]. Here, they are swapping G1 and G2 731 so that the public keys are small, and the benefits of avoiding a 732 membership check during signature verification would even be more 733 substantial. The current implementation does not seem to 734 implement the membership check. Chia uses the Fouque-Tibouchi 735 hashing to the curve, which can be done in constant time. 737 o Dfinity: go [3] BLS [4]. The current implementations do not seem 738 to implement the membership check. 740 o Ethereum 2.0: spec [5] 742 5. Related Standards 744 o Pairing-friendly curves draft-yonezawa-pairing-friendly-curves [6] 746 o Pairing-based Identity-Based Encryption IEEE 1363.3 [7]. 748 o Identity-Based Cryptography Standard rfc5901 [8]. 750 o Hashing to Elliptic Curves draft-irtf-cfrg-hash-to-curve-02 [9], 751 in order to implement the hash function H. The current draft does 752 not cover pairing-friendly curves, where we need to handle curves 753 over prime power extension fields GF(p^(k).) 755 o Verifiable random functions draft-irtf-cfrg-vrf-03 [10]. 756 Section 5.4.1 also discusses instantiations for H. 758 o EdDSA rfc8032 [11] 760 6. IANA Considerations 762 This document does not make any requests of IANA. 764 7. Appendix A. Test Vectors 766 TBA: (i) test vectors for both variants of the signature scheme 767 (signatures in G2 instead of G1) , (ii) test vectors ensuring 768 membership checks, (iii) intermediate computations ctr, hm. 770 8. Reference 772 8.1. Normative References 774 [BLS 01] Dan Boneh, Ben Lynn, Hovav Shacham: Short Signatures from 775 the Weil Pairing. ASIACRYPT 2001: 514-532. 777 [BGLS 03] Dan Boneh, Craig Gentry, Ben Lynn, Hovav Shacham: Aggregate 778 and Verifiably Encrypted Signatures from Bilinear Maps. EUROCRYPT 779 2003: 416-432. 781 [I-D.irtf-cfrg-hash-to-curve] S. Scott, N. Sullivan, and C. Wood: 782 "Hashing to Elliptic Curves", draft-irtf-cfrg-hash-to-curve-01 (work 783 in progress), July 2018. 785 [I-D.pairing-friendly-curves] S. Yonezawa, S. Chikara, T. 786 Kobayashi, T. Saito: "Pairing-Friendly Curves", draft-yonezawa- 787 pairing-friendly-curves-00, Jan 2019. 789 8.2. Informative References 791 9. References 793 9.1. URIs 795 [1] https://github.com/Chia-Network/bls-signatures/blob/master/ 796 SPEC.md 798 [2] https://github.com/Chia-Network/bls-signatures 800 [3] https://github.com/dfinity/go-dfinity-crypto 802 [4] https://github.com/dfinity/bls 804 [5] https://github.com/ethereum/eth2.0-specs/blob/master/specs/ 805 bls_signature.md 807 [6] https://tools.ietf.org/html/draft-yonezawa-pairing-friendly- 808 curves-00 810 [7] https://ieeexplore.ieee.org/document/6662370 812 [8] https://tools.ietf.org/html/rfc5091 814 [9] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-02 816 [10] https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03 818 [11] https://tools.ietf.org/html/rfc8032 820 Authors' Addresses 822 Dan Boneh 823 Stanford University 824 USA 826 Email: dabo@cs.stanford.edu 828 Sergey Gorbunov 829 Algorand and University of Waterloo 830 Boston, MA 831 USA 833 Email: sgorbunov@uwaterloo.ca 835 Hoeteck Wee 836 Algorand and ENS, Paris 837 Boston, MA 838 USA 840 Email: hoeteck.wee@ens.fr 842 Zhenfei Zhang 843 Algorand 844 Boston, MA 845 USA 847 Email: zhenfei@algorand.com