idnits 2.17.1 draft-irtf-cfrg-bls-signature-04.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 issues found here. 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 (10 September 2020) is 1324 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-09 == Outdated reference: A later version (-11) exists of draft-irtf-cfrg-pairing-friendly-curves-07 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: 14 March 2021 University of Waterloo 6 R. Wahby 7 Stanford University 8 H. Wee 9 NTT Research and ENS, Paris 10 Z. Zhang 11 Algorand 12 10 September 2020 14 BLS Signatures 15 draft-irtf-cfrg-bls-signature-04 17 Abstract 19 BLS is a digital signature scheme with aggregation properties. Given 20 set of signatures (signature_1, ..., signature_n) anyone can produce 21 an aggregated signature. Aggregation can also be done on secret keys 22 and public keys. Furthermore, the BLS signature scheme is 23 deterministic, non-malleable, and efficient. Its simplicity and 24 cryptographic properties allows it to be useful in a variety of use- 25 cases, specifically when minimal storage space or bandwidth are 26 required. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at https://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on 14 March 2021. 45 Copyright Notice 47 Copyright (c) 2020 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 52 license-info) in effect on the date of publication of this document. 53 Please review these documents carefully, as they describe your rights 54 and restrictions with respect to this document. Code Components 55 extracted from this document must include Simplified BSD License text 56 as described in Section 4.e of the Trust Legal Provisions and are 57 provided without warranty as described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 62 1.1. Comparison with ECDSA . . . . . . . . . . . . . . . . . . 4 63 1.2. Organization of this document . . . . . . . . . . . . . . 4 64 1.3. Terminology and definitions . . . . . . . . . . . . . . . 5 65 1.4. API . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 66 1.5. Requirements . . . . . . . . . . . . . . . . . . . . . . 7 67 2. Core operations . . . . . . . . . . . . . . . . . . . . . . . 7 68 2.1. Variants . . . . . . . . . . . . . . . . . . . . . . . . 7 69 2.2. Parameters . . . . . . . . . . . . . . . . . . . . . . . 7 70 2.3. KeyGen . . . . . . . . . . . . . . . . . . . . . . . . . 9 71 2.4. SkToPk . . . . . . . . . . . . . . . . . . . . . . . . . 10 72 2.5. KeyValidate . . . . . . . . . . . . . . . . . . . . . . . 11 73 2.6. CoreSign . . . . . . . . . . . . . . . . . . . . . . . . 11 74 2.7. CoreVerify . . . . . . . . . . . . . . . . . . . . . . . 12 75 2.8. Aggregate . . . . . . . . . . . . . . . . . . . . . . . . 12 76 2.9. CoreAggregateVerify . . . . . . . . . . . . . . . . . . . 13 77 3. BLS Signatures . . . . . . . . . . . . . . . . . . . . . . . 14 78 3.1. Basic scheme . . . . . . . . . . . . . . . . . . . . . . 14 79 3.1.1. AggregateVerify . . . . . . . . . . . . . . . . . . . 15 80 3.2. Message augmentation . . . . . . . . . . . . . . . . . . 15 81 3.2.1. Sign . . . . . . . . . . . . . . . . . . . . . . . . 15 82 3.2.2. Verify . . . . . . . . . . . . . . . . . . . . . . . 16 83 3.2.3. AggregateVerify . . . . . . . . . . . . . . . . . . . 16 84 3.3. Proof of possession . . . . . . . . . . . . . . . . . . . 17 85 3.3.1. Parameters . . . . . . . . . . . . . . . . . . . . . 18 86 3.3.2. PopProve . . . . . . . . . . . . . . . . . . . . . . 18 87 3.3.3. PopVerify . . . . . . . . . . . . . . . . . . . . . . 19 88 3.3.4. FastAggregateVerify . . . . . . . . . . . . . . . . . 19 89 4. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 20 90 4.1. Ciphersuite format . . . . . . . . . . . . . . . . . . . 20 91 4.2. Ciphersuites for BLS12-381 . . . . . . . . . . . . . . . 22 92 4.2.1. Basic . . . . . . . . . . . . . . . . . . . . . . . . 22 93 4.2.2. Message augmentation . . . . . . . . . . . . . . . . 22 94 4.2.3. Proof of possession . . . . . . . . . . . . . . . . . 23 95 5. Security Considerations . . . . . . . . . . . . . . . . . . . 24 96 5.1. Validating public keys . . . . . . . . . . . . . . . . . 24 97 5.2. Skipping membership check . . . . . . . . . . . . . . . . 24 98 5.3. Side channel attacks . . . . . . . . . . . . . . . . . . 25 99 5.4. Randomness considerations . . . . . . . . . . . . . . . . 25 100 5.5. Implementing hash_to_point and hash_pubkey_to_point . . . 25 101 6. Implementation Status . . . . . . . . . . . . . . . . . . . . 25 102 7. Related Standards . . . . . . . . . . . . . . . . . . . . . . 26 103 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 104 9. Normative References . . . . . . . . . . . . . . . . . . . . 26 105 10. Informative References . . . . . . . . . . . . . . . . . . . 27 106 Appendix A. BLS12-381 . . . . . . . . . . . . . . . . . . . . . 28 107 Appendix B. Test Vectors . . . . . . . . . . . . . . . . . . . . 29 108 Appendix C. Security analyses . . . . . . . . . . . . . . . . . 29 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 29 111 1. Introduction 113 A signature scheme is a fundamental cryptographic primitive that is 114 used to protect authenticity and integrity of communication. Only 115 the holder of a secret key can sign messages, but anyone can verify 116 the signature using the associated public key. 118 Signature schemes are used in point-to-point secure communication 119 protocols, PKI, remote connections, etc. Designing efficient and 120 secure digital signature is very important for these applications. 122 This document describes the BLS signature scheme. The scheme enjoys 123 a variety of important efficiency properties: 125 1. The public key and the signatures are encoded as single group 126 elements. 128 2. Verification requires 2 pairing operations. 130 3. A collection of signatures (signature_1, ..., signature_n) can be 131 aggregated into a single signature. Moreover, the aggregate 132 signature can be verified using only n+1 pairings (as opposed to 133 2n pairings, when verifying n signatures separately). 135 Given the above properties, the scheme enables many interesting 136 applications. The immediate applications include 138 * Authentication and integrity for Public Key Infrastructure (PKI) 139 and blockchains. 141 - The usage is similar to classical digital signatures, such as 142 ECDSA. 144 * Aggregating signature chains for PKI and Secure Border Gateway 145 Protocol (SBGP). 147 - Concretely, in a PKI signature chain of depth n, we have n 148 signatures by n certificate authorities on n distinct 149 certificates. Similarly, in SBGP, each router receives a list 150 of n signatures attesting to a path of length n in the network. 151 In both settings, using the BLS signature scheme would allow us 152 to aggregate the n signatures into a single signature. 154 * consensus protocols for blockchains. 156 - There, BLS signatures are used for authenticating transactions 157 as well as votes during the consensus protocol, and the use of 158 aggregation significantly reduces the bandwidth and storage 159 requirements. 161 1.1. Comparison with ECDSA 163 The following comparison assumes BLS signatures with curve BLS12-381, 164 targeting 128 bits security. 166 For 128 bits security, ECDSA takes 37 and 79 micro-seconds to sign 167 and verify a signature on a typical laptop. In comparison, for the 168 same level of security, BLS takes 370 and 2700 micro-seconds to sign 169 and verify a signature. 171 In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes 172 for signatures; while BLS uses 96 bytes for public keys, and 48 bytes 173 for signatures. Alternatively, BLS can also be instantiated with 48 174 bytes of public keys and 96 bytes of signatures. BLS also allows for 175 signature aggregation. In other words, a single signature is 176 sufficient to authenticate multiple messages and public keys. 178 1.2. Organization of this document 180 This document is organized as follows: 182 * The remainder of this section defines terminology and the high- 183 level API. 185 * Section 2 defines primitive operations used in the BLS signature 186 scheme. These operations MUST NOT be used alone. 188 * Section 3 defines three BLS Signature schemes giving slightly 189 different security and performance properties. 191 * Section 4 defines the format for a ciphersuites and gives 192 recommended ciphersuites. 194 * The appendices give test vectors, etc. 196 1.3. Terminology and definitions 198 The following terminology is used through this document: 200 * SK: The secret key for the signature scheme. 202 * PK: The public key for the signature scheme. 204 * message: The input to be signed by the signature scheme. 206 * signature: The digital signature output. 208 * aggregation: Given a list of signatures for a list of messages and 209 public keys, an aggregation algorithm generates one signature that 210 authenticates the same list of messages and public keys. 212 * rogue key attack: An attack in which a specially crafted public 213 key (the "rogue" key) is used to forge an aggregated signature. 214 Section 3 specifies methods for securing against rogue key 215 attacks. 217 The following notation and primitives are used: 219 * a || b denotes the concatenation of octet strings a and b. 221 * A pairing-friendly elliptic curve defines the following primitives 222 (see [I-D.irtf-cfrg-pairing-friendly-curves] for detailed 223 discussion): 225 - E1, E2: elliptic curve groups defined over finite fields. This 226 document assumes that E1 has a more compact representation than 227 E2, i.e., because E1 is defined over a smaller field than E2. 229 - G1, G2: subgroups of E1 and E2 (respectively) having prime 230 order r. 232 - P1, P2: distinguished points that generate G1 and G2, 233 respectively. 235 - GT: a subgroup, of prime order r, of the multiplicative group 236 of a field extension. 238 - e : G1 x G2 -> GT: a non-degenerate bilinear map. 240 * For the above pairing-friendly curve, this document writes 241 operations in E1 and E2 in additive notation, i.e., P + Q denotes 242 point addition and x * P denotes scalar multiplication. 244 Operations in GT are written in multiplicative notation, i.e., a * 245 b is field multiplication. 247 * For each of E1 and E2 defined by the above pairing-friendly curve, 248 we assume that the pairing-friendly elliptic curve definition 249 provides several primitives, described below. 251 Note that these primitives are named generically. When referring 252 to one of these primitives for a specific group, this document 253 appends the name of the group, e.g., point_to_octets_E1, 254 subgroup_check_E2, etc. 256 - point_to_octets(P) -> ostr: returns the canonical 257 representation of the point P as an octet string. This 258 operation is also known as serialization. 260 - octets_to_point(ostr) -> P: returns the point P corresponding 261 to the canonical representation ostr, or INVALID if ostr is not 262 a valid output of point_to_octets. This operation is also 263 known as deserialization. 265 - subgroup_check(P) -> VALID or INVALID: returns VALID when the 266 point P is an element of the subgroup of order r, and INVALID 267 otherwise. This function can always be implemented by checking 268 that r * P is equal to the identity element. In some cases, 269 faster checks may also exist, e.g., [Bowe19]. 271 * I2OSP and OS2IP are the functions defined in [RFC8017], Section 4. 273 * hash_to_point(ostr) -> P: a cryptographic hash function that takes 274 as input an arbitrary octet string and returns a point on an 275 elliptic curve. Functions of this kind are defined in 276 [I-D.irtf-cfrg-hash-to-curve]. Each of the ciphersuites in 277 Section 4 specifies the hash_to_point algorithm to be used. 279 1.4. API 281 The BLS signature scheme defines the following API: 283 * KeyGen(IKM) -> SK: a key generation algorithm that takes as input 284 an octet string comprising secret keying material, and outputs a 285 secret key SK. 287 * SkToPk(SK) -> PK: an algorithm that takes as input a secret key 288 and outputs the corresponding public key. 290 * Sign(SK, message) -> signature: a signing algorithm that generates 291 a deterministic signature given a secret key SK and a message. 293 * Verify(PK, message, signature) -> VALID or INVALID: a verification 294 algorithm that outputs VALID if signature is a valid signature of 295 message under public key PK, and INVALID otherwise. 297 * Aggregate((signature_1, ..., signature_n)) -> signature: an 298 aggregation algorithm that aggregates a collection of signatures 299 into a single signature. 301 * AggregateVerify((PK_1, ..., PK_n), (message_1, ..., message_n), 302 signature) -> VALID or INVALID: an aggregate verification 303 algorithm that outputs VALID if signature is a valid aggregated 304 signature for a collection of public keys and messages, and 305 outputs INVALID otherwise. 307 1.5. Requirements 309 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 310 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 311 document are to be interpreted as described in [RFC2119]. 313 2. Core operations 315 This section defines core operations used by the schemes defined in 316 Section 3. These operations MUST NOT be used except as described in 317 that section. 319 2.1. Variants 321 Each core operation has two variants that trade off signature and 322 public key size: 324 1. Minimal-signature-size: signatures are points in G1, public keys 325 are points in G2. (Recall from Section 1.3 that E1 has a more 326 compact representation than E2.) 328 2. Minimal-pubkey-size: public keys are points in G1, signatures are 329 points in G2. 331 Implementations using signature aggregation SHOULD use this 332 approach, since the size of (PK_1, ..., PK_n, signature) is 333 dominated by the public keys even for small n. 335 2.2. Parameters 337 The core operations in this section depend on several parameters: 339 * A signature variant, either minimal-signature-size or minimal- 340 pubkey-size. These are defined in Section 2.1. 342 * A pairing-friendly elliptic curve, plus associated functionality 343 given in Section 1.3. 345 * H, a hash function that MUST be a secure cryptographic hash 346 function, e.g., SHA-256 [FIPS180-4]. For security, H MUST output 347 at least ceil(log2(r)) bits, where r is the order of the subgroups 348 G1 and G2 defined by the pairing-friendly elliptic curve. 350 * hash_to_point, a function whose interface is described in 351 Section 1.3. When the signature variant is minimal-signature- 352 size, this function MUST output a point in G1. When the signature 353 variant is minimal-pubkey size, this function MUST output a point 354 in G2. For security, this function MUST be either a random oracle 355 encoding or a nonuniform encoding, as defined in 356 [I-D.irtf-cfrg-hash-to-curve]. 358 In addition, the following primitives are determined by the above 359 parameters: 361 * P, an elliptic curve point. When the signature variant is 362 minimal-signature-size, P is the distinguished point P2 that 363 generates the group G2 (see Section 1.3). When the signature 364 variant is minimal-pubkey-size, P is the distinguished point P1 365 that generates the group G1. 367 * r, the order of the subgroups G1 and G2 defined by the pairing- 368 friendly curve. 370 * pairing, a function that invokes the function e of Section 1.3, 371 with argument order depending on signature variant: 373 - For minimal-signature-size: 375 pairing(U, V) := e(U, V) 377 - For minimal-pubkey-size: 379 pairing(U, V) := e(V, U) 381 * point_to_pubkey and point_to_signature, functions that invoke the 382 appropriate serialization routine (Section 1.3) depending on 383 signature variant: 385 - For minimal-signature-size: 387 point_to_pubkey(P) := point_to_octets_E2(P) 389 point_to_signature(P) := point_to_octets_E1(P) 391 - For minimal-pubkey-size: 393 point_to_pubkey(P) := point_to_octets_E1(P) 395 point_to_signature(P) := point_to_octets_E2(P) 397 * pubkey_to_point and signature_to_point, functions that invoke the 398 appropriate deserialization routine (Section 1.3) depending on 399 signature variant: 401 - For minimal-signature-size: 403 pubkey_to_point(ostr) := octets_to_point_E2(ostr) 405 signature_to_point(ostr) := octets_to_point_E1(ostr) 407 - For minimal-pubkey-size: 409 pubkey_to_point(ostr) := octets_to_point_E1(ostr) 411 signature_to_point(ostr) := octets_to_point_E2(ostr) 413 * pubkey_subgroup_check and signature_subgroup_check, functions that 414 invoke the appropriate subgroup check routine (Section 1.3) 415 depending on signature variant: 417 - For minimal-signature-size: 419 pubkey_subgroup_check(P) := subgroup_check_E2(P) 421 signature_subgroup_check(P) := subgroup_check_E1(P) 423 - For minimal-pubkey-size: 425 pubkey_subgroup_check(P) := subgroup_check_E1(P) 427 signature_subgroup_check(P) := subgroup_check_E2(P) 429 2.3. KeyGen 431 The KeyGen procedure described in this section generates a secret key 432 SK deterministically from a secret octet string IKM. SK is 433 guaranteed to be nonzero, as required by KeyValidate (Section 2.5). 435 KeyGen uses HKDF [RFC5869] instantiated with the hash function H. 437 For security, IKM MUST be infeasible to guess, e.g., generated by a 438 trusted source of randomness. IKM MUST be at least 32 bytes long, 439 but it MAY be longer. 441 KeyGen takes an optional parameter, key_info. This parameter MAY be 442 used to derive multiple independent keys from the same IKM. By 443 default, key_info is the empty string. 445 SK = KeyGen(IKM) 447 Inputs: 448 - IKM, a secret octet string. See requirements above. 450 Outputs: 451 - SK, a uniformly random integer such that 1 <= SK < r. 453 Parameters: 454 - key_info, an optional octet string. 455 If key_info is not supplied, it defaults to the empty string. 457 Definitions: 458 - HKDF-Extract is as defined in RFC5869, instantiated with hash H. 459 - HKDF-Expand is as defined in RFC5869, instantiated with hash H. 460 - I2OSP and OS2IP are as defined in RFC8017, Section 4. 461 - L is the integer given by ceil((3 * ceil(log2(r))) / 16). 462 - "BLS-SIG-KEYGEN-SALT-" is an ASCII string comprising 20 octets. 464 Procedure: 465 1. salt = "BLS-SIG-KEYGEN-SALT-" 466 2. SK = 0 467 3. while SK == 0: 468 4. salt = H(salt) 469 5. PRK = HKDF-Extract(salt, IKM || I2OSP(0, 1)) 470 6. OKM = HKDF-Expand(PRK, key_info || I2OSP(L, 2), L) 471 7. SK = OS2IP(OKM) mod r 472 8. return SK 474 KeyGen is the RECOMMENDED way of generating secret keys, but its use 475 is not required for compatibility, and implementations MAY use a 476 different KeyGen procedure. For security, such an alternative KeyGen 477 procedure MUST output SK that is statistically close to uniformly 478 random in the range 1 <= SK < r. 480 2.4. SkToPk 482 The SkToPk algorithm takes a secret key SK and outputs the 483 corresponding public key PK. Section 2.3 discusses requirements for 484 SK. 486 PK = SkToPk(SK) 488 Inputs: 489 - SK, a secret integer such that 1 <= SK < r. 491 Outputs: 492 - PK, a public key encoded as an octet string. 494 Procedure: 495 1. xP = SK * P 496 2. PK = point_to_pubkey(xP) 497 3. return PK 499 2.5. KeyValidate 501 The KeyValidate algorithm ensures that a public key is valid. In 502 particular, it ensures that a public key represents a valid, non- 503 identity point that is in the correct subgroup. See Section 5.1 for 504 further discussion. 506 As an optimization, implementations MAY cache the result of 507 KeyValidate in order to avoid unnecessarily repeating validation for 508 known keys. 510 result = KeyValidate(PK) 512 Inputs: 513 - PK, a public key in the format output by SkToPk. 515 Outputs: 516 - result, either VALID or INVALID 518 Procedure: 519 1. xP = pubkey_to_point(PK) 520 2. If xP is INVALID, return INVALID 521 3. If xP is the identity element, return INVALID 522 4. If pubkey_subgroup_check(xP) is INVALID, return INVALID 523 5. return VALID 525 2.6. CoreSign 527 The CoreSign algorithm computes a signature from SK, a secret key, 528 and message, an octet string. 530 signature = CoreSign(SK, message) 532 Inputs: 533 - SK, a secret key in the format output by KeyGen. 534 - message, an octet string. 536 Outputs: 537 - signature, an octet string. 539 Procedure: 540 1. Q = hash_to_point(message) 541 2. R = SK * Q 542 3. signature = point_to_signature(R) 543 4. return signature 545 2.7. CoreVerify 547 The CoreVerify algorithm checks that a signature is valid for the 548 octet string message under the public key PK. 550 result = CoreVerify(PK, message, signature) 552 Inputs: 553 - PK, a public key in the format output by SkToPk. 554 - message, an octet string. 555 - signature, an octet string in the format output by CoreSign. 557 Outputs: 558 - result, either VALID or INVALID. 560 Procedure: 561 1. R = signature_to_point(signature) 562 2. If R is INVALID, return INVALID 563 3. If signature_subgroup_check(R) is INVALID, return INVALID 564 4. If KeyValidate(PK) is INVALID, return INVALID 565 5. xP = pubkey_to_point(PK) 566 6. Q = hash_to_point(message) 567 7. C1 = pairing(Q, xP) 568 8. C2 = pairing(R, P) 569 9. If C1 == C2, return VALID, else return INVALID 571 2.8. Aggregate 573 The Aggregate algorithm aggregates multiple signatures into one. 575 signature = Aggregate((signature_1, ..., signature_n)) 577 Inputs: 578 - signature_1, ..., signature_n, octet strings output by 579 either CoreSign or Aggregate. 581 Outputs: 582 - signature, an octet string encoding a aggregated signature 583 that combines all inputs; or INVALID. 585 Precondition: n >= 1, otherwise return INVALID. 587 Procedure: 588 1. aggregate = signature_to_point(signature_1) 589 2. If aggregate is INVALID, return INVALID 590 3. for i in 2, ..., n: 591 4. next = signature_to_point(signature_i) 592 5. If next is INVALID, return INVALID 593 6. aggregate = aggregate + next 594 7. signature = point_to_signature(aggregate) 595 8. return signature 597 2.9. CoreAggregateVerify 599 The CoreAggregateVerify algorithm checks an aggregated signature over 600 several (PK, message) pairs. 602 result = CoreAggregateVerify((PK_1, ..., PK_n), 603 (message_1, ... message_n), 604 signature) 606 Inputs: 607 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 608 - message_1, ..., message_n, octet strings. 609 - signature, an octet string output by Aggregate. 611 Outputs: 612 - result, either VALID or INVALID. 614 Precondition: n >= 1, otherwise return INVALID. 616 Procedure: 617 1. R = signature_to_point(signature) 618 2. If R is INVALID, return INVALID 619 3. If signature_subgroup_check(R) is INVALID, return INVALID 620 4. C1 = 1 (the identity element in GT) 621 5. for i in 1, ..., n: 622 6. If KeyValidate(PK_i) is INVALID, return INVALID 623 7. xP = pubkey_to_point(PK_i) 624 8. Q = hash_to_point(message_i) 625 9. C1 = C1 * pairing(Q, xP) 626 10. C2 = pairing(R, P) 627 11. If C1 == C2, return VALID, else return INVALID 629 3. BLS Signatures 631 This section defines three signature schemes: basic, message 632 augmentation, and proof of possession. These schemes differ in the 633 ways that they defend against rogue key attacks (Section 1.3). 635 All of the schemes in this section are built on a set of core 636 operations defined in Section 2. Thus, defining a scheme requires 637 fixing a set of parameters as defined in Section 2.2. 639 All three schemes expose the KeyGen, SkToPk, and Aggregate operations 640 that are defined in Section 2. The sections below define the other 641 API functions (Section 1.4) for each scheme. 643 3.1. Basic scheme 645 In a basic scheme, rogue key attacks are handled by requiring all 646 messages signed by an aggregate signature to be distinct. This 647 requirement is enforced in the definition of AggregateVerify. 649 The Sign and Verify functions are identical to CoreSign and 650 CoreVerify (Section 2), respectively. AggregateVerify is defined 651 below. 653 3.1.1. AggregateVerify 655 This function first ensures that all messages are distinct, and then 656 invokes CoreAggregateVerify. 658 result = AggregateVerify((PK_1, ..., PK_n), 659 (message_1, ..., message_n), 660 signature) 662 Inputs: 663 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 664 - message_1, ..., message_n, octet strings. 665 - signature, an octet string output by Aggregate. 667 Outputs: 668 - result, either VALID or INVALID. 670 Precondition: n >= 1, otherwise return INVALID. 672 Procedure: 673 1. If any two input messages are equal, return INVALID. 674 2. return CoreAggregateVerify((PK_1, ..., PK_n), 675 (message_1, ..., message_n), 676 signature) 678 3.2. Message augmentation 680 In a message augmentation scheme, signatures are generated over the 681 concatenation of the public key and the message, ensuring that 682 messages signed by different public keys are distinct. 684 3.2.1. Sign 686 To match the API for Sign defined in Section 1.4, this function 687 recomputes the public key corresponding to the input SK. 688 Implementations MAY instead implement an interface that takes the 689 public key as an input. 691 Note that the point P and the point_to_pubkey function are defined in 692 Section 2.2. 694 signature = Sign(SK, message) 696 Inputs: 697 - SK, a secret key in the format output by KeyGen. 698 - message, an octet string. 700 Outputs: 701 - signature, an octet string. 703 Procedure: 704 1. PK = SkToPk(SK) 705 2. return CoreSign(SK, PK || message) 707 3.2.2. Verify 709 result = Verify(PK, message, signature) 711 Inputs: 712 - PK, a public key in the format output by SkToPk. 713 - message, an octet string. 714 - signature, an octet string in the format output by CoreSign. 716 Outputs: 717 - result, either VALID or INVALID. 719 Procedure: 720 1. return CoreVerify(PK, PK || message, signature) 722 3.2.3. AggregateVerify 723 result = AggregateVerify((PK_1, ..., PK_n), 724 (message_1, ..., message_n), 725 signature) 727 Inputs: 728 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 729 - message_1, ..., message_n, octet strings. 730 - signature, an octet string output by Aggregate. 732 Outputs: 733 - result, either VALID or INVALID. 735 Precondition: n >= 1, otherwise return INVALID. 737 Procedure: 738 1. for i in 1, ..., n: 739 2. mprime_i = PK_i || message_i 740 3. return CoreAggregateVerify((PK_1, ..., PK_n), 741 (mprime_1, ..., mprime_n), 742 signature) 744 3.3. Proof of possession 746 A proof of possession scheme uses a separate public key validation 747 step, called a proof of possession, to defend against rogue key 748 attacks. This enables an optimization to aggregate signature 749 verification for the case that all signatures are on the same 750 message. 752 The Sign, Verify, and AggregateVerify functions are identical to 753 CoreSign, CoreVerify, and CoreAggregateVerify (Section 2), 754 respectively. In addition, a proof of possession scheme defines 755 three functions beyond the standard API (Section 1.4): 757 * PopProve(SK) -> proof: an algorithm that generates a proof of 758 possession for the public key corresponding to secret key SK. 760 * PopVerify(PK, proof) -> VALID or INVALID: an algorithm that 761 outputs VALID if proof is valid for PK, and INVALID otherwise. 763 * FastAggregateVerify((PK_1, ..., PK_n), message, signature) -> 764 VALID or INVALID: a verification algorithm for the aggregate of 765 multiple signatures on the same message. This function is faster 766 than AggregateVerify. 768 All public keys used by Verify, AggregateVerify, and 769 FastAggregateVerify MUST be accompanied by a proof of possession, and 770 the result of evaluating PopVerify on the public key and proof MUST 771 be VALID. 773 3.3.1. Parameters 775 In addition to the parameters required to instantiate the core 776 operations (Section 2.2), a proof of possession scheme requires one 777 further parameter: 779 * hash_pubkey_to_point(PK) -> P: a cryptographic hash function that 780 takes as input a public key and outputs a point in the same 781 subgroup as the hash_to_point algorithm used to instantiate the 782 core operations. 784 For security, this function MUST be domain separated from the 785 hash_to_point function. In addition, this function MUST be either 786 a random oracle encoding or a nonuniform encoding, as defined in 787 [I-D.irtf-cfrg-hash-to-curve]. 789 The RECOMMENDED way of instantiating hash_pubkey_to_point is to 790 use the same hash-to-curve function as hash_to_point, with a 791 different domain separation tag (see 792 [I-D.irtf-cfrg-hash-to-curve], Section 3.1). Section 4.1 793 discusses the RECOMMENDED way to construct the domain separation 794 tag. 796 3.3.2. PopProve 798 This function recomputes the public key coresponding to the input SK. 799 Implementations MAY instead implement an interface that takes the 800 public key as input. 802 Note that the point P and the point_to_pubkey and point_to_signature 803 functions are defined in Section 2.2. The hash_pubkey_to_point 804 function is defined in Section 3.3.1. 806 proof = PopProve(SK) 808 Inputs: 809 - SK, a secret key in the format output by KeyGen. 811 Outputs: 812 - proof, an octet string. 814 Procedure: 815 1. PK = SkToPk(SK) 816 2. Q = hash_pubkey_to_point(PK) 817 3. R = SK * Q 818 4. proof = point_to_signature(R) 819 5. return proof 821 3.3.3. PopVerify 823 PopVerify uses several functions defined in Section 2. The 824 hash_pubkey_to_point function is defined in Section 3.3.1. 826 As an optimization, implementations MAY cache the result of PopVerify 827 in order to avoid unnecessarily repeating validation for known keys. 829 result = PopVerify(PK, proof) 831 Inputs: 832 - PK, a public key in the format output by SkToPk. 833 - proof, an octet string in the format output by PopProve. 835 Outputs: 836 - result, either VALID or INVALID 838 Procedure: 839 1. R = signature_to_point(proof) 840 2. If R is INVALID, return INVALID 841 3. If signature_subgroup_check(R) is INVALID, return INVALID 842 4. If KeyValidate(PK) is INVALID, return INVALID 843 5. xP = pubkey_to_point(PK) 844 6. Q = hash_pubkey_to_point(PK) 845 7. C1 = pairing(Q, xP) 846 8. C2 = pairing(R, P) 847 9. If C1 == C2, return VALID, else return INVALID 849 3.3.4. FastAggregateVerify 851 FastAggregateVerify uses several functions defined in Section 2. 853 result = FastAggregateVerify((PK_1, ..., PK_n), message, signature) 855 Inputs: 856 - PK_1, ..., PK_n, public keys in the format output by SkToPk. 857 - message, an octet string. 858 - signature, an octet string output by Aggregate. 860 Outputs: 861 - result, either VALID or INVALID. 863 Precondition: n >= 1, otherwise return INVALID. 865 Procedure: 866 1. aggregate = pubkey_to_point(PK_1) 867 2. for i in 2, ..., n: 868 3. next = pubkey_to_point(PK_i) 869 4. aggregate = aggregate + next 870 5. PK = point_to_pubkey(aggregate) 871 6. return CoreVerify(PK, message, signature) 873 4. Ciphersuites 875 This section defines the format for a BLS ciphersuite. It also gives 876 concrete ciphersuites based on the BLS12-381 pairing-friendly 877 elliptic curve [I-D.irtf-cfrg-pairing-friendly-curves]. 879 4.1. Ciphersuite format 881 A ciphersuite specifies all parameters from Section 2.2, a scheme 882 from Section 3, and any parameters the scheme requires. In 883 particular, a ciphersuite comprises: 885 * ID: the ciphersuite ID, an ASCII string. The REQUIRED format for 886 this string is 888 "BLS_SIG_" || H2C_SUITE_ID || SC_TAG || "_" 890 - Strings in double quotes are ASCII-encoded literals. 892 - H2C_SUITE_ID is the suite ID of the hash-to-curve suite used to 893 define the hash_to_point and hash_pubkey_to_point functions. 895 - SC_TAG is a string indicating the scheme and, optionally, 896 additional information. The first three characters of this 897 string MUST chosen as follows: 899 o "NUL" if SC is basic, 900 o "AUG" if SC is message-augmentation, or 902 o "POP" if SC is proof-of-possession. 904 o Other values MUST NOT be used. 906 SC_TAG MAY be used to encode other information about the 907 ciphersuite, for example, a version number. When used in this 908 way, SC_TAG MUST contain only ASCII characters between 0x21 and 909 0x7e (inclusive), except that it MUST NOT contain underscore 910 (0x5f). 912 The RECOMMENDED way to add user-defined information to SC_TAG 913 is to append a colon (':', ASCII 0x3a) and then the 914 informational string. For example, "NUL:version=2" is an 915 appropriate SC_TAG value. 917 Note that hash-to-curve suite IDs always include a trailing 918 underscore, so no field separator is needed between H2C_SUITE_ID 919 and SC_TAG. 921 * SC: the scheme, one of basic, message-augmentation, or proof-of- 922 possession. 924 * SV: the signature variant, either minimal-signature-size or 925 minimal-pubkey-size. 927 * EC: a pairing-friendly elliptic curve, plus all associated 928 functionality (Section 1.3). 930 * H: a cryptographic hash function. 932 * hash_to_point: a hash from arbitrary strings to elliptic curve 933 points. hash_to_point MUST be defined in terms of a hash-to-curve 934 suite [I-D.irtf-cfrg-hash-to-curve]. 936 The RECOMMENDED hash-to-curve domain separation tag is the 937 ciphersuite ID string defined above. 939 * hash_pubkey_to_point (only specified when SC is proof-of- 940 possession): a hash from serialized public keys to elliptic curve 941 points. hash_pubkey_to_point MUST be defined in terms of a hash- 942 to-curve suite [I-D.irtf-cfrg-hash-to-curve]. 944 The hash-to-curve domain separation tag MUST be distinct from the 945 domain separation tag used for hash_to_point. It is RECOMMENDED 946 that the domain separation tag be constructed similarly to the 947 ciphersuite ID string, namely: 949 "BLS_POP_" || H2C_SUITE_ID || SC_TAG || "_" 951 4.2. Ciphersuites for BLS12-381 953 The following ciphersuites are all built on the BLS12-381 elliptic 954 curve. The required primitives for this curve are given in 955 Appendix A. 957 These ciphersuites use the hash-to-curve suites BLS12381G1_XMD:SHA- 958 256_SSWU_RO_ and BLS12381G2_XMD:SHA-256_SSWU_RO_ defined in 959 [I-D.irtf-cfrg-hash-to-curve], Section 8.7. Each ciphersuite defines 960 a unique hash_to_point function by specifying a domain separation tag 961 (see [@I-D.irtf-cfrg-hash-to-curve, Section 3.1). 963 4.2.1. Basic 965 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_NUL_ is defined as follows: 967 * SC: basic 969 * SV: minimal-signature-size 971 * EC: BLS12-381, as defined in Appendix A. 973 * H: SHA-256 975 * hash_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the ASCII- 976 encoded domain separation tag 978 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_NUL_ 980 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_NUL_ is identical to 981 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_NUL_, except for the following 982 parameters: 984 * SV: minimal-pubkey-size 986 * hash_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the ASCII- 987 encoded domain separation tag 989 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_NUL_ 991 4.2.2. Message augmentation 993 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_AUG_ is defined as follows: 995 * SC: message-augmentation 996 * SV: minimal-signature-size 998 * EC: BLS12-381, as defined in Appendix A. 1000 * H: SHA-256 1002 * hash_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the ASCII- 1003 encoded domain separation tag 1005 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_AUG_ 1007 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_AUG_ is identical to 1008 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_AUG_, except for the following 1009 parameters: 1011 * SV: minimal-pubkey-size 1013 * hash_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the ASCII- 1014 encoded domain separation tag 1016 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_AUG_ 1018 4.2.3. Proof of possession 1020 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_ is defined as follows: 1022 * SC: proof-of-possession 1024 * SV: minimal-signature-size 1026 * EC: BLS12-381, as defined in Appendix A. 1028 * H: SHA-256 1030 * hash_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the ASCII- 1031 encoded domain separation tag 1033 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_ 1035 * hash_pubkey_to_point: BLS12381G1_XMD:SHA-256_SSWU_RO_ with the 1036 ASCII-encoded domain separation tag 1038 BLS_POP_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_ 1040 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_ is identical to 1041 BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_POP_, except for the following 1042 parameters: 1044 * SV: minimal-pubkey-size 1046 * hash_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the ASCII- 1047 encoded domain separation tag 1049 BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_ 1051 * hash_pubkey_to_point: BLS12381G2_XMD:SHA-256_SSWU_RO_ with the 1052 ASCII-encoded domain separation tag 1054 BLS_POP_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_ 1056 5. Security Considerations 1058 5.1. Validating public keys 1060 All algorithms in Section 2 and Section 3 that operate on public keys 1061 require first validating those keys. For the basic and message 1062 augmentation schemes, the use of KeyValidate is REQUIRED. For the 1063 proof of possession scheme, each public key MUST be accompanied by a 1064 proof of possession, and use of PopVerify is REQUIRED. 1066 KeyValidate requires all public keys to represent valid, non-identity 1067 points in the correct subgroup. A valid point and subgroup 1068 membership are required to ensure that the pairing operation is 1069 defined (Section 5.2). 1071 A non-identity point is required because the identity public key has 1072 the property that the corresponding secret key is equal to zero, 1073 which means that the identity point is the unique valid signature for 1074 every message under this key. A malicious signer could take 1075 advantage of this fact to equivocate about which message he signed. 1076 While non-equivocation is not a required property for a signature 1077 scheme, equivocation is infeasible for BLS signatures under any 1078 nonzero secret key because it would require finding colliding inputs 1079 to the hash_to_point function, which is assumed to be collision 1080 resistant. Prohibiting SK == 0 eliminates the exceptional case, 1081 which may help to prevent equivocation-related security issues in 1082 protocols that use BLS signatures. 1084 5.2. Skipping membership check 1086 Some existing implementations skip the signature_subgroup_check 1087 invocation in CoreVerify (Section 2.7), whose purpose is ensuring 1088 that the signature is an element of a prime-order subgroup. This 1089 check is REQUIRED of conforming implementations, for two reasons. 1091 1. For most pairing-friendly elliptic curves used in practice, the 1092 pairing operation e (Section 1.3) is undefined when its input 1093 points are not in the prime-order subgroups of E1 and E2. The 1094 resulting behavior is unpredictable, and may enable forgeries. 1096 2. Even if the pairing operation behaves properly on inputs that are 1097 outside the correct subgroups, skipping the subgroup check breaks 1098 the strong unforgeability property [ADR02]. 1100 5.3. Side channel attacks 1102 Implementations of the signing algorithm SHOULD protect the secret 1103 key from side-channel attacks. One method for protecting against 1104 certain side-channel attacks is ensuring that the implementation 1105 executes exactly the same sequence of instructions and performs 1106 exactly the same memory accesses, for any value of the secret key. 1107 In other words, implementations on the underlying pairing-friendly 1108 elliptic curve SHOULD run in constant time. 1110 5.4. Randomness considerations 1112 BLS signatures are deterministic. This protects against attacks 1113 arising from signing with bad randomness, for example, the nonce 1114 reuse attack on ECDSA [HDWH12]. 1116 As discussed in Section 2.3, the IKM input to KeyGen MUST be 1117 infeasible to guess and MUST be kept secret. One possibility is to 1118 generate IKM from a trusted source of randomness. Guidelines on 1119 constructing such a source are outside the scope of this document. 1121 5.5. Implementing hash_to_point and hash_pubkey_to_point 1123 The security analysis models hash_to_point and hash_pubkey_to_point 1124 as random oracles. It is crucial that these functions are 1125 implemented using a cryptographically secure hash function. For this 1126 purpose, implementations MUST meet the requirements of 1127 [I-D.irtf-cfrg-hash-to-curve]. 1129 In addition, ciphersuites MUST specify unique domain separation tags 1130 for hash_to_point and hash_pubkey_to_point. The domain separation 1131 tag format used in Section 4 is the RECOMMENDED one. 1133 6. Implementation Status 1135 This section will be removed in the final version of the draft. 1136 There are currently several implementations of BLS signatures using 1137 the BLS12-381 curve. 1139 * Algorand: bls_sigs_ref (https://github.com/kwantam/bls_sigs_ref). 1141 * Chia: spec (https://github.com/Chia-Network/bls- 1142 signatures/blob/master/SPEC.md) python/C++ (https://github.com/ 1143 Chia-Network/bls-signatures). Here, they are swapping G1 and G2 1144 so that the public keys are small, and the benefits of avoiding a 1145 membership check during signature verification would even be more 1146 substantial. The current implementation does not seem to 1147 implement the membership check. Chia uses the Fouque-Tibouchi 1148 hashing to the curve, which can be done in constant time. 1150 * Dfinity: go (https://github.com/dfinity/go-dfinity-crypto) BLS 1151 (https://github.com/dfinity/bls). The current implementations do 1152 not seem to implement the membership check. 1154 * Ethereum 2.0: spec (https://github.com/ethereum/eth2.0- 1155 specs/blob/master/specs/bls_signature.md). 1157 7. Related Standards 1159 * Pairing-friendly curves, [I-D.irtf-cfrg-pairing-friendly-curves] 1161 * Pairing-based Identity-Based Encryption IEEE 1363.3 1162 (https://ieeexplore.ieee.org/document/6662370). 1164 * Identity-Based Cryptography Standard rfc5901 1165 (https://tools.ietf.org/html/rfc5091). 1167 * Hashing to Elliptic Curves [I-D.irtf-cfrg-hash-to-curve], in order 1168 to implement the hash function hash_to_point. 1170 * EdDSA rfc8032 (https://tools.ietf.org/html/rfc8032). 1172 8. IANA Considerations 1174 TBD (consider to register ciphersuite identifiers for BLS signature 1175 and underlying pairing curves) 1177 9. Normative References 1179 [ZCash] Electric Coin Company, "BLS12-381", July 2017, 1180 . 1183 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1184 Requirement Levels", BCP 14, RFC 2119, 1185 DOI 10.17487/RFC2119, March 1997, 1186 . 1188 10. Informative References 1190 [BGLS03] Boneh, D., Gentry, C., Lynn, B., and H. Shacham, 1191 "Aggregate and verifiably encrypted signatures from 1192 bilinear maps", May 2003, . 1195 [BNN07] Bellare, M., Namprempre, C., and G. Neven, "Unrestricted 1196 aggregate signatures", July 2007, 1197 . 1200 [RY07] Ristenpart, T. and S. Yilek, "The Power of Proofs-of- 1201 Possession: Securing Multiparty Signatures against Rogue- 1202 Key Attacks", May 2007, . 1205 [HDWH12] Heninger, N., Durumeric, Z., Wustrow, E., and J.A. 1206 Halderman, "Mining your Ps and Qs: Detection of widespread 1207 weak keys in network devices", August 2012, 1208 . 1211 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1212 Key Derivation Function (HKDF)", RFC 5869, 1213 DOI 10.17487/RFC5869, May 2010, 1214 . 1216 [ADR02] An, J. H., Dodis, Y., and T. Rabin, "On the Security of 1217 Joint Signature and Encryption", April 2002, 1218 . 1220 [LOSSW06] Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., and B. 1221 Waters, "Sequential Aggregate Signatures and 1222 Multisignatures Without Random Oracles", May 2006, 1223 . 1225 [Bowe19] Bowe, S., "Faster subgroup checks for BLS12-381", July 1226 2019, . 1228 [I-D.irtf-cfrg-hash-to-curve] 1229 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1230 C. Wood, "Hashing to Elliptic Curves", Work in Progress, 1231 Internet-Draft, draft-irtf-cfrg-hash-to-curve-09, 29 June 1232 2020, . 1235 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1236 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1237 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1238 . 1240 [FIPS180-4] 1241 National Institute of Standards and Technology (NIST), 1242 "FIPS Publication 180-4: Secure Hash Standard", August 1243 2015, . 1246 [BLS01] Boneh, D., Lynn, B., and H. Shacham, "Short signatures 1247 from the Weil pairing", December 2001, 1248 . 1250 [Bol03] Boldyreva, A., "Threshold Signatures, Multisignatures and 1251 Blind Signatures Based on the Gap-Diffie-Hellman-Group 1252 Signature Scheme", January 2003, 1253 . 1256 [BDN18] Boneh, D., Drijvers, M., and G. Neven, "Compact multi- 1257 signatures for shorter blockchains", December 2018, 1258 . 1261 [I-D.irtf-cfrg-pairing-friendly-curves] 1262 Sakemi, Y., Kobayashi, T., Saito, T., and R. Wahby, 1263 "Pairing-Friendly Curves", Work in Progress, Internet- 1264 Draft, draft-irtf-cfrg-pairing-friendly-curves-07, 18 June 1265 2020, . 1268 Appendix A. BLS12-381 1270 The ciphersuites in Section 4 are based upon the BLS12-381 pairing- 1271 friendly elliptic curve. The following defines the correspondence 1272 between the primitives in Section 1.3 and the parameters given in 1273 Section 4.2.2 of [I-D.irtf-cfrg-pairing-friendly-curves]. 1275 * E1, G1: the curve E and its order-r subgroup. 1277 * E2, G2: the curve E' and its order-r subgroup. 1279 * GT: the subgroup G_T. 1281 * P1: the point BP. 1283 * P2: the point BP'. 1285 * e: the optimal Ate pairing defined in Appendix A of 1286 [I-D.irtf-cfrg-pairing-friendly-curves]. 1288 * point_to_octets and octets_to_point use the compressed 1289 serialization formats for E1 and E2 defined by [ZCash]. 1291 * subgroup_check MAY use either the naive check described in 1292 Section 1.3 or the optimized check given by [Bowe19]. 1294 Appendix B. Test Vectors 1296 TBA: (i) test vectors for both variants of the signature scheme 1297 (signatures in G2 instead of G1) , (ii) test vectors ensuring 1298 membership checks, (iii) intermediate computations ctr, hm. 1300 Appendix C. Security analyses 1302 The security properties of the BLS signature scheme are proved in 1303 [BLS01]. 1305 [BGLS03] prove the security of aggregate signatures over distinct 1306 messages, as in the basic scheme of Section 3.1. 1308 [BNN07] prove security of the message augmentation scheme of 1309 Section 3.2. 1311 [Bol03][LOSSW06][RY07] prove security of constructions related to the 1312 proof of possession scheme of Section 3.3. 1314 [BDN18] prove the security of another rogue key defense; this defense 1315 is not standardized in this document. 1317 Authors' Addresses 1319 Dan Boneh 1320 Stanford University 1321 United States of America 1323 Email: dabo@cs.stanford.edu 1325 Sergey Gorbunov 1326 University of Waterloo 1327 Waterloo, ON 1328 Canada 1329 Email: sgorbunov@uwaterloo.ca 1331 Riad S. Wahby 1332 Stanford University 1333 United States of America 1335 Email: rsw@cs.stanford.edu 1337 Hoeteck Wee 1338 NTT Research and ENS, Paris 1339 Boston, MA, 1340 United States of America 1342 Email: wee@di.ens.fr 1344 Zhenfei Zhang 1345 Algorand 1346 Boston, MA, 1347 United States of America 1349 Email: zhenfei@algorand.com