idnits 2.17.1 draft-irtf-cfrg-bls-signature-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard 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 (August 8, 2019) is 1724 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '1' on line 1148 -- Looks like a reference, but probably isn't: '2' on line 1150 -- Looks like a reference, but probably isn't: '3' on line 1153 -- Looks like a reference, but probably isn't: '4' on line 1155 -- Looks like a reference, but probably isn't: '5' on line 1157 -- Looks like a reference, but probably isn't: '6' on line 1159 -- Looks like a reference, but probably isn't: '7' on line 1162 -- Looks like a reference, but probably isn't: '8' on line 1165 -- Looks like a reference, but probably isn't: '9' on line 1167 -- Looks like a reference, but probably isn't: '10' on line 1169 -- Looks like a reference, but probably isn't: '11' on line 1171 -- Possible downref: Non-RFC (?) normative reference: ref. 'ZCash' == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-04 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG D. Boneh 3 Internet-Draft R. Wahby 4 Expires: February 9, 2020 Stanford University 5 S. Gorbunov 6 Algorand and University of Waterloo 7 H. Wee 8 Algorand and ENS, Paris 9 Z. Zhang 10 Algorand 11 August 8, 2019 13 draft-irtf-cfrg-bls-signature-00.txt 14 draft-irtf-cfrg-bls-signature-00 16 Abstract 18 BLS is a digital signature scheme with compression properties. With 19 a given set of signatures (signature_1, ..., signature_n) anyone can 20 produce a compressed signature signature_compressed. The same is 21 true for a set of secret keys or public keys, while keeping the 22 connection between sets (i.e., a compressed public key is associated 23 to its compressed secret key). Furthermore, the BLS signature scheme 24 is deterministic, non-malleable, and efficient. Its simplicity and 25 cryptographic properties allows it to be useful in a variety of use- 26 cases, specifically when minimal storage space or bandwidth are 27 required. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at https://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on February 9, 2020. 46 Copyright Notice 48 Copyright (c) 2019 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (https://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 68 1.5. Requirements . . . . . . . . . . . . . . . . . . . . . . 7 69 2. Core operations . . . . . . . . . . . . . . . . . . . . . . . 7 70 2.1. Variants . . . . . . . . . . . . . . . . . . . . . . . . 7 71 2.2. Parameters . . . . . . . . . . . . . . . . . . . . . . . 8 72 2.3. KeyGen . . . . . . . . . . . . . . . . . . . . . . . . . 9 73 2.4. KeyValidate . . . . . . . . . . . . . . . . . . . . . . . 10 74 2.5. CoreSign . . . . . . . . . . . . . . . . . . . . . . . . 11 75 2.6. CoreVerify . . . . . . . . . . . . . . . . . . . . . . . 11 76 2.7. Aggregate . . . . . . . . . . . . . . . . . . . . . . . . 12 77 2.8. CoreAggregateVerify . . . . . . . . . . . . . . . . . . . 12 78 3. BLS Signatures . . . . . . . . . . . . . . . . . . . . . . . 13 79 3.1. Basic scheme . . . . . . . . . . . . . . . . . . . . . . 13 80 3.1.1. AggregateVerify . . . . . . . . . . . . . . . . . . . 14 81 3.2. Message augmentation . . . . . . . . . . . . . . . . . . 14 82 3.2.1. Sign . . . . . . . . . . . . . . . . . . . . . . . . 14 83 3.2.2. Verify . . . . . . . . . . . . . . . . . . . . . . . 15 84 3.2.3. AggregateVerify . . . . . . . . . . . . . . . . . . . 15 85 3.3. Proof of possession . . . . . . . . . . . . . . . . . . . 16 86 3.3.1. Parameters . . . . . . . . . . . . . . . . . . . . . 16 87 3.3.2. PopProve . . . . . . . . . . . . . . . . . . . . . . 17 88 3.3.3. PopVerify . . . . . . . . . . . . . . . . . . . . . . 17 89 3.3.4. FastAggregateVerify . . . . . . . . . . . . . . . . . 18 90 4. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 18 91 4.1. Ciphersuite format . . . . . . . . . . . . . . . . . . . 19 92 4.2. Ciphersuites for BLS12-381 . . . . . . . . . . . . . . . 19 93 4.2.1. Basic . . . . . . . . . . . . . . . . . . . . . . . . 20 94 4.2.2. Message augmentation . . . . . . . . . . . . . . . . 20 95 4.2.3. Proof of possession . . . . . . . . . . . . . . . . . 21 96 5. Security Considerations . . . . . . . . . . . . . . . . . . . 22 97 5.1. Validating public keys . . . . . . . . . . . . . . . . . 22 98 5.2. Skipping membership check . . . . . . . . . . . . . . . . 22 99 5.3. Side channel attacks . . . . . . . . . . . . . . . . . . 22 100 5.4. Randomness considerations . . . . . . . . . . . . . . . . 22 101 5.5. Implementing hash_to_point and hash_pubkey_to_point . . . 23 102 6. Implementation Status . . . . . . . . . . . . . . . . . . . . 23 103 7. Related Standards . . . . . . . . . . . . . . . . . . . . . . 23 104 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 105 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 106 9.1. Normative References . . . . . . . . . . . . . . . . . . 24 107 9.2. Informative References . . . . . . . . . . . . . . . . . 24 108 9.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 26 109 Appendix A. BLS12-381 . . . . . . . . . . . . . . . . . . . . . 26 110 Appendix B. Test Vectors . . . . . . . . . . . . . . . . . . . . 27 111 Appendix C. Security analyses . . . . . . . . . . . . . . . . . 27 112 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27 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 compressed into a single signature (signature). Moreover, the 135 compressed signature can be verified using only n+1 pairings (as 136 opposed to 2n pairings, when verifying n signatures separately). 138 Given the above properties, the scheme enables many interesting 139 applications. The immediate applications include 140 o authentication and integrity for Public Key Infrastructure (PKI) 141 and blockchains. 143 * The usage is similar to classical digital signatures, such as 144 ECDSA. 146 o compressing signature chains for PKI and Secure Border Gateway 147 Protocol (SBGP). 149 * Concretely, in a PKI signature chain of depth n, we have n 150 signatures by n certificate authorities on n distinct 151 certificates. Similarly, in SBGP, each router receives a list 152 of n signatures attesting to a path of length n in the network. 153 In both settings, using the BLS signature scheme would allow us 154 to compress the n signatures into a single signature. 156 o consensus protocols for blockchains. 158 * There, BLS signatures are used for authenticating transactions 159 as well as votes during the consensus protocol, and the use of 160 aggregation significantly reduces the bandwidth and storage 161 requirements. 163 1.1. Comparison with ECDSA 165 The following comparison assumes BLS signatures with curve BLS12-381, 166 targeting 128 bits security. 168 For 128 bits security, ECDSA takes 37 and 79 micro-seconds to sign 169 and verify a signature on a typical laptop. In comparison, for the 170 same level of security, BLS takes 370 and 2700 micro-seconds to sign 171 and verify a signature. 173 In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes 174 for signatures; while BLS uses 96 bytes for public keys, and 48 bytes 175 for signatures. Alternatively, BLS can also be instantiated with 48 176 bytes of public keys and 96 bytes of signatures. BLS also allows for 177 signature compression. In other words, a single signature is 178 sufficient to anthenticate multiple messages and public keys. 180 1.2. Organization of this document 182 This document is organized as follows: 184 o The remainder of this section defines terminology and the high- 185 level API. 187 o Section 2 defines primitive operations used in the BLS signature 188 scheme. These operations MUST NOT be used alone. 190 o Section 3 defines three BLS Signature schemes giving slightly 191 different security and performance properties. 193 o Section 4 defines the format for a ciphersuites and gives 194 recommended ciphersuites. 196 o The appendices give test vectors, etc. 198 1.3. Terminology and definitions 200 The following terminology is used through this document: 202 o SK: The secret key for the signature scheme. 204 o PK: The public key for the signature scheme. 206 o message: The input to be signed by the signature scheme. 208 o signature: The digital signature output. 210 o aggregation: Given a list of signatures for a list of messages and 211 public keys, an aggregation algorithm generates one signature that 212 authenticates the same list of messages and public keys. 214 o rogue key attack: An attack in which a specially crafted public 215 key (the "rogue" key) is used to forge an aggregated signature. 216 Section 3 specifies methods for securing against rogue key 217 attacks. 219 The following notation and primitives are used: 221 o a || b denotes the concatenation of octet strings a and b. 223 o A pairing-friendly elliptic curve defines the following primitives 224 (see [I-D.yonezawa-pairing-friendly-curves] for detailed 225 discussion): 227 * E1, E2: elliptic curve groups defined over finite fields. This 228 document assumes that E1 has a more compact representation than 229 E2, i.e., because E1 is defined over a smaller field than E2. 231 * G1, G2: subgroups of E1 and E2 (respectively) having prime 232 order r. 234 * P1, P2: distinguished points that generate of G1 and G2, 235 respectively. 237 * GT: a subgroup, of prime order r, of the multiplicative group 238 of a field extension. 240 * e : G1 x G2 -> GT: a non-degenerate bilinear map. 242 o For the above pairing-friendly curve, this document writes 243 operations in E1 and E2 in additive notation, i.e., P + Q denotes 244 point addition and x * P denotes scalar multiplication. 245 Operations in GT are written in multiplicative notation, i.e., a * 246 b is field multiplication. 248 o For each of E1 and E2 defined by the above pairing-friendly curve, 249 we assume that the pairing-friendly elliptic curve definition 250 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 o I2OSP and OS2IP are the functions defined in [RFC8017], Section 4. 273 o 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 o KeyGen(IKM) -> PK, SK: a key generation algorithm that takes as 284 input an octet string comprising secret keying material, and 285 outputs a public key PK and corresponding secret key SK. 287 o Sign(SK, message) -> signature: a signing algorithm that generates 288 a deterministic signature given a secret key SK and a message. 290 o Verify(PK, message, signature) -> VALID or INVALID: a verification 291 algorithm that outputs VALID if signature is a valid signature of 292 message under public key PK, and INVALID otherwise. 294 o Aggregate(signature_1, ..., signature_n) -> signature: an 295 aggregation algorithm that compresses a collection of signatures 296 into a single signature. 298 o AggregateVerify((PK_1, message_1), ..., (PK_n, message_n), 299 signature) -> VALID or INVALID: an aggregate verification 300 algorithm that outputs VALID if signature is a valid aggregated 301 signature for a collection of public keys and messages, and 302 outputs INVALID otherwise. 304 1.5. Requirements 306 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 307 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 308 document are to be interpreted as described in [RFC2119]. 310 2. Core operations 312 This section defines core operations used by the schemes defined in 313 Section 3. These operations MUST NOT be used except as described in 314 that section. 316 2.1. Variants 318 Each core operation has two variants that trade off signature and 319 public key size: 321 1. Minimal-signature-size: signatures are points in G1, public keys 322 are points in G2. (Recall from Section 1.3 that E1 has a more 323 compact representation than E2.) 325 2. Minimal-pubkey-size: public keys are points in G1, signatures are 326 points in G2. 328 Implementations using signature aggregation SHOULD use this 329 approach, since the size of (PK_1, ..., PK_n, signature) is 330 dominated by the public keys even for small n. 332 2.2. Parameters 334 The core operations in this section depend on several parameters: 336 o A signature variant, either minimal-signature-size or minimal- 337 pubkey-size. These are defined in Section 2.1. 339 o A pairing-friendly elliptic curve, plus associated functionality 340 given in Section 1.3. 342 o H, a hash function H that MUST be a secure cryptographic hash 343 function, e.g., SHA-256 [FIPS180-4]. For security, H MUST output 344 at least ceil(log2(r)) bits, where r is the order of the subgroups 345 G1 and G2 defined by the pairing-friendly elliptic curve. 347 o hash_to_point, a function whose interface is described in 348 Section 1.3. When the signature variant is minimal-signature- 349 size, this function MUST output a point in G1. When the signature 350 variant is minimal-pubkey size, this function MUST output a point 351 in G2. For security, this function MUST be either a random oracle 352 encoding or a nonuniform encoding, as defined in 353 [I-D.irtf-cfrg-hash-to-curve]. 355 In addition, the following primitives are determined by the above 356 parameters: 358 o P, an elliptic curve point. When the signature variant is 359 minimal-signature-size, P is the distinguished point P2 that 360 generates the group G2 (see Section 1.3). When the signature 361 variant is minimal-pubkey-size, P is the distinguished point P1 362 that generates the group G1. 364 o r, the order of the subgroups G1 and G2 defined by the pairing- 365 friendly curve. 367 o pairing, a function that invokes the function e of Section 1.3, 368 with argument order depending on signature variant: 370 * For minimal-signature-size: 371 pairing(U, V) := e(U, V) 373 * For minimal-pubkey-size: 374 pairing(U, V) := e(V, U) 376 o point_to_pubkey and point_to_signature, functions that invoke the 377 appropriate serialization routine (Section 1.3) depending on 378 signature variant: 380 * For minimal-signature-size: 381 point_to_pubkey(P) := point_to_octets_E2(P) 382 point_to_signature(P) := point_to_octets_E1(P) 384 * For minimal-pubkey-size: 385 point_to_pubkey(P) := point_to_octets_E1(P) 386 point_to_signature(P) := point_to_octets_E2(P) 388 o pubkey_to_point and signature_to_point, functions that invoke the 389 appropriate deserialization routine (Section 1.3) depending on 390 signature variant: 392 * For minimal-signature-size: 393 pubkey_to_point(ostr) := octets_to_point_E2(ostr) 394 signature_to_point(ostr) := octets_to_point_E1(ostr) 396 * For minimal-pubkey-size: 397 pubkey_to_point(ostr) := octets_to_point_E1(ostr) 398 signature_to_point(ostr) := octets_to_point_E2(ostr) 400 o pubkey_subgroup_check and signature_subgroup_check, functions that 401 invoke the appropriate subgroup check routine (Section 1.3) 402 depending on signature variant: 404 * For minimal-signature-size: 405 pubkey_subgroup_check(P) := subgroup_check_E2(P) 406 signature_subgroup_check(P) := subgroup_check_E1(P) 408 * For minimal-pubkey-size: 409 pubkey_subgroup_check(P) := subgroup_check_E1(P) 410 signature_subgroup_check(P) := subgroup_check_E2(P) 412 2.3. KeyGen 414 The KeyGen algorithm generates a pair (PK, SK) deterministically 415 using the secret octet string IKM. 417 KeyGen uses HKDF [RFC5869] instantiated with the hash function H. 419 For security, IKM MUST be infeasible to guess, e.g., generated by a 420 trusted source of randomness. IKM MUST be at least 32 bytes long, 421 but it MAY be longer. 423 Because KeyGen is deterministic, implementations MAY choose either to 424 store the resulting (PK, SK) or to store IKM and call KeyGen to 425 derive the keys when necessary. 427 (PK, SK) = KeyGen(IKM) 429 Inputs: 430 - IKM, a secret octet string. See requirements above. 432 Outputs: 433 - PK, a public key encoded as an octet string. 434 - SK, the corresponding secret key, an integer 0 <= SK < r. 436 Definitions: 437 - HKDF-Extract is as defined in RFC5869, instantiated with hash H. 438 - HKDF-Expand is as defined in RFC5869, instantiated with hash H. 439 - L is the integer given by ceil((1.5 * ceil(log2(r))) / 8). 440 - "BLS-SIG-KEYGEN-SALT-" is an ASCII string comprising 20 octets. 441 - "" is the empty string. 443 Procedure: 444 1. PRK = HKDF-Extract("BLS-SIG-KEYGEN-SALT-", IKM) 445 2. OKM = HKDF-Expand(PRK, "", L) 446 3. x = OS2IP(OKM) mod r 447 4. xP = x * P 448 5. SK = x 449 6. PK = point_to_pubkey(xP) 450 7. return (PK, SK) 452 2.4. KeyValidate 454 The KeyValidate algorithm ensures that a public key is valid. 456 result = KeyValidate(PK) 458 Inputs: 459 - PK, a public key in the format output by KeyGen. 461 Outputs: 462 - result, either VALID or INVALID 464 Procedure: 465 1. xP = pubkey_to_point(PK) 466 2. If xP is INVALID, return INVALID 467 3. If pubkey_subgroup_check(xP) is INVALID, return INVALID 468 4. return VALID 470 2.5. CoreSign 472 The CoreSign algorithm computes a signature from SK, a secret key, 473 and message, an octet string. 475 signature = CoreSign(SK, message) 477 Inputs: 478 - SK, the secret key output by an invocation of KeyGen. 479 - message, an octet string. 481 Outputs: 482 - signature, an octet string. 484 Procedure: 485 1. Q = hash_to_point(message) 486 2. R = SK * Q 487 3. signature = point_to_signature(R) 488 4. return signature 490 2.6. CoreVerify 492 The CoreVerify algorithm checks that a signature is valid for the 493 octet string message under the public key PK. 495 The public key PK must satisfy KeyValidate(PK) == VALID 496 (Section 2.4). 498 result = CoreVerify(PK, message, signature) 500 Inputs: 501 - PK, a public key in the format output by KeyGen. 502 - message, an octet string. 503 - signature, an octet string in the format output by CoreSign. 505 Outputs: 506 - result, either VALID or INVALID. 508 Procedure: 509 1. R = signature_to_point(signature) 510 2. If R is INVALID, return INVALID 511 3. If signature_subgroup_check(R) is INVALID, return INVALID 512 4. xP = pubkey_to_point(PK) 513 5. Q = hash_to_point(message) 514 6. C1 = pairing(Q, xP) 515 7. C2 = pairing(R, P) 516 8. If C1 == C2, return VALID, else return INVALID 518 2.7. Aggregate 520 The Aggregate algorithm compresses multiple signatures into one. 522 signature = Aggregate(signature_1, ..., signature_n) 524 Inputs: 525 - signature_1, ..., signature_n, octet strings output by 526 either CoreSign or Aggregate. 528 Outputs: 529 - signature, an octet string encoding a compressed signature 530 that compbines all inputs; or INVALID. 532 Procedure: 533 1. accum = signature_to_point(signature_1) 534 2. If accum is INVALID, return INVALID 535 3. for i in 2, ..., n: 536 4. next = signature_to_point(signature_i) 537 5. If next is INVALID, return INVALID 538 6. accum = accum + next 539 7. signature = point_to_signature(accum) 540 8. return signature 542 2.8. CoreAggregateVerify 544 The CoreAggregateVerify algorithm checks an aggregated signature over 545 several (PK, message) pairs. 547 All public keys PK_i must satisfy KeyValidate(PK_i) == VALID 548 (Section 2.4). 550 result = CoreAggregateVerify((PK_1, message_1), ..., (PK_n, message_n), 551 signature) 553 Inputs: 554 - PK_1, ..., PK_n, public keys in the format output by KeyGen. 555 - message_1, ..., message_n, octet strings. 556 - signature, an octet string output by Aggregate. 558 Outputs: 559 - result, either VALID or INVALID. 561 Procedure: 562 1. R = signature_to_point(signature) 563 2. If R is INVALID, return INVALID 564 3. If signature_subgroup_check(R) is INVALID, return INVALID 565 4. C1 = 1 (the identity element in GT) 566 5. for i in 1, ..., n: 567 6. xP = pubkey_to_point(PK_i) 568 7. Q = hash_to_point(message_i) 569 8. C1 = C1 * pairing(Q, xP) 570 9. C2 = pairing(R, P) 571 10. If C1 == C2, return VALID, else return INVALID 573 3. BLS Signatures 575 This section defines three signature schemes: basic, message 576 augmentation, and proof of possession. These schemes differ in the 577 ways that they defend against rogue key attacks (Section 1.3). 579 All of the schemes in this section are built on a set of core 580 operations defined in Section 2. Thus, defining a scheme requires 581 fixing a set of parameters as defined in Section 2.2. 583 All three schemes expose the KeyGen and Aggregate operations that are 584 defined in Section 2. The sections below define the other API 585 functions (Section 1.4) for each scheme. 587 3.1. Basic scheme 589 In a basic scheme, rogue key attacks are handled by requiring all 590 messages signed by an aggregate signature to be distinct. This 591 requirement is enforced in the definition of AggregateVerify. 593 The Sign and Verify functions are identical to CoreSign and 594 CoreVerify (Section 2), respectively. AggregateVerify is defined 595 below. 597 All public keys PK supplied as arguments to Verify and 598 AggregateVerify MUST satisfy KeyValidate(PK) == VALID (Section 2.4). 600 3.1.1. AggregateVerify 602 This function first ensures that all messages are distinct, and then 603 invokes CoreAggregateVerify. 605 result = AggregateVerify((PK_1, message_1), ..., (PK_n, message_n), 606 signature) 608 Inputs: 609 - PK_1, ..., PK_n, public keys in the format output by KeyGen. 610 - message_1, ..., message_n, octet strings. 611 - signature, an octet string output by Aggregate. 613 Outputs: 614 - result, either VALID or INVALID. 616 Procedure: 617 1. If any two input messages are equal, return INVALID. 618 2. return CoreAggregateVerify((PK_1, message_1), ..., (PK_n, message_n), 619 signature) 621 3.2. Message augmentation 623 In a message augmentation scheme, signatures are generated over the 624 concatenation of the public key and the message, ensuring that 625 messages signed by different public keys are distinct. 627 All public keys PK supplied as arguments to Verify and 628 AggregateVerify MUST satisfy KeyValidate(PK) == VALID (Section 2.4). 630 3.2.1. Sign 632 To match the API for Sign defined in Section 1.4, this function 633 recomputes the public key corresponding to the input SK. 634 Implementations MAY instead implement an interface that takes the 635 public key as an input. 637 Note that the point P and the point_to_pubkey function are defined in 638 Section 2.2. 640 signature = Sign(SK, message) 642 Inputs: 643 - SK, a secret key output by an invocation of KeyGen. 644 - message, an octet string. 646 Outputs: 647 - signature, an octet string. 649 Procedure: 650 1. xP = SK * P 651 2. PK = point_to_pubkey(xP) 652 3. return CoreSign(SK, PK || message) 654 3.2.2. Verify 656 result = Verify(PK, message, signature) 658 Inputs: 659 - PK, a public key in the format output by KeyGen. 660 - message, an octet string. 661 - signature, an octet string in the format output by CoreSign. 663 Outputs: 664 - result, either VALID or INVALID. 666 Procedure: 667 1. return CoreVerify(PK, PK || message, signature) 669 3.2.3. AggregateVerify 671 result = AggregateVerify((PK_1, message_1), ..., (PK_n, message_n), 672 signature) 674 Inputs: 675 - PK_1, ..., PK_n, public keys in the format output by KeyGen. 676 - message_1, ..., message_n, octet strings. 677 - signature, an octet string output by Aggregate. 679 Outputs: 680 - result, either VALID or INVALID. 682 Procedure: 683 1. for i in 1, ..., n: 684 2. mprime_i = PK_i || message_i 685 3. return CoreAggregateVerify((PK_1, mprime_1), ..., (PK_n, mprime_n), 686 signature) 688 3.3. Proof of possession 690 A proof of possession scheme uses a separate public key validation 691 step, called a proof of possession, to defend against rogue key 692 attacks. This enables an optimization to aggregate signature 693 verification for the case that all signatures are on the same 694 message. 696 The Sign, Verify, and AggregateVerify functions are identical to 697 CoreSign, CoreVerify, and CoreAggregateVerify (Section 2), 698 respectively. In addition, a proof of possession scheme defines 699 three functions beyond the standard API (Section 1.4): 701 o PopProve(SK) -> proof: an algorithm that generates a proof of 702 possession for the public key corresponding to secret key SK. 704 o PopVerify(PK, proof) -> VALID or INVALID: an algorithm that 705 outputs VALID if proof is valid for PK, and INVALID otherwise. 707 o FastAggregateVerify(PK_1, ..., PK_n, message, signature) -> VALID 708 or INVALID: a verification algorithm for the aggregate of multiple 709 signatures on the same message. This function is faster than 710 AggregateVerify. 712 All public keys used by Verify, AggregateVerify, and 713 FastAggregateVerify MUST be accompanied by a proof of possession 714 generated by PopProve, and the result of PopVerify on this proof MUST 715 be VALID. 717 3.3.1. Parameters 719 In addition to the parameters required to instantiate the core 720 operations (Section 2.2), a proof of possession scheme requires one 721 further parameter: 723 o hash_pubkey_to_point(PK) -> P: a cryptographic hash function that 724 takes as input a public key and outputs a point in the same 725 subgroup as the hash_to_point algorithm used to instantiate the 726 core operations. 727 For security, this function MUST be orthogonal to the 728 hash_to_point function. In addition, this function MUST be either 729 a random oracle encoding or a nonuniform encoding, as defined in 730 [I-D.irtf-cfrg-hash-to-curve]. The RECOMMENDED way of 731 instantiating hash_pubkey_to_point is to use the same hash-to- 732 curve function as hash_to_point, with a different domain 733 separation tag (see [I-D.irtf-cfrg-hash-to-curve], Section 5.1). 735 3.3.2. PopProve 737 This function recomputes the public key coresponding to the input SK. 738 Implementations MAY instead implement an interface that takes the 739 public key as input. 741 Note that the point P and the point_to_pubkey and point_to_signature 742 functions are defined in Section 2.2. The hash_pubkey_to_point 743 function is defined in Section 3.3.1. 745 proof = PopProve(SK) 747 Inputs: 748 - SK, a secret key output by an invocation of KeyGen. 750 Outputs: 751 - proof, an octet string. 753 Procedure: 754 1. xP = SK * P 755 2. PK = point_to_pubkey(xP) 756 3. Q = hash_pubkey_to_point(PK) 757 4. R = SK * Q 758 5. proof = point_to_signature(R) 759 6. return signature 761 3.3.3. PopVerify 763 Note that the following uses several functions defined in Section 2. 764 The hash_pubkey_to_point function is defined in Section 3.3.1. 766 result = PopVerify(PK, proof) 768 Inputs: 769 - PK, a public key inthe format output by KeyGen. 770 - proof, an octet string in the format output by PopProve. 772 Outputs: 773 - result, either VALID or INVALID 775 Procedure: 776 1. R = signature_to_point(proof) 777 2. If R is INVALID, return INVALID 778 3. If signature_subgroup_check(R) is INVALID, return INVALID 779 4. If KeyValidate(PK) is INVALID, return INVALID 780 5. xP = pubkey_to_point(PK) 781 6. Q = hash_pubkey_to_point(PK) 782 7. C1 = pairing(Q, xP) 783 8. C2 = pairing(R, P) 784 9. If C1 == C2, return VALID, else return INVALID 786 3.3.4. FastAggregateVerify 788 Note that the following uses several functions defined in Section 2. 790 result = FastAggregateVerify(PK_1, ..., PK_n, message, signature) 792 Inputs: 793 - PK_1, ..., PK_n, public keys in the format output by KeyGen. 794 - message, an octet string. 795 - signature, an octet string output by Aggregate. 797 Outputs: 798 - result, either VALID or INVALID. 800 Procedure: 801 1. accum = pubkey_to_point(PK_1) 802 2. for i in 2, ..., n: 803 3. next = pubkey_to_point(PK_i) 804 4. accum = accum + next 805 5. PK = point_to_pubkey(accum) 806 6. return CoreVerify(PK, message, signature) 808 4. Ciphersuites 810 This section defines the format for a BLS ciphersuite. It also gives 811 concrete ciphersuites based on the BLS12-381 pairing-friendly 812 elliptic curve [I-D.yonezawa-pairing-friendly-curves]. 814 4.1. Ciphersuite format 816 A ciphersuite specifies all parameters from Section 2.2, a scheme 817 from Section 3, and any parameters the scheme requires. In 818 particular, a ciphersuite comprises: 820 o ID: the ciphersuite ID, an ASCII string. The RECOMMENDED format 821 for this string is 822 "BLS_SIG_" || H2C_SUITE || "_" || SC_TAG || "_" 824 * strings in double quotes are literal ASCII octet sequences 826 * H2C_SUITE is the name of the hash-to-curve ciphersuite used to 827 define the hash_to_point and hash_pubkey_to_point functions. 829 * SC_TAG SHOULD be "NUL" when SC is basic, "AUG" when SC is 830 message-augmentation, or "POP" when SC is proof-of-possession. 832 o SC: the scheme, either basic, message-augmentation, or proof-of- 833 possession. 835 o SV: the signature variant, either minimal-signature-size or 836 minimal-pubkey-size. 838 o EC: a pairing-friendly elliptic curve, plus all associated 839 functionality (Section 1.3). 841 o H: a cryptographic hash function. 843 o hash_to_point: a hash from arbitrary strings to elliptic curve 844 points. It is RECOMMENDED that hash_to_point be defined in terms 845 of a hash-to-curve suite [I-D.irtf-cfrg-hash-to-curve] with domain 846 separation tag equal to the ID string. 848 o hash_pubkey_to_point (only specified when SC is proof-of- 849 possession): a hash from serialized public keys to elliptic curve 850 points. It is RECOMMENDED that hash_pubkey_to_point be defined in 851 terms of a has-to-curve suite [I-D.irtf-cfrg-hash-to-curve], with 852 domain separation tag constructed similarly to the ID string, 853 namely: 854 "BLS_POP_" || H2C_SUITE || "_" || SC_TAG || "_" 856 4.2. Ciphersuites for BLS12-381 858 The following ciphersuites are all built on the BLS12-381 elliptic 859 curve. The required primitives for this curve are given in 860 Appendix A. 862 These ciphersuites use the hash-to-curve suites BLS12381G1-SHA256- 863 SSWU-RO- and BLS12381G2-SHA256-SSWU-RO- defined in 864 [I-D.irtf-cfrg-hash-to-curve]. Each ciphersuite defines a unique 865 hash_to_point function by specifying a domain separation tag (see 866 [@I-D.irtf-cfrg-hash-to-curve, Section 5.1). 868 4.2.1. Basic 870 The ciphersuite with ID BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_NUL_ uses 871 the following parameters, in addition to the common parameters below. 873 o SV: minimal-signature-size 875 o hash_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII domain 876 separation tag 877 BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_NUL_ 879 The ciphersuite with ID BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_NUL_ uses 880 the following parameters, in addition to the common parameters below. 882 o SV: minimal-pubkey-size 884 o hash_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII domain 885 separation tag 886 BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_NUL_ 888 The above ciphersuites share the following common parameters: 890 o SC: basic 892 o EC: BLS12-381, as defined in Appendix A. 894 o H: SHA-256 896 4.2.2. Message augmentation 898 The ciphersuite with ID BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_AUG_ uses 899 the following parameters, in addition to the common parameters below. 901 o SV: minimal-signature-size 903 o hash_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII domain 904 separation tag 905 BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_AUG_ 907 The ciphersuite with ID BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_AUG_ uses 908 the following parameters, in addition to the common parameters below. 910 o SV: minimal-pubkey-size 912 o hash_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII domain 913 separation tag 914 BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_AUG_ 916 The above ciphersuites share the following common parameters: 918 o SC: message-augmentation 920 o EC: BLS12-381, as defined in Appendix A. 922 o H: SHA-256 924 4.2.3. Proof of possession 926 The ciphersuite with ID BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_POP_ uses 927 the following parameters, in addition to the common parameters below. 929 o SV: minimal-signature-size 931 o hash_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII domain 932 separation tag 933 BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_POP_ 935 o hash_pubkey_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII 936 domain separation tag 937 BLS_POP_BLS12381G1-SHA256-SSWU-RO-_POP_ 939 The ciphersuite with ID BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_POP_ uses 940 the following parameters, in addition to the common parameters below. 942 o SV: minimal-pubkey-size 944 o hash_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII domain 945 separation tag 946 BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_POP_ 948 o hash_pubkey_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII 949 domain separation tag 950 BLS_POP_BLS12381G2-SHA256-SSWU-RO-_POP_ 952 The above ciphersuites share the following common parameters: 954 o SC: proof-of-possession 956 o EC: BLS12-381, as defined in Appendix A. 958 o H: SHA-256 960 5. Security Considerations 962 5.1. Validating public keys 964 All algorithms in Section 2 and Section 3 that operate on public keys 965 require first validating these keys. For the basic and message 966 augmentation schemes, the use of KeyValidate is REQUIRED. For the 967 proof of possession scheme, each public key MUST be accompanied by a 968 proof of possession, and use of PopVerify is REQUIRED. 970 Note that implementations MAY cache validation results for public 971 keys in order to avoid unnecessarily repeating validation for known 972 keys. 974 5.2. Skipping membership check 976 Some existing implementations skip the signature_subgroup_check 977 invocation in CoreVerify (Section 2.6), whose purpose is ensuring 978 that the signature is an element of a prime-order subgroup. This 979 check is REQUIRED of conforming implementations, for two reasons. 981 1. For most pairing-friendly elliptic curves used in practice, the 982 pairing operation e (Section 1.3) is undefined when its input 983 points are not in the prime-order subgroups of E1 and E2. The 984 resulting behavior is unpredictable, and may enable forgeries. 986 2. Even if the pairing operation behaves properly on inputs that are 987 outside the correct subgroups, skipping the subgroup check breaks 988 the strong unforgeability property. 990 5.3. Side channel attacks 992 Implementations of the signing algorithm SHOULD protect the secret 993 key from side-channel attacks. One method for protecting against 994 certain side-channel attacks is ensuring that the implementation 995 executes exactly the same sequence of instructions and performs 996 exactly the same memory accesses, for any value of the secret key. 997 In other words, implementations on the underlying pairing-friendly 998 elliptic curve SHOULD run in constant time. 1000 5.4. Randomness considerations 1002 BLS signatures are deterministic. This protects against attacks 1003 arising from signing with bad randomness, for example, the nonce 1004 reuse attack on ECDSA [HDWH12]. 1006 As discussed in Section 2.3, the IKM input to KeyGen MUST be 1007 infeasible to guess and MUST be kept secret. One possibility is to 1008 generate IKM from a trusted source of randonmess. Guidelines on 1009 constructing such a source are outside the scope of this document. 1011 5.5. Implementing hash_to_point and hash_pubkey_to_point 1013 The security analysis models hash_to_point and hash_pubkey_to_point 1014 as random oracles. It is crucial that these functions are 1015 implemented using a cryptographically secure hash function. For this 1016 purpose, implementations MUST meet the requirements of 1017 [I-D.irtf-cfrg-hash-to-curve]. 1019 In addition, ciphersuites MUST specify unique domain separation tags 1020 for hash_to_point and hash_pubkey_to_point. The domain separation 1021 tag format used in Section 4 is the RECOMMENDED one. 1023 6. Implementation Status 1025 This section will be removed in the final version of the draft. 1026 There are currently several implementations of BLS signatures using 1027 the BLS12-381 curve. 1029 o Algorand: bls_sigs_ref [1] 1031 o Chia: spec [2] python/C++ [3]. Here, they are swapping G1 and G2 1032 so that the public keys are small, and the benefits of avoiding a 1033 membership check during signature verification would even be more 1034 substantial. The current implementation does not seem to 1035 implement the membership check. Chia uses the Fouque-Tibouchi 1036 hashing to the curve, which can be done in constant time. 1038 o Dfinity: go [4] BLS [5]. The current implementations do not seem 1039 to implement the membership check. 1041 o Ethereum 2.0: spec [6] 1043 7. Related Standards 1045 o Pairing-friendly curves draft-yonezawa-pairing-friendly-curves [7] 1047 o Pairing-based Identity-Based Encryption IEEE 1363.3 [8]. 1049 o Identity-Based Cryptography Standard rfc5901 [9]. 1051 o Hashing to Elliptic Curves draft-irtf-cfrg-hash-to-curve-04 [10], 1052 in order to implement the hash function hash_to_point. 1054 o EdDSA rfc8032 [11] 1056 8. IANA Considerations 1058 TBD (consider to register ciphersuite identifiers for BLS signature 1059 and underlying pairing curves) 1061 9. References 1063 9.1. Normative References 1065 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1066 Requirement Levels", BCP 14, RFC 2119, 1067 DOI 10.17487/RFC2119, March 1997, 1068 . 1070 [ZCash] Electric Coin Company, "BLS12-381", July 2017, 1071 . 1074 9.2. Informative References 1076 [BDN18] Boneh, D., Drijvers, M., and G. Neven, "Compact multi- 1077 signatures for shorter blockchains", December 2018, 1078 . 1081 [BGLS03] Boneh, D., Gentry, C., Lynn, B., and H. Shacham, 1082 "Aggregate and verifiably encrypted signatures from 1083 bilinear maps", May 2003, . 1086 [BLS01] Boneh, D., Lynn, B., and H. Shacham, "Short signatures 1087 from the Weil pairing", December 2001, 1088 . 1090 [BNN07] Bellare, M., Namprempre, C., and G. Neven, "Unrestricted 1091 aggregate signatures", July 2007, 1092 . 1095 [Bol03] Boldyreva, A., "Threshold Signatures, Multisignatures and 1096 Blind Signatures Based on the Gap-Diffie-Hellman-Group 1097 Signature Scheme", January 2003, 1098 . 1101 [Bowe19] Bowe, S., "Faster subgroup checks for BLS12-381", July 1102 2019, . 1104 [FIPS180-4] 1105 National Institute of Standards and Technology (NIST), 1106 "FIPS Publication 180-4: Secure Hash Standard", August 1107 2015, . 1110 [HDWH12] Heninger, N., Durumeric, Z., Wustrow, E., and J. 1111 Halderman, "Mining your Ps and Qs: Detection of widespread 1112 weak keys in network devices", August 2012, 1113 . 1116 [I-D.irtf-cfrg-hash-to-curve] 1117 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1118 C. Wood, "Hashing to Elliptic Curves", draft-irtf-cfrg- 1119 hash-to-curve-04 (work in progress), July 2019. 1121 [I-D.yonezawa-pairing-friendly-curves] 1122 Yonezawa, S., Kobayashi, T., and T. Saito, "Pairing- 1123 Friendly Curves", draft-yonezawa-pairing-friendly- 1124 curves-02 (work in progress), July 2019. 1126 [LOSSW06] Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., and B. 1127 Waters, "Sequential Aggregate Signatures and 1128 Multisignatures Without Random Oracles", May 2006, 1129 . 1131 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1132 Key Derivation Function (HKDF)", RFC 5869, 1133 DOI 10.17487/RFC5869, May 2010, 1134 . 1136 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1137 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1138 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1139 . 1141 [RY07] Ristenpart, T. and S. Yilek, "The Power of Proofs-of- 1142 Possession: Securing Multiparty Signatures against Rogue- 1143 Key Attacks", May 2007, . 1146 9.3. URIs 1148 [1] https://github.com/kwantam/bls_sigs_ref 1150 [2] https://github.com/Chia-Network/bls-signatures/blob/master/ 1151 SPEC.md 1153 [3] https://github.com/Chia-Network/bls-signatures 1155 [4] https://github.com/dfinity/go-dfinity-crypto 1157 [5] https://github.com/dfinity/bls 1159 [6] https://github.com/ethereum/eth2.0-specs/blob/master/specs/ 1160 bls_signature.md 1162 [7] https://tools.ietf.org/html/draft-yonezawa-pairing-friendly- 1163 curves-00 1165 [8] https://ieeexplore.ieee.org/document/6662370 1167 [9] https://tools.ietf.org/html/rfc5091 1169 [10] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-02 1171 [11] https://tools.ietf.org/html/rfc8032 1173 Appendix A. BLS12-381 1175 The ciphersuites in Section 4 are based upon the BLS12-381 pairing- 1176 friendly elliptic curve. The following defines the correspondence 1177 between the primitives in Section 1.3 and the parameters given in 1178 Section 4.2.2 of [I-D.yonezawa-pairing-friendly-curves]. 1180 o E1, G1: the curve E and its order-r subgroup. 1182 o E2, G2: the curve E' and its order-r subgroup. 1184 o GT: the subgroup G_T. 1186 o P1: the point BP. 1188 o P2: the point BP'. 1190 o e: the optimal Ate pairing defined in Appendix A of 1191 [I-D.yonezawa-pairing-friendly-curves]. 1193 o point_to_octets and octets_to_point use the compressed 1194 serialization formats for E1 and E2 defined by [ZCash]. 1196 o subgroup_check MAY use either the naive check described in 1197 Section 1.3 or the optimized check given by [Bowe19]. 1199 Appendix B. Test Vectors 1201 TBA: (i) test vectors for both variants of the signature scheme 1202 (signatures in G2 instead of G1) , (ii) test vectors ensuring 1203 membership checks, (iii) intermediate computations ctr, hm. 1205 Appendix C. Security analyses 1207 The security properties of the BLS signature scheme are proved in 1208 [BLS01]. 1210 [BGLS03] prove the security of aggregate signatures over distinct 1211 messages, as in the basic scheme of Section 3.1. 1213 [BNN07] prove security of the message augmentation scheme of 1214 Section 3.2. 1216 [Bol03][LOSSW06][RY07] prove security of constructions related to the 1217 proof of possession scheme of Section 3.3. 1219 [BDN18] prove the security of another rogue key defense; this defense 1220 is not standardized in this document. 1222 Authors' Addresses 1224 Dan Boneh 1225 Stanford University 1226 USA 1228 Email: dabo@cs.stanford.edu 1230 Riad S. Wahby 1231 Stanford University 1232 USA 1234 Email: rsw@cs.stanford.edu 1235 Sergey Gorbunov 1236 Algorand and University of Waterloo 1237 Boston, MA 1238 USA 1240 Email: sergey@algorand.com 1242 Hoeteck Wee 1243 Algorand and ENS, Paris 1244 Boston, MA 1245 USA 1247 Email: wee@di.ens.fr 1249 Zhenfei Zhang 1250 Algorand 1251 Boston, MA 1252 USA 1254 Email: zhenfei@algorand.com