idnits 2.17.1 draft-irtf-cfrg-bls-signature-05.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: ---------------------------------------------------------------------------- == There is 1 instance of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (16 June 2022) is 680 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-11) exists of draft-irtf-cfrg-pairing-friendly-curves-10 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG D. Boneh 3 Internet-Draft Stanford University 4 Intended status: Informational S. Gorbunov 5 Expires: 18 December 2022 University of Waterloo 6 R. Wahby 7 Carnegie Mellon University 8 H. Wee 9 NTT Research and ENS, Paris 10 C. Wood 11 Cloudflare, Inc. 12 Z. Zhang 13 Algorand 14 16 June 2022 16 BLS Signatures 17 draft-irtf-cfrg-bls-signature-05 19 Abstract 21 BLS is a digital signature scheme with aggregation properties. Given 22 set of signatures (signature_1, ..., signature_n) anyone can produce 23 an aggregated signature. Aggregation can also be done on secret keys 24 and public keys. Furthermore, the BLS signature scheme is 25 deterministic, non-malleable, and efficient. Its simplicity and 26 cryptographic properties allows it to be useful in a variety of use- 27 cases, specifically when minimal storage space or bandwidth are 28 required. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at https://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on 18 December 2022. 47 Copyright Notice 49 Copyright (c) 2022 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 54 license-info) in effect on the date of publication of this document. 55 Please review these documents carefully, as they describe your rights 56 and restrictions with respect to this document. Code Components 57 extracted from this document must include Revised BSD License text as 58 described in Section 4.e of the Trust Legal Provisions and are 59 provided without warranty as described in the Revised BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 64 1.1. Comparison with ECDSA . . . . . . . . . . . . . . . . . . 4 65 1.2. Organization of this document . . . . . . . . . . . . . . 4 66 1.3. Terminology and definitions . . . . . . . . . . . . . . . 5 67 1.4. API . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 68 1.5. Requirements . . . . . . . . . . . . . . . . . . . . . . 7 69 2. Core operations . . . . . . . . . . . . . . . . . . . . . . . 7 70 2.1. Variants . . . . . . . . . . . . . . . . . . . . . . . . 7 71 2.2. Parameters . . . . . . . . . . . . . . . . . . . . . . . 8 72 2.3. KeyGen . . . . . . . . . . . . . . . . . . . . . . . . . 10 73 2.4. SkToPk . . . . . . . . . . . . . . . . . . . . . . . . . 11 74 2.5. KeyValidate . . . . . . . . . . . . . . . . . . . . . . . 11 75 2.6. CoreSign . . . . . . . . . . . . . . . . . . . . . . . . 12 76 2.7. CoreVerify . . . . . . . . . . . . . . . . . . . . . . . 12 77 2.8. Aggregate . . . . . . . . . . . . . . . . . . . . . . . . 13 78 2.9. CoreAggregateVerify . . . . . . . . . . . . . . . . . . . 14 79 3. BLS Signatures . . . . . . . . . . . . . . . . . . . . . . . 14 80 3.1. Basic scheme . . . . . . . . . . . . . . . . . . . . . . 15 81 3.1.1. AggregateVerify . . . . . . . . . . . . . . . . . . . 15 82 3.2. Message augmentation . . . . . . . . . . . . . . . . . . 15 83 3.2.1. Sign . . . . . . . . . . . . . . . . . . . . . . . . 15 84 3.2.2. Verify . . . . . . . . . . . . . . . . . . . . . . . 16 85 3.2.3. AggregateVerify . . . . . . . . . . . . . . . . . . . 16 86 3.3. Proof of possession . . . . . . . . . . . . . . . . . . . 17 87 3.3.1. Parameters . . . . . . . . . . . . . . . . . . . . . 18 88 3.3.2. PopProve . . . . . . . . . . . . . . . . . . . . . . 18 89 3.3.3. PopVerify . . . . . . . . . . . . . . . . . . . . . . 19 90 3.3.4. FastAggregateVerify . . . . . . . . . . . . . . . . . 19 91 4. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 20 92 4.1. Ciphersuite format . . . . . . . . . . . . . . . . . . . 20 93 4.2. Ciphersuites for BLS12-381 . . . . . . . . . . . . . . . 22 94 4.2.1. Basic . . . . . . . . . . . . . . . . . . . . . . . . 22 95 4.2.2. Message augmentation . . . . . . . . . . . . . . . . 23 96 4.2.3. Proof of possession . . . . . . . . . . . . . . . . . 23 97 5. Security Considerations . . . . . . . . . . . . . . . . . . . 24 98 5.1. Choosing a salt value for KeyGen . . . . . . . . . . . . 24 99 5.2. Validating public keys . . . . . . . . . . . . . . . . . 25 100 5.3. Skipping membership check . . . . . . . . . . . . . . . . 25 101 5.4. Side channel attacks . . . . . . . . . . . . . . . . . . 26 102 5.5. Randomness considerations . . . . . . . . . . . . . . . . 26 103 5.6. Implementing hash_to_point and hash_pubkey_to_point . . . 26 104 6. Implementation Status . . . . . . . . . . . . . . . . . . . . 26 105 7. Related Standards . . . . . . . . . . . . . . . . . . . . . . 27 106 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 107 9. Normative References . . . . . . . . . . . . . . . . . . . . 27 108 10. Informative References . . . . . . . . . . . . . . . . . . . 27 109 Appendix A. BLS12-381 . . . . . . . . . . . . . . . . . . . . . 29 110 Appendix B. Test Vectors . . . . . . . . . . . . . . . . . . . . 30 111 Appendix C. Security analyses . . . . . . . . . . . . . . . . . 30 112 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30 114 1. Introduction 116 A signature scheme is a fundamental cryptographic primitive that is 117 used to protect authenticity and integrity of communication. Only 118 the holder of a secret key can sign messages, but anyone can verify 119 the signature using the associated public key. 121 Signature schemes are used in point-to-point secure communication 122 protocols, PKI, remote connections, etc. Designing efficient and 123 secure digital signature is very important for these applications. 125 This document describes the BLS signature scheme. The scheme enjoys 126 a variety of important efficiency properties: 128 1. The public key and the signatures are encoded as single group 129 elements. 131 2. Verification requires 2 pairing operations. 133 3. A collection of signatures (signature_1, ..., signature_n) can be 134 aggregated into a single signature. Moreover, the aggregate 135 signature can be verified using only n+1 pairings (as opposed to 136 2n pairings, when verifying n signatures separately). 138 Given the above properties, the scheme enables many interesting 139 applications. The immediate applications include 141 * Authentication and integrity for Public Key Infrastructure (PKI) 142 and blockchains. 144 - The usage is similar to classical digital signatures, such as 145 ECDSA. 147 * Aggregating signature chains for PKI and Secure Border Gateway 148 Protocol (SBGP). 150 - Concretely, in a PKI signature chain of depth n, we have n 151 signatures by n certificate authorities on n distinct 152 certificates. Similarly, in SBGP, each router receives a list 153 of n signatures attesting to a path of length n in the network. 154 In both settings, using the BLS signature scheme would allow us 155 to aggregate the n signatures into a single signature. 157 * consensus protocols for blockchains. 159 - There, BLS signatures are used for authenticating transactions 160 as well as votes during the consensus protocol, and the use of 161 aggregation significantly reduces the bandwidth and storage 162 requirements. 164 1.1. Comparison with ECDSA 166 The following comparison assumes BLS signatures with curve BLS12-381, 167 targeting 126 bits of security [GMT19]. 169 For 128 bits security, ECDSA takes 37 and 79 micro-seconds to sign 170 and verify a signature on a typical laptop. In comparison, for a 171 similar level of security, BLS takes 370 and 2700 micro-seconds to 172 sign and verify a signature. 174 In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes 175 for signatures; while BLS uses 96 bytes for public keys, and 48 bytes 176 for signatures. Alternatively, BLS can also be instantiated with 48 177 bytes of public keys and 96 bytes of signatures. BLS also allows for 178 signature aggregation. In other words, a single signature is 179 sufficient to authenticate multiple messages and public keys. 181 1.2. Organization of this document 183 This document is organized as follows: 185 * The remainder of this section defines terminology and the high- 186 level API. 188 * Section 2 defines primitive operations used in the BLS signature 189 scheme. These operations MUST NOT be used alone. 191 * Section 3 defines three BLS Signature schemes giving slightly 192 different security and performance properties. 194 * Section 4 defines the format for a ciphersuites and gives 195 recommended ciphersuites. 197 * The appendices give test vectors, etc. 199 1.3. Terminology and definitions 201 The following terminology is used through this document: 203 * SK: The secret key for the signature scheme. 205 * PK: The public key for the signature scheme. 207 * message: The input to be signed by the signature scheme. 209 * signature: The digital signature output. 211 * aggregation: Given a list of signatures for a list of messages and 212 public keys, an aggregation algorithm generates one signature that 213 authenticates the same list of messages and public keys. 215 * rogue key attack: An attack in which a specially crafted public 216 key (the "rogue" key) is used to forge an aggregated signature. 217 Section 3 specifies methods for securing against rogue key 218 attacks. 220 The following notation and primitives are used: 222 * a || b denotes the concatenation of octet strings a and b. 224 * A pairing-friendly elliptic curve defines the following primitives 225 (see [I-D.irtf-cfrg-pairing-friendly-curves] for detailed 226 discussion): 228 - E1, E2: elliptic curve groups defined over finite fields. This 229 document assumes that E1 has a more compact representation than 230 E2, i.e., because E1 is defined over a smaller field than E2. 232 - G1, G2: subgroups of E1 and E2 (respectively) having prime 233 order r. 235 - P1, P2: distinguished points that generate G1 and G2, 236 respectively. 238 - GT: a subgroup, of prime order r, of the multiplicative group 239 of a field extension. 241 - e : G1 x G2 -> GT: a non-degenerate bilinear map. 243 * For the above pairing-friendly curve, this document writes 244 operations in E1 and E2 in additive notation, i.e., P + Q denotes 245 point addition and x * P denotes scalar multiplication. 246 Operations in GT are written in multiplicative notation, i.e., a * 247 b is field multiplication. 249 * For each of E1 and E2 defined by the above pairing-friendly curve, 250 we assume that the pairing-friendly elliptic curve definition 251 provides several primitives, described below. 253 Note that these primitives are named generically. When referring 254 to one of these primitives for a specific group, this document 255 appends the name of the group, e.g., point_to_octets_E1, 256 subgroup_check_E2, etc. 258 - point_to_octets(P) -> ostr: returns the canonical 259 representation of the point P as an octet string. This 260 operation is also known as serialization. 262 - octets_to_point(ostr) -> P: returns the point P corresponding 263 to the canonical representation ostr, or INVALID if ostr is not 264 a valid output of point_to_octets. This operation is also 265 known as deserialization. 267 - subgroup_check(P) -> VALID or INVALID: returns VALID when the 268 point P is an element of the subgroup of order r, and INVALID 269 otherwise. This function can always be implemented by checking 270 that r * P is equal to the identity element. In some cases, 271 faster checks may also exist, e.g., [Bowe19]. 273 * I2OSP and OS2IP are the functions defined in [RFC8017], Section 4. 275 * hash_to_point(ostr) -> P: a cryptographic hash function that takes 276 as input an arbitrary octet string and returns a point on an 277 elliptic curve. Functions of this kind are defined in 278 [I-D.irtf-cfrg-hash-to-curve]. Each of the ciphersuites in 279 Section 4 specifies the hash_to_point algorithm to be used. 281 1.4. API 283 The BLS signature scheme defines the following API: 285 * KeyGen(IKM) -> SK: a key generation algorithm that takes as input 286 an octet string comprising secret keying material, and outputs a 287 secret key SK. 289 * SkToPk(SK) -> PK: an algorithm that takes as input a secret key 290 and outputs the corresponding public key. 292 * Sign(SK, message) -> signature: a signing algorithm that generates 293 a deterministic signature given a secret key SK and a message. 295 * Verify(PK, message, signature) -> VALID or INVALID: a verification 296 algorithm that outputs VALID if signature is a valid signature of 297 message under public key PK, and INVALID otherwise. 299 * Aggregate((signature_1, ..., signature_n)) -> signature: an 300 aggregation algorithm that aggregates a collection of signatures 301 into a single signature. 303 * AggregateVerify((PK_1, ..., PK_n), (message_1, ..., message_n), 304 signature) -> VALID or INVALID: an aggregate verification 305 algorithm that outputs VALID if signature is a valid aggregated 306 signature for a collection of public keys and messages, and 307 outputs INVALID otherwise. 309 1.5. Requirements 311 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 312 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 313 document are to be interpreted as described in [RFC2119]. 315 2. Core operations 317 This section defines core operations used by the schemes defined in 318 Section 3. These operations MUST NOT be used except as described in 319 that section. 321 2.1. Variants 323 Each core operation has two variants that trade off signature and 324 public key size: 326 1. Minimal-signature-size: signatures are points in G1, public keys 327 are points in G2. (Recall from Section 1.3 that E1 has a more 328 compact representation than E2.) 330 2. Minimal-pubkey-size: public keys are points in G1, signatures are 331 points in G2. 333 Implementations using signature aggregation SHOULD use this 334 approach, since the size of (PK_1, ..., PK_n, signature) is 335 dominated by the public keys even for small n. 337 2.2. Parameters 339 The core operations in this section depend on several parameters: 341 * A signature variant, either minimal-signature-size or minimal- 342 pubkey-size. These are defined in Section 2.1. 344 * A pairing-friendly elliptic curve, plus associated functionality 345 given in Section 1.3. 347 * H, a hash function that MUST be a secure cryptographic hash 348 function, e.g., SHA-256 [FIPS180-4]. For security, H MUST output 349 at least ceil(log2(r)) bits, where r is the order of the subgroups 350 G1 and G2 defined by the pairing-friendly elliptic curve. 352 * hash_to_point, a function whose interface is described in 353 Section 1.3. When the signature variant is minimal-signature- 354 size, this function MUST output a point in G1. When the signature 355 variant is minimal-pubkey size, this function MUST output a point 356 in G2. For security, this function MUST be either a random oracle 357 encoding or a nonuniform encoding, as defined in 358 [I-D.irtf-cfrg-hash-to-curve]. 360 In addition, the following primitives are determined by the above 361 parameters: 363 * P, an elliptic curve point. When the signature variant is 364 minimal-signature-size, P is the distinguished point P2 that 365 generates the group G2 (see Section 1.3). When the signature 366 variant is minimal-pubkey-size, P is the distinguished point P1 367 that generates the group G1. 369 * r, the order of the subgroups G1 and G2 defined by the pairing- 370 friendly curve. 372 * pairing, a function that invokes the function e of Section 1.3, 373 with argument order depending on signature variant: 375 - For minimal-signature-size: 377 pairing(U, V) := e(U, V) 379 - For minimal-pubkey-size: 381 pairing(U, V) := e(V, U) 383 * point_to_pubkey and point_to_signature, functions that invoke the 384 appropriate serialization routine (Section 1.3) depending on 385 signature variant: 387 - For minimal-signature-size: 389 point_to_pubkey(P) := point_to_octets_E2(P) 391 point_to_signature(P) := point_to_octets_E1(P) 393 - For minimal-pubkey-size: 395 point_to_pubkey(P) := point_to_octets_E1(P) 397 point_to_signature(P) := point_to_octets_E2(P) 399 * pubkey_to_point and signature_to_point, functions that invoke the 400 appropriate deserialization routine (Section 1.3) depending on 401 signature variant: 403 - For minimal-signature-size: 405 pubkey_to_point(ostr) := octets_to_point_E2(ostr) 407 signature_to_point(ostr) := octets_to_point_E1(ostr) 409 - For minimal-pubkey-size: 411 pubkey_to_point(ostr) := octets_to_point_E1(ostr) 413 signature_to_point(ostr) := octets_to_point_E2(ostr) 415 * pubkey_subgroup_check and signature_subgroup_check, functions that 416 invoke the appropriate subgroup check routine (Section 1.3) 417 depending on signature variant: 419 - For minimal-signature-size: 421 pubkey_subgroup_check(P) := subgroup_check_E2(P) 423 signature_subgroup_check(P) := subgroup_check_E1(P) 425 - For minimal-pubkey-size: 427 pubkey_subgroup_check(P) := subgroup_check_E1(P) 428 signature_subgroup_check(P) := subgroup_check_E2(P) 430 2.3. KeyGen 432 The KeyGen procedure described in this section generates a secret key 433 SK deterministically from a secret octet string IKM. SK is 434 guaranteed to be nonzero, as required by KeyValidate (Section 2.5). 436 KeyGen uses HKDF [RFC5869] instantiated with the hash function H. 438 For security, IKM MUST be infeasible to guess, e.g., generated by a 439 trusted source of randomness. IKM MUST be at least 32 bytes long, 440 but it MAY be longer. 442 KeyGen takes two parameters. The first parameter, salt, is required; 443 see below for further discussion of this value. The second 444 parameter, key_info, is optional; it MAY be used to derive multiple 445 independent keys from the same IKM. By default, key_info is the 446 empty string. 448 SK = KeyGen(IKM) 450 Inputs: 451 - IKM, a secret octet string. See requirements above. 453 Outputs: 454 - SK, a uniformly random integer such that 1 <= SK < r. 456 Parameters: 457 - salt, a required octet string. 458 - key_info, an optional octet string. 459 If key_info is not supplied, it defaults to the empty string. 461 Definitions: 462 - HKDF-Extract is as defined in RFC5869, instantiated with hash H. 463 - HKDF-Expand is as defined in RFC5869, instantiated with hash H. 464 - I2OSP and OS2IP are as defined in RFC8017, Section 4. 465 - L is the integer given by ceil((3 * ceil(log2(r))) / 16). 467 Procedure: 468 1. while True: 469 2. PRK = HKDF-Extract(salt, IKM || I2OSP(0, 1)) 470 3. OKM = HKDF-Expand(PRK, key_info || I2OSP(L, 2), L) 471 4. SK = OS2IP(OKM) mod r 472 5. if SK != 0: 473 6. return SK 474 7. salt = H(salt) 475 KeyGen is the RECOMMENDED way of generating secret keys, but its use 476 is not required for compatibility, and implementations MAY use a 477 different KeyGen procedure. For security, such an alternative KeyGen 478 procedure MUST output SK that is statistically close to uniformly 479 random in the range 1 <= SK < r. 481 For compatibility with prior versions of this document, 482 implementations SHOULD allow applications to choose the salt value. 483 Setting salt to the value H("BLS-SIG-KEYGEN-SALT-") (i.e., the hash 484 of an ASCII string comprising 20 octets) results in a KeyGen 485 algorithm that is compatible with version 4 of this document. 486 Setting salt to the value "BLS-SIG-KEYGEN-SALT-" (i.e., an ASCII 487 string comprising 20 octets) results in a KeyGen algorithm that is 488 compatible with versions of this document prior to number 4. See 489 Section 5.1 for more information on choosing a salt value. 491 2.4. SkToPk 493 The SkToPk algorithm takes a secret key SK and outputs the 494 corresponding public key PK. Section 2.3 discusses requirements for 495 SK. 497 PK = SkToPk(SK) 499 Inputs: 500 - SK, a secret integer such that 1 <= SK < r. 502 Outputs: 503 - PK, a public key encoded as an octet string. 505 Procedure: 506 1. xP = SK * P 507 2. PK = point_to_pubkey(xP) 508 3. return PK 510 2.5. KeyValidate 512 The KeyValidate algorithm ensures that a public key is valid. In 513 particular, it ensures that a public key represents a valid, non- 514 identity point that is in the correct subgroup. See Section 5.2 for 515 further discussion. 517 As an optimization, implementations MAY cache the result of 518 KeyValidate in order to avoid unnecessarily repeating validation for 519 known keys. 521 result = KeyValidate(PK) 523 Inputs: 524 - PK, a public key in the format output by SkToPk. 526 Outputs: 527 - result, either VALID or INVALID 529 Procedure: 530 1. xP = pubkey_to_point(PK) 531 2. If xP is INVALID, return INVALID 532 3. If xP is the identity element, return INVALID 533 4. If pubkey_subgroup_check(xP) is INVALID, return INVALID 534 5. return VALID 536 2.6. CoreSign 538 The CoreSign algorithm computes a signature from SK, a secret key, 539 and message, an octet string. 541 signature = CoreSign(SK, message) 543 Inputs: 544 - SK, a secret key in the format output by KeyGen. 545 - message, an octet string. 547 Outputs: 548 - signature, an octet string. 550 Procedure: 551 1. Q = hash_to_point(message) 552 2. R = SK * Q 553 3. signature = point_to_signature(R) 554 4. return signature 556 2.7. CoreVerify 558 The CoreVerify algorithm checks that a signature is valid for the 559 octet string message under the public key PK. 561 result = CoreVerify(PK, message, signature) 563 Inputs: 564 - PK, a public key in the format output by SkToPk. 565 - message, an octet string. 566 - signature, an octet string in the format output by CoreSign. 568 Outputs: 569 - result, either VALID or INVALID. 571 Procedure: 572 1. R = signature_to_point(signature) 573 2. If R is INVALID, return INVALID 574 3. If signature_subgroup_check(R) is INVALID, return INVALID 575 4. If KeyValidate(PK) is INVALID, return INVALID 576 5. xP = pubkey_to_point(PK) 577 6. Q = hash_to_point(message) 578 7. C1 = pairing(Q, xP) 579 8. C2 = pairing(R, P) 580 9. If C1 == C2, return VALID, else return INVALID 582 2.8. Aggregate 584 The Aggregate algorithm aggregates multiple signatures into one. 586 signature = Aggregate((signature_1, ..., signature_n)) 588 Inputs: 589 - signature_1, ..., signature_n, octet strings output by 590 either CoreSign or Aggregate. 592 Outputs: 593 - signature, an octet string encoding a aggregated signature 594 that combines all inputs; or INVALID. 596 Precondition: n >= 1, otherwise return INVALID. 598 Procedure: 599 1. aggregate = signature_to_point(signature_1) 600 2. If aggregate is INVALID, return INVALID 601 3. for i in 2, ..., n: 602 4. next = signature_to_point(signature_i) 603 5. If next is INVALID, return INVALID 604 6. aggregate = aggregate + next 605 7. signature = point_to_signature(aggregate) 606 8. return signature 608 2.9. CoreAggregateVerify 610 The CoreAggregateVerify algorithm checks an aggregated signature over 611 several (PK, message) pairs. 613 result = CoreAggregateVerify((PK_1, ..., PK_n), 614 (message_1, ... message_n), 615 signature) 617 Inputs: 618 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 619 - message_1, ..., message_n, octet strings. 620 - signature, an octet string output by Aggregate. 622 Outputs: 623 - result, either VALID or INVALID. 625 Precondition: n >= 1, otherwise return INVALID. 627 Procedure: 628 1. R = signature_to_point(signature) 629 2. If R is INVALID, return INVALID 630 3. If signature_subgroup_check(R) is INVALID, return INVALID 631 4. C1 = 1 (the identity element in GT) 632 5. for i in 1, ..., n: 633 6. If KeyValidate(PK_i) is INVALID, return INVALID 634 7. xP = pubkey_to_point(PK_i) 635 8. Q = hash_to_point(message_i) 636 9. C1 = C1 * pairing(Q, xP) 637 10. C2 = pairing(R, P) 638 11. If C1 == C2, return VALID, else return INVALID 640 3. BLS Signatures 642 This section defines three signature schemes: basic, message 643 augmentation, and proof of possession. These schemes differ in the 644 ways that they defend against rogue key attacks (Section 1.3). 646 All of the schemes in this section are built on a set of core 647 operations defined in Section 2. Thus, defining a scheme requires 648 fixing a set of parameters as defined in Section 2.2. 650 All three schemes expose the KeyGen, SkToPk, and Aggregate operations 651 that are defined in Section 2. The sections below define the other 652 API functions (Section 1.4) for each scheme. 654 3.1. Basic scheme 656 In a basic scheme, rogue key attacks are handled by requiring all 657 messages signed by an aggregate signature to be distinct. This 658 requirement is enforced in the definition of AggregateVerify. 660 The Sign and Verify functions are identical to CoreSign and 661 CoreVerify (Section 2), respectively. AggregateVerify is defined 662 below. 664 3.1.1. AggregateVerify 666 This function first ensures that all messages are distinct, and then 667 invokes CoreAggregateVerify. 669 result = AggregateVerify((PK_1, ..., PK_n), 670 (message_1, ..., message_n), 671 signature) 673 Inputs: 674 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 675 - message_1, ..., message_n, octet strings. 676 - signature, an octet string output by Aggregate. 678 Outputs: 679 - result, either VALID or INVALID. 681 Precondition: n >= 1, otherwise return INVALID. 683 Procedure: 684 1. If any two input messages are equal, return INVALID. 685 2. return CoreAggregateVerify((PK_1, ..., PK_n), 686 (message_1, ..., message_n), 687 signature) 689 3.2. Message augmentation 691 In a message augmentation scheme, signatures are generated over the 692 concatenation of the public key and the message, ensuring that 693 messages signed by different public keys are distinct. 695 3.2.1. Sign 697 To match the API for Sign defined in Section 1.4, this function 698 recomputes the public key corresponding to the input SK. 699 Implementations MAY instead implement an interface that takes the 700 public key as an input. 702 Note that the point P and the point_to_pubkey function are defined in 703 Section 2.2. 705 signature = Sign(SK, message) 707 Inputs: 708 - SK, a secret key in the format output by KeyGen. 709 - message, an octet string. 711 Outputs: 712 - signature, an octet string. 714 Procedure: 715 1. PK = SkToPk(SK) 716 2. return CoreSign(SK, PK || message) 718 3.2.2. Verify 720 result = Verify(PK, message, signature) 722 Inputs: 723 - PK, a public key in the format output by SkToPk. 724 - message, an octet string. 725 - signature, an octet string in the format output by CoreSign. 727 Outputs: 728 - result, either VALID or INVALID. 730 Procedure: 731 1. return CoreVerify(PK, PK || message, signature) 733 3.2.3. AggregateVerify 734 result = AggregateVerify((PK_1, ..., PK_n), 735 (message_1, ..., message_n), 736 signature) 738 Inputs: 739 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 740 - message_1, ..., message_n, octet strings. 741 - signature, an octet string output by Aggregate. 743 Outputs: 744 - result, either VALID or INVALID. 746 Precondition: n >= 1, otherwise return INVALID. 748 Procedure: 749 1. for i in 1, ..., n: 750 2. mprime_i = PK_i || message_i 751 3. return CoreAggregateVerify((PK_1, ..., PK_n), 752 (mprime_1, ..., mprime_n), 753 signature) 755 3.3. Proof of possession 757 A proof of possession scheme uses a separate public key validation 758 step, called a proof of possession, to defend against rogue key 759 attacks. This enables an optimization to aggregate signature 760 verification for the case that all signatures are on the same 761 message. 763 The Sign, Verify, and AggregateVerify functions are identical to 764 CoreSign, CoreVerify, and CoreAggregateVerify (Section 2), 765 respectively. In addition, a proof of possession scheme defines 766 three functions beyond the standard API (Section 1.4): 768 * PopProve(SK) -> proof: an algorithm that generates a proof of 769 possession for the public key corresponding to secret key SK. 771 * PopVerify(PK, proof) -> VALID or INVALID: an algorithm that 772 outputs VALID if proof is valid for PK, and INVALID otherwise. 774 * FastAggregateVerify((PK_1, ..., PK_n), message, signature) -> 775 VALID or INVALID: a verification algorithm for the aggregate of 776 multiple signatures on the same message. This function is faster 777 than AggregateVerify. 779 All public keys used by Verify, AggregateVerify, and 780 FastAggregateVerify MUST be accompanied by a proof of possession, and 781 the result of evaluating PopVerify on each public key and its proof 782 MUST be VALID. 784 3.3.1. Parameters 786 In addition to the parameters required to instantiate the core 787 operations (Section 2.2), a proof of possession scheme requires one 788 further parameter: 790 * hash_pubkey_to_point(PK) -> P: a cryptographic hash function that 791 takes as input a public key and outputs a point in the same 792 subgroup as the hash_to_point algorithm used to instantiate the 793 core operations. 795 For security, this function MUST be domain separated from the 796 hash_to_point function. In addition, this function MUST be either 797 a random oracle encoding or a nonuniform encoding, as defined in 798 [I-D.irtf-cfrg-hash-to-curve]. 800 The RECOMMENDED way of instantiating hash_pubkey_to_point is to 801 use the same hash-to-curve function as hash_to_point, with a 802 different domain separation tag (see 803 [I-D.irtf-cfrg-hash-to-curve], Section 3.1). Section 4.1 804 discusses the RECOMMENDED way to construct the domain separation 805 tag. 807 3.3.2. PopProve 809 This function recomputes the public key coresponding to the input SK. 810 Implementations MAY instead implement an interface that takes the 811 public key as input. 813 Note that the point P and the point_to_pubkey and point_to_signature 814 functions are defined in Section 2.2. The hash_pubkey_to_point 815 function is defined in Section 3.3.1. 817 proof = PopProve(SK) 819 Inputs: 820 - SK, a secret key in the format output by KeyGen. 822 Outputs: 823 - proof, an octet string. 825 Procedure: 826 1. PK = SkToPk(SK) 827 2. Q = hash_pubkey_to_point(PK) 828 3. R = SK * Q 829 4. proof = point_to_signature(R) 830 5. return proof 832 3.3.3. PopVerify 834 PopVerify uses several functions defined in Section 2. The 835 hash_pubkey_to_point function is defined in Section 3.3.1. 837 As an optimization, implementations MAY cache the result of PopVerify 838 in order to avoid unnecessarily repeating validation for known keys. 840 result = PopVerify(PK, proof) 842 Inputs: 843 - PK, a public key in the format output by SkToPk. 844 - proof, an octet string in the format output by PopProve. 846 Outputs: 847 - result, either VALID or INVALID 849 Procedure: 850 1. R = signature_to_point(proof) 851 2. If R is INVALID, return INVALID 852 3. If signature_subgroup_check(R) is INVALID, return INVALID 853 4. If KeyValidate(PK) is INVALID, return INVALID 854 5. xP = pubkey_to_point(PK) 855 6. Q = hash_pubkey_to_point(PK) 856 7. C1 = pairing(Q, xP) 857 8. C2 = pairing(R, P) 858 9. If C1 == C2, return VALID, else return INVALID 860 3.3.4. FastAggregateVerify 862 FastAggregateVerify uses several functions defined in Section 2. 864 All public keys passed as arguments to this algorithm MUST have a 865 corresponding proof of possession, and the result of evaluating 866 PopVerify on each public key and its proof MUST be VALID. The caller 867 is responsible for ensuring that this precondition is met. If it is 868 violated, this scheme provides no security against aggregate 869 signature forgery. 871 result = FastAggregateVerify((PK_1, ..., PK_n), message, signature) 873 Inputs: 874 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 875 - message, an octet string. 876 - signature, an octet string output by Aggregate. 878 Outputs: 879 - result, either VALID or INVALID. 881 Preconditions: 882 - n >= 1, otherwise return INVALID. 883 - The caller MUST know a proof of possession for all PK_i, and the 884 result of evaluating PopVerify on PK_i and this proof MUST be VALID. 885 See discussion above. 887 Procedure: 888 1. aggregate = pubkey_to_point(PK_1) 889 2. for i in 2, ..., n: 890 3. next = pubkey_to_point(PK_i) 891 4. aggregate = aggregate + next 892 5. PK = point_to_pubkey(aggregate) 893 6. return CoreVerify(PK, message, signature) 895 4. Ciphersuites 897 This section defines the format for a BLS ciphersuite. It also gives 898 concrete ciphersuites based on the BLS12-381 pairing-friendly 899 elliptic curve [I-D.irtf-cfrg-pairing-friendly-curves]. 901 4.1. Ciphersuite format 903 A ciphersuite specifies all parameters from Section 2.2, a scheme 904 from Section 3, and any parameters the scheme requires. In 905 particular, a ciphersuite comprises: 907 * ID: the ciphersuite ID, an ASCII string. The REQUIRED format for 908 this string is 910 "BLS_SIG_" || H2C_SUITE_ID || SC_TAG || "_" 911 - Strings in double quotes are ASCII-encoded literals. 913 - H2C_SUITE_ID is the suite ID of the hash-to-curve suite used to 914 define the hash_to_point and hash_pubkey_to_point functions. 916 - SC_TAG is a string indicating the scheme and, optionally, 917 additional information. The first three characters of this 918 string MUST chosen as follows: 920 o "NUL" if SC is basic, 922 o "AUG" if SC is message-augmentation, or 924 o "POP" if SC is proof-of-possession. 926 o Other values MUST NOT be used. 928 SC_TAG MAY be used to encode other information about the 929 ciphersuite, for example, a version number. When used in this 930 way, SC_TAG MUST contain only ASCII characters between 0x21 and 931 0x7e (inclusive), except that it MUST NOT contain underscore 932 (0x5f). 934 The RECOMMENDED way to add user-defined information to SC_TAG 935 is to append a colon (':', ASCII 0x3a) and then the 936 informational string. For example, "NUL:version=2" is an 937 appropriate SC_TAG value. 939 Note that hash-to-curve suite IDs always include a trailing 940 underscore, so no field separator is needed between H2C_SUITE_ID 941 and SC_TAG. 943 * SC: the scheme, one of basic, message-augmentation, or proof-of- 944 possession. 946 * SV: the signature variant, either minimal-signature-size or 947 minimal-pubkey-size. 949 * EC: a pairing-friendly elliptic curve, plus all associated 950 functionality (Section 1.3). 952 * H: a cryptographic hash function. 954 * hash_to_point: a hash from arbitrary strings to elliptic curve 955 points. hash_to_point MUST be defined in terms of a hash-to-curve 956 suite [I-D.irtf-cfrg-hash-to-curve]. 958 The RECOMMENDED hash-to-curve domain separation tag is the 959 ciphersuite ID string defined above. 961 * hash_pubkey_to_point (only specified when SC is proof-of- 962 possession): a hash from serialized public keys to elliptic curve 963 points. hash_pubkey_to_point MUST be defined in terms of a hash- 964 to-curve suite [I-D.irtf-cfrg-hash-to-curve]. 966 The hash-to-curve domain separation tag MUST be distinct from the 967 domain separation tag used for hash_to_point. It is RECOMMENDED 968 that the domain separation tag be constructed similarly to the 969 ciphersuite ID string, namely: 971 "BLS_POP_" || H2C_SUITE_ID || SC_TAG || "_" 973 4.2. Ciphersuites for BLS12-381 975 The following ciphersuites are all built on the BLS12-381 elliptic 976 curve. The required primitives for this curve are given in 977 Appendix A. 979 These ciphersuites use the hash-to-curve suites BLS12381G1_XMD:SHA- 980 256_SSWU_RO_ and BLS12381G2_XMD:SHA-256_SSWU_RO_ defined in 981 [I-D.irtf-cfrg-hash-to-curve], Section 8.7. Each ciphersuite defines 982 a unique hash_to_point function by specifying a domain separation tag 983 (see [@I-D.irtf-cfrg-hash-to-curve, Section 3.1). 985 4.2.1. Basic 987 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_NUL_ is defined as follows: 989 * SC: basic 991 * SV: minimal-signature-size 993 * EC: BLS12-381, as defined in Appendix A. 995 * H: SHA-256 997 * hash_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the ASCII- 998 encoded domain separation tag 1000 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_NUL_ 1002 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_NUL_ is identical to 1003 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_NUL_, except for the following 1004 parameters: 1006 * SV: minimal-pubkey-size 1008 * hash_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the ASCII- 1009 encoded domain separation tag 1011 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_NUL_ 1013 4.2.2. Message augmentation 1015 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_AUG_ is defined as follows: 1017 * SC: message-augmentation 1019 * SV: minimal-signature-size 1021 * EC: BLS12-381, as defined in Appendix A. 1023 * H: SHA-256 1025 * hash_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the ASCII- 1026 encoded domain separation tag 1028 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_AUG_ 1030 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_AUG_ is identical to 1031 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_AUG_, except for the following 1032 parameters: 1034 * SV: minimal-pubkey-size 1036 * hash_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the ASCII- 1037 encoded domain separation tag 1039 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_AUG_ 1041 4.2.3. Proof of possession 1043 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_ is defined as follows: 1045 * SC: proof-of-possession 1047 * SV: minimal-signature-size 1049 * EC: BLS12-381, as defined in Appendix A. 1051 * H: SHA-256 1052 * hash_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the ASCII- 1053 encoded domain separation tag 1055 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_ 1057 * hash_pubkey_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the 1058 ASCII-encoded domain separation tag 1060 BLS_POP_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_ 1062 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_ is identical to 1063 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_, except for the following 1064 parameters: 1066 * SV: minimal-pubkey-size 1068 * hash_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the ASCII- 1069 encoded domain separation tag 1071 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_ 1073 * hash_pubkey_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the 1074 ASCII-encoded domain separation tag 1076 BLS_POP_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_ 1078 5. Security Considerations 1080 5.1. Choosing a salt value for KeyGen 1082 KeyGen uses HKDF to generate keys. The security analysis of HKDF 1083 assumes that the salt value is either empty (in which case it is 1084 replaced by the all-zeros string) or an unstructured string. 1085 Versions of this document prior to number 4 set the salt parameter to 1086 "BLS-SIG-KEYGEN-SALT-", which does not meet this requirement. If, as 1087 is common, the hash function H is modeled as a random oracle, this 1088 requirement is obviated. 1090 When choosing a salt value other than "BLS-SIG-KEYGEN-SALT-" or 1091 H("BLS-SIG-KEYGEN-SALT-"), the RECOMMENDED method is to fix a 1092 uniformly random octet string whose length equals the output length 1093 of H. 1095 5.2. Validating public keys 1097 All algorithms in Section 2 and Section 3 that operate on public keys 1098 require first validating those keys. For the basic and message 1099 augmentation schemes, the use of KeyValidate is REQUIRED. For the 1100 proof of possession scheme, each public key MUST be accompanied by a 1101 proof of possession, and use of PopVerify is REQUIRED. 1103 KeyValidate requires all public keys to represent valid, non-identity 1104 points in the correct subgroup. A valid point and subgroup 1105 membership are required to ensure that the pairing operation is 1106 defined (Section 5.3). 1108 A non-identity point is required because the identity public key has 1109 the property that the corresponding secret key is equal to zero, 1110 which means that the identity point is the unique valid signature for 1111 every message under this key. A malicious signer could take 1112 advantage of this fact to equivocate about which message he signed. 1113 While non-equivocation is not a required property for a signature 1114 scheme, equivocation is infeasible for BLS signatures under any 1115 nonzero secret key because it would require finding colliding inputs 1116 to the hash_to_point function, which is assumed to be collision 1117 resistant. Prohibiting SK == 0 eliminates the exceptional case, 1118 which may help to prevent equivocation-related security issues in 1119 protocols that use BLS signatures. 1121 5.3. Skipping membership check 1123 Some existing implementations skip the signature_subgroup_check 1124 invocation in CoreVerify (Section 2.7), whose purpose is ensuring 1125 that the signature is an element of a prime-order subgroup. This 1126 check is REQUIRED of conforming implementations, for two reasons. 1128 1. For most pairing-friendly elliptic curves used in practice, the 1129 pairing operation e (Section 1.3) is undefined when its input 1130 points are not in the prime-order subgroups of E1 and E2. The 1131 resulting behavior is unpredictable, and may enable forgeries. 1133 2. Even if the pairing operation behaves properly on inputs that are 1134 outside the correct subgroups, skipping the subgroup check breaks 1135 the strong unforgeability property [ADR02]. 1137 5.4. Side channel attacks 1139 Implementations of the signing algorithm SHOULD protect the secret 1140 key from side-channel attacks. One method for protecting against 1141 certain side-channel attacks is ensuring that the implementation 1142 executes exactly the same sequence of instructions and performs 1143 exactly the same memory accesses, for any value of the secret key. 1144 In other words, implementations on the underlying pairing-friendly 1145 elliptic curve SHOULD run in constant time. 1147 5.5. Randomness considerations 1149 BLS signatures are deterministic. This protects against attacks 1150 arising from signing with bad randomness, for example, the nonce 1151 reuse attack on ECDSA [HDWH12]. 1153 As discussed in Section 2.3, the IKM input to KeyGen MUST be 1154 infeasible to guess and MUST be kept secret. One possibility is to 1155 generate IKM from a trusted source of randomness. Guidelines on 1156 constructing such a source are outside the scope of this document. 1158 5.6. Implementing hash_to_point and hash_pubkey_to_point 1160 The security analysis models hash_to_point and hash_pubkey_to_point 1161 as random oracles. It is crucial that these functions are 1162 implemented using a cryptographically secure hash function. For this 1163 purpose, implementations MUST meet the requirements of 1164 [I-D.irtf-cfrg-hash-to-curve]. 1166 In addition, ciphersuites MUST specify unique domain separation tags 1167 for hash_to_point and hash_pubkey_to_point. The domain separation 1168 tag format used in Section 4 is the RECOMMENDED one. 1170 6. Implementation Status 1172 This section will be removed in the final version of the draft. 1173 There are currently several implementations of BLS signatures using 1174 the BLS12-381 curve. 1176 * Algorand: bls_sigs_ref (https://github.com/kwantam/bls_sigs_ref). 1178 * Chia: spec (https://github.com/Chia-Network/bls- 1179 signatures/blob/master/SPEC.md) python/C++ (https://github.com/ 1180 Chia-Network/bls-signatures). Here, they are swapping G1 and G2 1181 so that the public keys are small, and the benefits of avoiding a 1182 membership check during signature verification would even be more 1183 substantial. The current implementation does not seem to 1184 implement the membership check. Chia uses the Fouque-Tibouchi 1185 hashing to the curve, which can be done in constant time. 1187 * Dfinity: go (https://github.com/dfinity/go-dfinity-crypto) BLS 1188 (https://github.com/dfinity/bls). The current implementations do 1189 not seem to implement the membership check. 1191 * Ethereum 2.0: spec (https://github.com/ethereum/eth2.0- 1192 specs/blob/master/specs/bls_signature.md). 1194 7. Related Standards 1196 * Pairing-friendly curves, [I-D.irtf-cfrg-pairing-friendly-curves] 1198 * Pairing-based Identity-Based Encryption IEEE 1363.3 1199 (https://ieeexplore.ieee.org/document/6662370). 1201 * Identity-Based Cryptography Standard rfc5901 1202 (https://tools.ietf.org/html/rfc5091). 1204 * Hashing to Elliptic Curves [I-D.irtf-cfrg-hash-to-curve], in order 1205 to implement the hash function hash_to_point. 1207 * EdDSA rfc8032 (https://tools.ietf.org/html/rfc8032). 1209 8. IANA Considerations 1211 TBD (consider to register ciphersuite identifiers for BLS signature 1212 and underlying pairing curves) 1214 9. Normative References 1216 [ZCash] Electric Coin Company, "BLS12-381", July 2017, . 1220 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1221 Requirement Levels", BCP 14, RFC 2119, 1222 DOI 10.17487/RFC2119, March 1997, 1223 . 1225 10. Informative References 1227 [Bol03] Boldyreva, A., "Threshold Signatures, Multisignatures and 1228 Blind Signatures Based on the Gap-Diffie-Hellman-Group 1229 Signature Scheme", January 2003, 1230 . 1233 [I-D.irtf-cfrg-pairing-friendly-curves] 1234 Sakemi, Y., Kobayashi, T., Saito, T., and R. S. Wahby, 1235 "Pairing-Friendly Curves", Work in Progress, Internet- 1236 Draft, draft-irtf-cfrg-pairing-friendly-curves-10, 30 July 1237 2021, . 1240 [Bowe19] Bowe, S., "Faster subgroup checks for BLS12-381", July 1241 2019, . 1243 [ADR02] An, J. H., Dodis, Y., and T. Rabin, "On the Security of 1244 Joint Signature and Encryption", April 2002, 1245 . 1247 [BLS01] Boneh, D., Lynn, B., and H. Shacham, "Short signatures 1248 from the Weil pairing", December 2001, 1249 . 1251 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1252 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1253 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1254 . 1256 [Scott21] Scott, M., "A note on group membership tests for G1, G2 1257 and GT on BLS pairing-friendly curves", September 2021, 1258 . 1260 [LOSSW06] Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., and B. 1261 Waters, "Sequential Aggregate Signatures and 1262 Multisignatures Without Random Oracles", May 2006, 1263 . 1265 [RY07] Ristenpart, T. and S. Yilek, "The Power of Proofs-of- 1266 Possession: Securing Multiparty Signatures against Rogue- 1267 Key Attacks", May 2007, . 1270 [GMT19] Guillevic, A., Masson, S., and E. Thome, "Cocks–Pinch 1271 curves of embedding degrees five to eight and optimal ate 1272 pairing computation", 2019. 1274 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1275 Key Derivation Function (HKDF)", RFC 5869, 1276 DOI 10.17487/RFC5869, May 2010, 1277 . 1279 [BGLS03] Boneh, D., Gentry, C., Lynn, B., and H. Shacham, 1280 "Aggregate and verifiably encrypted signatures from 1281 bilinear maps", May 2003, . 1284 [BNN07] Bellare, M., Namprempre, C., and G. Neven, "Unrestricted 1285 aggregate signatures", July 2007, 1286 . 1289 [BDN18] Boneh, D., Drijvers, M., and G. Neven, "Compact multi- 1290 signatures for shorter blockchains", December 2018, 1291 . 1294 [I-D.irtf-cfrg-hash-to-curve] 1295 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., 1296 and C. A. Wood, "Hashing to Elliptic Curves", Work in 1297 Progress, Internet-Draft, draft-irtf-cfrg-hash-to-curve- 1298 16, 15 June 2022, . 1301 [FIPS180-4] 1302 National Institute of Standards and Technology (NIST), 1303 "FIPS Publication 180-4: Secure Hash Standard", August 1304 2015, . 1307 [HDWH12] Heninger, N., Durumeric, Z., Wustrow, E., and J.A. 1308 Halderman, "Mining your Ps and Qs: Detection of widespread 1309 weak keys in network devices", August 2012, 1310 . 1313 Appendix A. BLS12-381 1315 The ciphersuites in Section 4 are based upon the BLS12-381 pairing- 1316 friendly elliptic curve. The following defines the correspondence 1317 between the primitives in Section 1.3 and the parameters given in 1318 Section 4.2.1 of [I-D.irtf-cfrg-pairing-friendly-curves]. 1320 * E1, G1: the curve E and its order-r subgroup. 1322 * E2, G2: the curve E' and its order-r subgroup. 1324 * GT: the subgroup G_T. 1326 * P1: the point BP. 1328 * P2: the point BP'. 1330 * e: the optimal Ate pairing defined in Appendix A of 1331 [I-D.irtf-cfrg-pairing-friendly-curves]. 1333 * point_to_octets and octets_to_point use the compressed 1334 serialization formats for E1 and E2 defined by [ZCash]. 1336 * subgroup_check MAY use either the naive check described in 1337 Section 1.3 or the optimized checks given by [Bowe19] or 1338 [Scott21]. 1340 Appendix B. Test Vectors 1342 TBA: (i) test vectors for both variants of the signature scheme 1343 (signatures in G2 instead of G1) , (ii) test vectors ensuring 1344 membership checks, (iii) intermediate computations ctr, hm. 1346 Appendix C. Security analyses 1348 The security properties of the BLS signature scheme are proved in 1349 [BLS01]. 1351 [BGLS03] prove the security of aggregate signatures over distinct 1352 messages, as in the basic scheme of Section 3.1. 1354 [BNN07] prove security of the message augmentation scheme of 1355 Section 3.2. 1357 [Bol03][LOSSW06][RY07] prove security of constructions related to the 1358 proof of possession scheme of Section 3.3. 1360 [BDN18] prove the security of another rogue key defense; this defense 1361 is not standardized in this document. 1363 Authors' Addresses 1365 Dan Boneh 1366 Stanford University 1367 United States of America 1368 Email: dabo@cs.stanford.edu 1369 Sergey Gorbunov 1370 University of Waterloo 1371 Waterloo, ON 1372 Canada 1373 Email: sgorbunov@uwaterloo.ca 1375 Riad S. Wahby 1376 Carnegie Mellon University 1377 United States of America 1378 Email: rsw@cs.stanford.edu 1380 Hoeteck Wee 1381 NTT Research and ENS, Paris 1382 Boston, MA, 1383 United States of America 1384 Email: wee@di.ens.fr 1386 Christopher A. Wood 1387 Cloudflare, Inc. 1388 San Francisco, CA, 1389 United States of America 1390 Email: caw@heapingbits.net 1392 Zhenfei Zhang 1393 Algorand 1394 Boston, MA, 1395 United States of America 1396 Email: zhenfei@algorand.com