idnits 2.17.1 draft-irtf-cfrg-pairing-friendly-curves-10.txt: -(1285): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1318): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There are 6 instances of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (30 July 2021) is 999 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 2360 == Outdated reference: A later version (-23) exists of draft-ietf-lwig-curve-representations-08 == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-09 Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG Y. Sakemi, Ed. 3 Internet-Draft Infours 4 Intended status: Informational T. Kobayashi 5 Expires: 31 January 2022 T. Saito 6 NTT 7 R. Wahby 8 Stanford University 9 30 July 2021 11 Pairing-Friendly Curves 12 draft-irtf-cfrg-pairing-friendly-curves-10 14 Abstract 16 Pairing-based cryptography, a subfield of elliptic curve 17 cryptography, has received attention due to its flexible and 18 practical functionality. Pairings are special maps defined using 19 elliptic curves and it can be applied to construct several 20 cryptographic protocols such as identity-based encryption, attribute- 21 based encryption, and so on. At CRYPTO 2016, Kim and Barbulescu 22 proposed an efficient number field sieve algorithm named exTNFS for 23 the discrete logarithm problem in a finite field. Several types of 24 pairing-friendly curves such as Barreto-Naehrig curves are affected 25 by the attack. In particular, a Barreto-Naehrig curve with a 254-bit 26 characteristic was adopted by a lot of cryptographic libraries as a 27 parameter of 128-bit security, however, it ensures no more than the 28 100-bit security level due to the effect of the attack. In this 29 memo, we list the security levels of certain pairing-friendly curves, 30 and motivate our choices of curves. First, we summarize the adoption 31 status of pairing-friendly curves in standards, libraries and 32 applications, and classify them in the 128-bit, 192-bit, and 256-bit 33 security levels. Then, from the viewpoints of "security" and "widely 34 used", we select the recommended pairing-friendly curves considering 35 exTNFS. 37 Status of This Memo 39 This Internet-Draft is submitted in full conformance with the 40 provisions of BCP 78 and BCP 79. 42 Internet-Drafts are working documents of the Internet Engineering 43 Task Force (IETF). Note that other groups may also distribute 44 working documents as Internet-Drafts. The list of current Internet- 45 Drafts is at https://datatracker.ietf.org/drafts/current/. 47 Internet-Drafts are draft documents valid for a maximum of six months 48 and may be updated, replaced, or obsoleted by other documents at any 49 time. It is inappropriate to use Internet-Drafts as reference 50 material or to cite them other than as "work in progress." 52 This Internet-Draft will expire on 31 January 2022. 54 Copyright Notice 56 Copyright (c) 2021 IETF Trust and the persons identified as the 57 document authors. All rights reserved. 59 This document is subject to BCP 78 and the IETF Trust's Legal 60 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 61 license-info) in effect on the date of publication of this document. 62 Please review these documents carefully, as they describe your rights 63 and restrictions with respect to this document. Code Components 64 extracted from this document must include Simplified BSD License text 65 as described in Section 4.e of the Trust Legal Provisions and are 66 provided without warranty as described in the Simplified BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 71 1.1. Pairing-based Cryptography . . . . . . . . . . . . . . . 3 72 1.2. Applications of Pairing-based Cryptography . . . . . . . 3 73 1.3. Motivation and Contribution . . . . . . . . . . . . . . . 5 74 1.4. Requirements Terminology . . . . . . . . . . . . . . . . 6 75 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 6 76 2.1. Elliptic Curves . . . . . . . . . . . . . . . . . . . . . 6 77 2.2. Pairings . . . . . . . . . . . . . . . . . . . . . . . . 7 78 2.3. Barreto-Naehrig Curves . . . . . . . . . . . . . . . . . 8 79 2.4. Barreto-Lynn-Scott Curves . . . . . . . . . . . . . . . . 8 80 2.5. Representation Convention for an Extension Field . . . . 9 81 3. Security of Pairing-Friendly Curves . . . . . . . . . . . . . 10 82 3.1. Evaluating the Security of Pairing-Friendly Curves . . . 10 83 3.2. Impact of Recent Attacks . . . . . . . . . . . . . . . . 11 84 4. Selection of Pairing-Friendly Curves . . . . . . . . . . . . 12 85 4.1. Adoption Status of Pairing-friendly Curves . . . . . . . 12 86 4.1.1. International Standards . . . . . . . . . . . . . . . 15 87 4.1.2. Cryptographic Libraries . . . . . . . . . . . . . . . 15 88 4.1.3. Applications . . . . . . . . . . . . . . . . . . . . 17 89 4.2. For 128-bit Security . . . . . . . . . . . . . . . . . . 17 90 4.2.1. BLS Curves for the 128-bit security level 91 (BLS12_381) . . . . . . . . . . . . . . . . . . . . . 17 92 4.2.2. BN Curves for the 128-bit security level (BN462) . . 19 93 4.3. For 256-bit Security . . . . . . . . . . . . . . . . . . 21 94 5. Security Considerations . . . . . . . . . . . . . . . . . . . 25 95 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 96 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 27 97 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 27 98 8.1. Normative References . . . . . . . . . . . . . . . . . . 27 99 8.2. Informative References . . . . . . . . . . . . . . . . . 28 100 Appendix A. Computing the Optimal Ate Pairing . . . . . . . . . 35 101 A.1. Optimal Ate Pairings over Barreto-Naehrig Curves . . . . 36 102 A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves . . . 36 103 Appendix B. Test Vectors of Optimal Ate Pairing . . . . . . . . 37 104 Appendix C. ZCash serialization format for BLS12_381 . . . . . . 48 105 C.1. Point Serialization Procedure . . . . . . . . . . . . . . 49 106 C.2. Point deserialization procedure . . . . . . . . . . . . . 50 107 Appendix D. Adoption Status of Pairing-Friendly Curves with the 108 100-bit Security Level . . . . . . . . . . . . . . . . . 52 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 54 111 1. Introduction 113 1.1. Pairing-based Cryptography 115 Elliptic curve cryptography is an important area in currently 116 deployed cryptography. The cryptographic algorithms based on 117 elliptic curve cryptography, such as the Elliptic Curve Digital 118 Signature Algorithm (ECDSA), are widely used in many applications. 120 Pairing-based cryptography, a subfield of elliptic curve 121 cryptography, has attracted much attention due to its flexible and 122 practical functionality. Pairings are special maps defined using 123 elliptic curves. Pairings are fundamental in the construction of 124 several cryptographic algorithms and protocols such as identity-based 125 encryption (IBE), attribute-based encryption (ABE), authenticated key 126 exchange (AKE), short signatures, and so on. Several applications of 127 pairing-based cryptography are currently in practical use. 129 As the importance of pairings grows, elliptic curves where pairings 130 are efficiently computable are studied and the special curves called 131 pairing-friendly curves are proposed. 133 1.2. Applications of Pairing-based Cryptography 135 Several applications using pairing-based cryptography have already 136 been standardized and deployed. We list here some examples of 137 applications available in the real world. 139 IETF published RFCs for pairing-based cryptography such as Identity- 140 Based Cryptography [RFC5091], Sakai-Kasahara Key Encryption (SAKKE) 141 [RFC6508], and Identity-Based Authenticated Key Exchange (IBAKE) 142 [RFC6539]. SAKKE is applied to Multimedia Internet KEYing (MIKEY) 143 [RFC6509] and used in 3GPP [SAKKE]. 145 Pairing-based key agreement protocols are standardized in ISO/IEC 146 [ISOIEC11770-3]. In [ISOIEC11770-3], a key agreement scheme by Joux 147 [Joux00], identity-based key agreement schemes by Smart-Chen-Cheng 148 [CCS07] and Fujioka-Suzuki-Ustaoglu [FSU10] are specified. 150 MIRACL implements M-Pin, a multi-factor authentication protocol 151 [M-Pin]. The M-Pin protocol includes a type of zero-knowledge proof, 152 where pairings are used for its construction. 154 The Trusted Computing Group (TCG) specified the Elliptic Curve Direct 155 Anonymous Attestation (ECDAA) in the specification of a Trusted 156 Platform Module (TPM) [TPM]. ECDAA is a protocol for proving the 157 attestation held by a TPM to a verifier without revealing the 158 attestation held by that TPM. Pairings are used in the construction 159 of ECDAA. FIDO Alliance [FIDO] and W3C [W3C] also published an ECDAA 160 algorithm similar to TCG. 162 Intel introduced Intel Enhanced Privacy ID (EPID) that enables remote 163 attestation of a hardware device while preserving the privacy of the 164 device as part of the functionality of Intel Software Guard 165 Extensions (SGX) [EPID]. They extended TPM ECDAA to realize such 166 functionality. A pairing-based EPID was proposed [BL10] and 167 distributed along with Intel SGX applications. 169 Zcash implemented their own zero-knowledge proof algorithm named 170 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk- 171 SNARKs) [Zcash]. zk-SNARKs are used for protecting the privacy of 172 transactions of Zcash. They use pairings to construct zk-SNARKs. 174 Cloudflare introduced Geo Key Manager [Cloudflare] to restrict 175 distribution of customers' private keys to a subset of their data 176 centers. To achieve this functionality, ABE is used, and pairings 177 take a role as a building block. In addition, Cloudflare published a 178 new cryptographic library, the Cloudflare Interoperable, Reusable 179 Cryptographic Library (CIRCL) [CIRCL] in 2019. They plan to include 180 securely implemented subroutines for pairing computations on certain 181 secure pairing-friendly curves in CIRCL. 183 Currently, Boneh-Lynn-Shacham (BLS) signature schemes are being 184 standardized [I-D.boneh-bls-signature] and utilized in several 185 blockchain projects such as Ethereum [Ethereum], Algorand [Algorand], 186 Chia Network [Chia], and DFINITY [DFINITY]. The aggregation 187 functionality of BLS signatures is effective for their applications 188 of decentralization and scalability. 190 1.3. Motivation and Contribution 192 At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field 193 sieve (NFS) algorithm for the discrete logarithm problem in a finite 194 field GF(p^k) [KB16]. The attack improves the polynomial selection 195 that is the first step in the number field sieve algorithm for 196 discrete logarithms in GF(p^k). The idea is applicable when the 197 embedding degree k is a composite that satisfies k = i*j (gcd (i, j) 198 = 1, i, j> 1). The basic idea is based on the equality GF(p^k) = 199 (GF(p^i)^j) and one of the improvement for reducing the amount of 200 cost for solving the discrete logarithm problem is using sub-field 201 calculation. Several types of pairing-friendly curves such as 202 Barreto-Naehrig curves (BN curves)[BN05] and Barreto-Lynn-Scott 203 curves (BLS curves)[BLS02] are affected by the attack, since a 204 pairing-friendly curve suitable for cryptographic applications 205 requires that the discrete logarithm problem is sufficiently 206 difficult. Please refer to [KB16] for detailed ideas and calculation 207 algorithms of the attack by Kim. In particular, BN254, which is a BN 208 curve with a 254-bit characteristic effective for pairing 209 calculations, was adopted by a lot of cryptographic libraries as a 210 parameter of the 128-bit security level, however, BN254 ensures no 211 more than the 100-bit security level due to the effect of the attack, 212 where the security levels described in this memo correspond to the 213 security strength of NIST recommendation [NIST]. 215 To resolve this effect immediately, several research groups and 216 implementers re-evaluated the security of pairing-friendly curves and 217 they respectively proposed various curves that are secure against the 218 attack [BD18] [BLS12_381]. 220 In this memo, we list the security levels of certain pairing-friendly 221 curves, and motivate our choices of curves. First, we summarize the 222 adoption status of pairing-friendly curves in international 223 standards, libraries and applications, and classify them in the 224 128-bit, 192-bit, and 256-bit security levels. Then, from the 225 viewpoints of "security" and "widely used", pairing-friendly curves 226 corresponding to each security level are selected in accordance with 227 the security evaluation by Barbulescu and Duquesne [BD18]. 229 As a result, we recommend the BLS curve with 381-bit characteristic 230 of embedding degree 12 and the BN curve with the 462-bit 231 characteristic for the 128-bit security level, and the BLS curves of 232 embedding degree 48 with the 581-bit characteristic for the 256-bit 233 security level. This memo shows their specific test vectors. 235 1.4. Requirements Terminology 237 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 238 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 239 "OPTIONAL" in this document are to be interpreted as described in BCP 240 14 [RFC2119] [RFC8174] when, and only when, they appear in all 241 capitals, as shown here. 243 2. Preliminaries 245 2.1. Elliptic Curves 247 Let p be a prime number and q = p^n for a natural number n > 0, where 248 p at least 5. Let GF(q) be a finite field. The curve defined by the 249 following equation E is called an elliptic curve: 251 E : y^2 = x^3 + a * x + b, 253 and a and b in GF(q) satisfy the discriminant inequality 4 * a^3 + 27 254 * b^2 != 0 mod q. This is called the Weierstrass normal form of an 255 elliptic curve. 257 A solution (x,y) to the equation E can be thought of as a point on 258 the corresponding curve. For a natural number k, we define the set 259 of (GF(q^k))-rational points of E, denoted by E(GF(q^k)), to be the 260 set of all solutions (x,y) in GF(q^k), together with a 'point at 261 infinity' O_E, which is defined to lie on every vertical line passing 262 through the curve E. 264 The set E(GF(q^k)) forms a group under a group law that can be 265 defined geometrically as follows. For P and Q in E(GF(q^k)) define P 266 + Q to be the reflection around the x-axis of the unique third point 267 R of intersection of the straight line passing through P and Q with 268 the curve E. If the straight line is tangent to E, we say that it 269 passes through that point twice. The identity of this group is the 270 point at infinity O_E. We also define scalar multiplication [K]P for 271 a positive integer K as the point P added to itself (K-1) times. 272 Here, [0]P becomes the point at infinity O_E and the relation [-K]P = 273 -([K]P) is satisfied. 275 2.2. Pairings 277 A pairing is a bilinear map defined on two subgroups of rational 278 points of an elliptic curve. Examples include the Weil pairing, the 279 Tate pairing, the optimal Ate pairing [Ver09], and so on. The 280 optimal Ate pairing is considered to be the most efficient to compute 281 and is the one that is most commonly used for practical 282 implementation. 284 Let E be an elliptic curve defined over a prime field GF(p). Let k 285 be the minimum integer for which r is a divisor of p^k - 1; this is 286 called the embedding degree of E over GF(p). Let G_1 be a cyclic 287 subgroup of E(GF(p)) of order r, there also exists a cyclic subgroup 288 of E(GF(p^k)) of order r, define this to be G_2. Let d be a divisor 289 of k and E' be an elliptic curve defined over GF(p^(k/d)). If an 290 isomorphism from E' to E(GF(p^k)) exists, then E' is called the twist 291 of E. It can sometimes be convenient for efficiency to do the 292 computations of G_2 in the twist E', and so consider G_2 to instead 293 be a subgroup of E'. Let G_T be an order r subgroup of the 294 multiplicative group (GF(p^k))^*; this exists by definition of k. 296 A pairing is defined as a bilinear map e: (G_1, G_2) -> G_T 297 satisfying the following properties: 299 1. Bilinearity: for any S in G_1, T in G_2, and integers K and L, 300 e([K]S, [L]T) = e(S, T)^{K * L}. 302 2. Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S = 303 O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T = 304 O_E. 306 In applications, it is also necessary that for any S in G_1 and T in 307 G_2, this bilinear map is efficiently computable. 309 We define some of the terminology used in this memo as follows: 311 GF(p): a finite field with characteristic p. 313 GF(p^k): an extension field of degree k. 315 (GF(p))*: a multiplicative group of GF(p). 317 (GF(p^k))*: a multiplicative group of GF(p^k). 319 b: a primitive element of the multiplicative group (GF(p))^*. 321 O_E: the point at infinity over an elliptic curve E. 323 E(GF(p^k)): the group of GF(p^k)-rational points of E. 325 #E(GF(p^k)): the number of GF(p^k)-rational points of E. 327 r: the order of G_1 and G_2. 329 BP: a point in G_1. (The 'base point' of a cyclic subgroup of G_1) 331 h: the cofactor h = #E(GF(p)) / r, where gcd(h, r)=1. 333 2.3. Barreto-Naehrig Curves 335 A BN curve [BN05] is a family of pairing-friendly curves proposed in 336 2005. A pairing over BN curves constructs optimal Ate pairings. 338 A BN curve is defined by elliptic curves E and E' parameterized by a 339 well-chosen integer t. E is defined over GF(p), where p is a prime 340 number and at least 5, and E(GF(p)) has a subgroup of prime order r. 341 The characteristic p and the order r are parameterized by 343 p = 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1 344 r = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1 346 for an integer t. 348 The elliptic curve E has an equation of the form E: y^2 = x^3 + b, 349 where b is a primitive element of the multiplicative group (GF(p))^* 350 of order (p - 1). 352 In the case of BN curves, we can use twists of the degree 6. If m is 353 an element that is neither a square nor a cube in an extension field 354 GF(p^2), the twist E' of E is defined over an extension field GF(p^2) 355 by the equation E': y^2 = x^3 + b' with b' = b / m or b' = b * m. BN 356 curves are called D-type if b' = b / m, and M-type if b' = b * m. 357 The embedding degree k is 12. 359 A pairing e is defined by taking G_1 as a subgroup of E(GF(p)) of 360 order r, G_2 as a subgroup of E'(GF(p^2)), and G_T as a subgroup of a 361 multiplicative group (GF(p^12))^* of order r. 363 2.4. Barreto-Lynn-Scott Curves 365 A BLS curve [BLS02] is a another family of pairing-frinedly curves 366 proposed in 2002. Similar to BN curves, a pairing over BLS curves 367 constructs optimal Ate pairings. 369 A BLS curve is defined by elliptic curves E and E' parameterized by a 370 well-chosen integer t. E is defined over a finite field GF(p) by an 371 equation of the form E: y^2 = x^3 + b, and its twist E': y^2 = x^3 + 372 b', is defined in the same way as BN curves. In contrast to BN 373 curves, E(GF(p)) does not have a prime order. Instead, its order is 374 divisible by a large parameterized prime r and denoted by h * r with 375 cofactor h. The pairing is defined on the r-torsion points. In the 376 same way as BN curves, BLS curves can be categorized as D-type and 377 M-type. 379 BLS curves vary in accordance with different embedding degrees. In 380 this memo, we deal with the BLS12 and BLS48 families with embedding 381 degrees 12 and 48 with respect to r, respectively. 383 In BLS curves, parameters p and r are given by the following 384 equations: 386 BLS12: 387 p = (t - 1)^2 * (t^4 - t^2 + 1) / 3 + t 388 r = t^4 - t^2 + 1 389 BLS48: 390 p = (t - 1)^2 * (t^16 - t^8 + 1) / 3 + t 391 r = t^16 - t^8 + 1 393 for a well chosen integer t where t must be 1 (mod 3). 395 A pairing e is defined by taking G_1 as a subgroup of E(GF(p)) of 396 order r, G_2 as an order r subgroup of E'(GF(p^2)) for BLS12 and of 397 E'(GF(p^8)) for BLS48, and G_T as an order r subgroup of a 398 multiplicative group (GF(p^12))^* for BLS12 and of a multiplicative 399 group (GF(p^48))^* for BLS48. 401 2.5. Representation Convention for an Extension Field 403 Pairing-friendly curves use a tower of some extension fields. In 404 order to encode an element of an extension field, focusing on 405 interoperability, we adopt the representation convention shown in 406 Appendix J.4 of [I-D.ietf-lwig-curve-representations] as a standard 407 and effective method. Note that the big-endian encoding is used for 408 an element in GF(p) which follows to mcl [mcl], ISO/IEC 15946-5 409 [ISOIEC15946-5] and etc. 411 Let GF(p) be a finite field of characteristic p and GF(p^d) = 412 GF(p)(i) be an extension field of GF(p) of degree d. 414 For an element s in GF(p^d) such that s = s_0 + s_1 * i + ... + s_{d 415 - 1} * i^{d - 1} where s_0, s_1, ... , s_{d - 1} in the basefield 416 GF(p), s is represented as octet string by oct(s) = s_0 || s_1 || 417 ... || s_{d - 1}. 419 Let GF(p^d') = GF(p^d)(j) be an extension field of GF(p^d) of degree 420 d' / d. 422 For an element s' in GF(p^d') such that s' = s'_0 + s'_1 * j + ... + 423 s'_{d' / d - 1} * j^{d' / d - 1} where s'_0, s'_1, ..., s'_{d' / d - 424 1} in the basefield GF(p^d), s' is represented as integer by oct(s') 425 = oct(s'_0) || oct(s'_1) || ... || oct(s'_{d' / d - 1}), where 426 oct(s'_0), ... , oct(s'_{d' / d - 1}) are octet strings encoded by 427 above convention. 429 In general, one can define encoding between integer and an element of 430 any finite field tower by inductively applying the above convention. 432 The parameters and test vectors of extension fields described in this 433 memo are encoded by this convention and represented in an octet 434 stream. 436 When applications communicate elements in an extension field, using 437 the compression method [MP04] may be more effective. In that case, 438 care for interoperability must be taken. 440 3. Security of Pairing-Friendly Curves 442 3.1. Evaluating the Security of Pairing-Friendly Curves 444 The security of pairing-friendly curves is evaluated by the hardness 445 of the following discrete logarithm problems: 447 * The elliptic curve discrete logarithm problem (ECDLP) in G_1 and 448 G_2 450 * The finite field discrete logarithm problem (FFDLP) in G_T 452 There are other hard problems over pairing-friendly curves used for 453 proving the security of pairing-based cryptography. Such problems 454 include the computational bilinear Diffie-Hellman (CBDH) problem, the 455 bilinear Diffie-Hellman (BDH) problem, the decision bilinear Diffie- 456 Hellman (DBDH) problem, the gap DBDH problem, etc. [ECRYPT]. Almost 457 all of these variants are reduced to the hardness of discrete 458 logarithm problems described above and are believed to be easier than 459 the discrete logarithm problems. 461 Although it would be sufficient to attack any of these problems to 462 attack pairing-based crytography, the only known attacks thus far 463 attack the discrete logarithm problem directly, so we focus on the 464 discrete logarithm in this memo. 466 The security levels of pairing-friendly curves are estimated by the 467 computational cost of the most efficient algorithm for solving the 468 above discrete logarithm problems. The best-known algorithms for 469 solving the discrete logarithm problems are based on Pollard's rho 470 algorithm [Pollard78] and Index Calculus [HR83]. To make index 471 calculus algorithms more efficient, number field sieve (NFS) 472 algorithms are utilized. 474 3.2. Impact of Recent Attacks 476 In 2016, Kim and Barbulescu proposed a new variant of the NFS 477 algorithms, the extended tower number field sieve (exTNFS), which 478 drastically reduces the complexity of solving FFDLP [KB16]. The 479 exTNFS improves the polynomial selection that is the first step in 480 the number field sieve algorithm for discrete logarithms in GF(p^k). 481 The idea is applicable when the embedding degree k is a composite 482 that satisfies k = i * j (gcd (i, j) = 1, i, j> 1). Since the above 483 condition is satisfied especially when k = 2^n*3^m (n, m> 1), BN 484 curves and BLS curves whose embedding degree is divisible by 6 are 485 affected by the exTNFS. The basic idea of the exTNFS is based on the 486 equality GF(p^k) = (GF(p^i)^j) and one of the improvement for 487 reducing the amount of cost for solving FFDLP is using sub-field 488 calculation. Please refer to [KB16] for detailed ideas and 489 calculation algorithms of exTNFS. Due to exTNFS, the security levels 490 of certain pairing-friendly curves asymptotically dropped down. For 491 instance, Barbulescu and Duquesne estimated that the security of the 492 BN curves, which had been believed to provide 128-bit security 493 (BN256, for example) was reduced to approximately 100 bits [BD18]. 494 Here, the security levels described in this memo correspond to the 495 security strength of NIST recommendation [NIST]. 497 There has since been research into the minimum bit length of the 498 parameters of pairing-friendly curves for each security level when 499 applying exTNFS as an attacking method for FFDLP. For 128-bit 500 security, Barbulescu and Duquesne estimated the minimum bit length of 501 p of BN curves and BLS12 curves after exTNFS as 461 bits [BD18]. For 502 256-bit security, Kiyomura et al. estimated the minimum bit length of 503 p^k of BLS48 curves as 27,410 bits, which indicated 572 bits of p 504 [KIK17]. 506 4. Selection of Pairing-Friendly Curves 508 In this section, we introduce some of the known secure pairing- 509 friendly curves that consider the impact of exTNFS. 511 First, we show the adoption status of pairing-friendly curves in 512 standards, libraries and applications, and classify them in 513 accordance with the 128-bit, 192-bit, and 256-bit security levels. 514 Then, from the viewpoints of "security" and "widely used", pairing- 515 friendly curves corresponding to each security level are selected and 516 their parameters are indicated. 518 In our selection policy, it is important that selected curves are 519 shown in peer-reviewed papers for security and that they are widely 520 used in cryptographic libraries. In addition, "efficiency" is one of 521 the important aspects but greatly dependant on implementations, so we 522 choose to prioritize "security" and "widely used" over "efficiency" 523 in consideration of future interconnections and interoperability over 524 the internet. 526 As a result, we recommend the BLS curve with 381-bit characteristic 527 of embedding degree 12 and the BN curve with the 462-bit 528 characteristic for the 128-bit security level, and the BLS curves of 529 embedding degree 48 with the 581-bit characteristic for the 256-bit 530 security level. On the other hand, we do not show the parameters for 531 192-bit security here because there are no curves that match our 532 selection policy. 534 4.1. Adoption Status of Pairing-friendly Curves 536 We show the pairing-friendly curves that have been selected by 537 existing standards, cryptographic libraries, and applications. 539 Table 1 summarizes the adoption status of pairing-friendly curves. 540 In this table, "Arnd" is an abbreviation for "Around". The curves 541 categorized as 'Arnd 128-bit', 'Arnd 192-bit' and 'Arnd 256-bit' for 542 each label show that their security levels are within the range of 543 plus/minus 5 bits for each security level. Other labels shown with 544 '~' mean that the security level of the categorized curve is outside 545 the range of each security level. Specifically, the security level 546 of the categorized curves is more than the previous column and is 547 less than the next column. The details are described as the 548 following subsections. A BN curve with a XXX-bit characteristic p is 549 denoted as BNXXX and a BLS curve of embedding degree k with a XXX-bit 550 p is denoted as BLSk_XXX. 552 Table 1 omits parameters with security levels below the "Arnd 553 128-bit" range due to space limitations and viewpoints of secure 554 usage of parameters. On the other hand, indicating which standards, 555 libraries, and applications use these lower security level parameters 556 would be useful information for implementers, therefore Appendix D 557 shows these parameters. In addition, the full version of Table 1 is 558 available at https://lepidum.co.jp/blog/2020-03-27/ietf-draft-pfc/. 560 In Table 1, the security level for each curve is evaluated in 561 accordance with [BD18],[GMT19], [MAF19] and [FK18]. Note that the 562 Freeman curves and MNT curves are not included in this table because 563 [BD18] does not show the security levels of these curves. 565 +=============+============+===========+============================+ 566 | Category | Name | Curve Type| Securi | 567 | | | | ty | 568 | | | | Levels | 569 | | | | (bit) | 570 | | | +======+===+======+===+======+ 571 | | | | Arnd | ~ | Arnd | ~ | Arnd | 572 | | | | 128 | | 192 | | 256 | 573 +=============+============+===========+------+---+------+---+------+ 574 | Standard |ISO/IEC |BN384 | X | | | | | 575 | | +-----------+------+---+------+---+------+ 576 | | |BN512I | | X | | | | 577 | +------------+-----------+------+---+------+---+------+ 578 | |TCG |BN638 | | X | | | | 579 | +------------+-----------+------+---+------+---+------+ 580 | |FIDO/W3C |BN512I | | X | | | | 581 | | +-----------+------+---+------+---+------+ 582 | | |BN638 | | X | | | | 583 +-------------+------------+-----------+------+---+------+---+------+ 584 | Library |mcl |BLS12_381 | X | | | | | 585 | | +-----------+------+---+------+---+------+ 586 | | |BN382M | X | | | | | 587 | | +-----------+------+---+------+---+------+ 588 | | |BN462 | X | | | | | 589 | +------------+-----------+------+---+------+---+------+ 590 | |RELIC |BLS12_381 | X | | | | | 591 | | +-----------+------+---+------+---+------+ 592 | | |BLS12_446 | X | | | | | 593 | | +-----------+------+---+------+---+------+ 594 | | |BLS12_455 | X | | | | | 595 | | +-----------+------+---+------+---+------+ 596 | | |BLS12_638 | | X | | | | 597 | | +-----------+------+---+------+---+------+ 598 | | |BLS24_477 | | | X | | | 599 | | +-----------+------+---+------+---+------+ 600 | | |BLS48_575 | | | | | X | 601 | | +-----------+------+---+------+---+------+ 602 | | |BN382R | X | | | | | 603 | | +-----------+------+---+------+---+------+ 604 | | |BN446 | X | | | | | 605 | | +-----------+------+---+------+---+------+ 606 | | |BN638 | | X | | | | 607 | | +-----------+------+---+------+---+------+ 608 | | |CP8_544 | X | | | | | 609 | | +-----------+------+---+------+---+------+ 610 | | |K54_569 | | | | | X | 611 | | +-----------+------+---+------+---+------+ 612 | | |KSS18_508 | | X | | | | 613 | | +-----------+------+---+------+---+------+ 614 | | |OT8_511 | X | | | | | 615 | +------------+-----------+------+---+------+---+------+ 616 | |AMCL |BLS12_381 | X | | | | | 617 | | +-----------+------+---+------+---+------+ 618 | | |BLS12_383 | X | | | | | 619 | | +-----------+------+---+------+---+------+ 620 | | |BLS12_461 | X | | | | | 621 | | +-----------+------+---+------+---+------+ 622 | | |BLS24_479 | | | X | | | 623 | | +-----------+------+---+------+---+------+ 624 | | |BLS48_556 | | | | | X | 625 | | +-----------+------+---+------+---+------+ 626 | | |BN512I | | X | | | | 627 | +------------+-----------+------+---+------+---+------+ 628 | |Kyushu Univ.|BLS48_581 | | | | | X | 629 | +------------+-----------+------+---+------+---+------+ 630 | |MIRACL |BLS12_381 | X | | | | | 631 | | +-----------+------+---+------+---+------+ 632 | | |BLS12_383 | X | | | | | 633 | | +-----------+------+---+------+---+------+ 634 | | |BLS12_461 | X | | | | | 635 | | +-----------+------+---+------+---+------+ 636 | | |BLS24_479 | | | X | | | 637 | | +-----------+------+---+------+---+------+ 638 | | |BLS48_556 | | | | | X | 639 | | +-----------+------+---+------+---+------+ 640 | | |BLS48_581 | | | | | X | 641 | | +-----------+------+---+------+---+------+ 642 | | |BN462 | X | | | | | 643 | | +-----------+------+---+------+---+------+ 644 | | |BN512I | | X | | | | 645 | +------------+-----------+------+---+------+---+------+ 646 | |Adjoint |BLS12_381 | X | | | | | 647 | | +-----------+------+---+------+---+------+ 648 | | |BN462 | X | | | | | 649 | +------------+-----------+------+---+------+---+------+ 650 | |bls12377js |BLS12_377 | X | | | | | 651 +-------------+------------+-----------+------+---+------+---+------+ 652 | Application |Zcash |BLS12_381 | X | | | | | 653 | +------------+-----------+------+---+------+---+------+ 654 | |Ethereum |BLS12_381 | X | | | | | 655 | +------------+-----------+------+---+------+---+------+ 656 | |Chia Network|BLS12_381 | X | | | | | 657 | +------------+-----------+------+---+------+---+------+ 658 | |DFINITY |BLS12_381 | X | | | | | 659 | | +-----------+------+---+------+---+------+ 660 | | |BN382M | X | | | | | 661 | | +-----------+------+---+------+---+------+ 662 | | |BN462 | X | | | | | 663 | +------------+-----------+------+---+------+---+------+ 664 | |Algorand |BLS12_381 | X | | | | | 665 +-------------+------------+-----------+------+---+------+---+------+ 667 Table 1: Adoption Status of Pairing-Friendly Curves 669 4.1.1. International Standards 671 ISO/IEC 15946 series specifies public-key cryptographic techniques 672 based on elliptic curves. ISO/IEC 15946-5 [ISOIEC15946-5] shows 673 numerical examples of MNT curves[MNT01] with 160-bit p and 256-bit p, 674 Freeman curves [Freeman06] with 224-bit p and 256-bit p, and BN 675 curves with 160-bit p, 192-bit p, 224-bit p, 256-bit p, 384-bit p, 676 and 512-bit p. These parameters do not take into account the effects 677 of the exTNFS. On the other hand, the parameters may be revised in 678 future versions since ISO/IEC 15946-5 is currently under development. 679 As described below, BN curves with 256-bit p and 512-bit p specified 680 in ISO/IEC 15946-5 used by other standards and libraries, these 681 curves are especially denoted as BN256I and BN512I. The suffix 'I' 682 of BN256I and BN512I are given from the initials of the standard name 683 ISO. 685 TCG adopts the BN256I and a BN curve with 638-bit p specified by 686 their own[TPM]. FIDO Alliance [FIDO] and W3C [W3C] adopt BN256I, 687 BN512I, the BN638 by TCG, and the BN curve with 256-bit p proposed by 688 Devegili et al.[DSD07] (named BN256D). The suffix 'D' of BN256D is 689 given from the initials of the first author's name of the paper which 690 proposed the parameter. 692 4.1.2. Cryptographic Libraries 694 There are a lot of cryptographic libraries that support pairing 695 calculations. 697 PBC is a library for pairing-based cryptography published by Stanford 698 University that supports BN curves, MNT curves, Freeman curves, and 699 supersingular curves [PBC]. Users can generate pairing parameters by 700 using PBC and use pairing operations with the generated parameters. 702 mcl[mcl] is a library for pairing-based cryptography that supports 703 four BN curves and BLS12_381 [GMT19]. These BN curves include BN254 704 proposed by Nogami et al. [NASKM08] (named BN254N), BN_SNARK1 705 suitable for SNARK applications[libsnark], BN382M, and BN462. The 706 suffix 'N' of BN256N and the suffix 'M' of BN382M are respectively 707 given from the initials of the first author's name of the proposed 708 paper and the library's name mcl. Kyushu University published a 709 library that supports the BLS48_581 [BLS48]. The University of 710 Tsukuba Elliptic Curve and Pairing Library (TEPLA) [TEPLA] supports 711 two BN curves, BN254N and BN254 proposed by Beuchat et al. 712 [BGMORT10] (named BN254B). The suffix 'B' of BN254B is given from 713 the initials of the first author's name of the proposed paper. Intel 714 published a cryptographic library named Intel Integrated Performance 715 Primitives (Intel-IPP) [Intel-IPP] and the library supports BN256I. 717 RELIC [RELIC] uses various types of pairing-friendly curves including 718 six BN curves (BN158, BN254R, BN256R, BN382R, BN446, and BN638), 719 where BN254R, BN256R, and BN382R are RELIC specific parameters that 720 are different from BN254N, BN254B, BN256I, BN256D, and BN382M. The 721 suffix 'R' of BN382R is given from the initials of the library's name 722 RELIC. In addition, RELIC supports six BLS curves (BLS12_381, 723 BLS12_446, BLS12_445, BLS12_638, BLS24_477, and BLS48_575 [MAF19]), 724 Cocks-Pinch curves of embedding degree 8 with 544-bit p[GMT19], 725 pairing-friendly curves constructed by Scott et al. [SG19] based on 726 Kachisa-Scott-Schaefer curves with embedding degree 54 with 569-bit p 727 (named K54_569)[MAF19], a KSS curve [KSS08] of embedding degree 18 728 with 508-bit p (named KSS18_508) [AFKMR12], Optimal TNFS-secure curve 729 [FM19] of embedding degree 8 with 511-bit p(OT8_511), and a 730 supersingular curve [S86] with 1536-bit p (SS_1536). 732 Apache Milagro Crypto Library (AMCL)[AMCL] supports four BLS curves 733 (BLS12_381, BLS12_461, BLS24_479 and BLS48_556) and four BN curves 734 (BN254N, BN254CX proposed by CertiVox, BN256I, and BN512I). In 735 addition to AMCL's supported curves, MIRACL [MIRACL] supports BN462 736 and BLS48_581. 738 Adjoint published a library that supports the BLS12_381 and six BN 739 curves (BN_SNARK1, BN254B, BN254N, BN254S1, BN254S2, and BN462) 740 [AdjointLib], where BN254S1 and BN254S2 are BN curves adopted by an 741 old version of AMCL [AMCLv2]. The suffix 'S' of BN254S1 and BN254S2 742 are given from the initials of developper's name because he proposed 743 these parameters. 745 The Celo foundation published the bls12377js library [bls12377js]. 746 The supported curve is the BLS12_377 curve which is shown in 747 [BCGMMW20]. 749 4.1.3. Applications 751 Zcash uses a BN curve (named BN128) in their library libsnark 752 [libsnark]. In response to the exTNFS attacks, they proposed new 753 parameters using BLS12_381 [BLS12_381] [GMT19]and published its 754 experimental implementation [zkcrypto]. 756 Ethereum 2.0 adopted BLS12_381 and uses the implementation by Meyer 757 [pureGo-bls]. Chia Network published their implementation [Chia] by 758 integrating the RELIC toolkit [RELIC]. DFINITY uses mcl, and 759 Algorand published an implementation which supports BLS12_381. 761 4.2. For 128-bit Security 763 Table 1 shows a lot of cases of adopting BN and BLS curves. Among 764 them, BLS12_381 and BN462 match our selection policy. Especially, 765 the one that best matches the policy is BLS12_381 from the viewpoint 766 of "widely used" and "efficiency", so we introduce the parameters of 767 BLS12_381 in this memo. 769 On the other hand, from the viewpoint of the future use, the 770 parameter of BN462 is also introduced. As shown in recent security 771 evaluations for BLS12_381[BD18] [GMT19], its security level close to 772 128-bit but it is less than 128-bit. If the attack is improved even 773 a little, BLS12_381 will not be suitable for the curve of the 128-bit 774 security level. As curves of 128-bit security level are currently 775 the most widely used, we recommend both BLS12_381 and BN462 in this 776 memo in order to have a more efficient and a more prudent option 777 respectively. 779 4.2.1. BLS Curves for the 128-bit security level (BLS12_381) 781 In this part, we introduce the parameters of the Barreto-Lynn-Scott 782 curve of embedding degree 12 with 381-bit p that is adopted by a lot 783 of applications such as Zcash [Zcash], Ethereum [Ethereum], and so 784 on. 786 The BLS12_381 curve is shown in [BLS12_381] and it is defined by the 787 parameter 789 t = -2^63 - 2^62 - 2^60 - 2^57 - 2^48 - 2^16 791 where the size of p becomes 381-bit length. 793 For the finite field GF(p), the towers of extension field GF(p^2), 794 GF(p^6) and GF(p^12) are defined by indeterminates u, v, and w as 795 follows: 797 GF(p^2) = GF(p)[u] / (u^2 + 1) 798 GF(p^6) = GF(p^2)[v] / (v^3 - u - 1) 799 GF(p^12) = GF(p^6)[w] / (w^2 - v). 801 Defined by t, the elliptic curve E and its twist E' are represented 802 by E: y^2 = x^3 + 4 and E': y^2 = x^3 + 4(u + 1). BLS12_381 is 803 categorized as M-type. 805 We have to note that the security level of this pairing is expected 806 to be 126 rather than 128 bits [GMT19]. 808 Parameters of BLS12_381 are given as follows. 810 * G_1 is the largest prime-order subgroup of E(GF(p)) 812 - BP = (x,y) : a 'base point', i.e., a generator of G_1 814 * G_2 is an r-order subgroup of E'(GF(p^2)) 816 - BP' = (x',y') : a 'base point', i.e., a generator of G_2 817 (encoded with [I-D.ietf-lwig-curve-representations]) 819 o x' = x'_0 + x'_1 * u (x'_0, x'_1 in GF(p)) 821 o y' = y'_0 + y'_1 * u (y'_0, y'_1 in GF(p)) 823 - h' : the cofactor #E'(GF(p^2))/r 825 p: 826 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f624 827 1eabfffeb153ffffb9feffffffffaaab 829 r: 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff0000000 830 1 832 x: 833 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac58 834 6c55e83ff97a1aeffb3af00adb22c6bb 836 y: 837 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3ed 838 d03cc744a2888ae40caa232946c5e7e1 840 h: 0x396c8c005555e1568c00aaab0000aaab 841 b: 4 843 x'_0: 844 0x024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3d177 845 0bac0326a805bbefd48056c8c121bdb8 847 x'_1: 848 0x13e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049 849 334cf11213945d57e5ac7d055d042b7e 851 y'_0: 852 0x0ce5d527727d6e118cc9cdc6da2e351aadfd9baa8cbdd3a76d429a695160d12c 853 923ac9cc3baca289e193548608b82801 855 y'_1: 856 0x0606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af267492ab572e99ab 857 3f370d275cec1da1aaa9075ff05f79be 859 h': 860 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa 861 628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5 863 b': 4 * (u + 1) 865 As mentioned above, BLS12_381 is adopted in a lot of applications. 866 Since it is expected that BLS12_381 will continue to be widely used 867 more and more in the future, Appendix C shows the serialization 868 format of points on an elliptic curve as useful information. This 869 serialization format is also adopted in [I-D.boneh-bls-signature] 870 [zkcrypto]. 872 In addition, many pairing-based cryptographic applications use a 873 hashing to an elliptic curve procedure that outputs a rational point 874 on an elliptic curve from an arbitrary input. A standard 875 specification of ciphersuites for a hashing to an elliptic curve, 876 including BLS12_381, is under discussion in the IETF 877 [I-D.irtf-cfrg-hash-to-curve] and it will be valuable information for 878 implementers. 880 4.2.2. BN Curves for the 128-bit security level (BN462) 882 A BN curve with the 128-bit security level is shown in [BD18], which 883 we call BN462. BN462 is defined by the parameter 885 t = 2^114 + 2^101 - 2^14 - 1 887 for the definition in Section 2.3. 889 For the finite field GF(p), the towers of extension field GF(p^2), 890 GF(p^6) and GF(p^12) are defined by indeterminates u, v, and w as 891 follows: 893 GF(p^2) = GF(p)[u] / (u^2 + 1) 894 GF(p^6) = GF(p^2)[v] / (v^3 - u - 2) 895 GF(p^12) = GF(p^6)[w] / (w^2 - v). 897 Defined by t, the elliptic curve E and its twist E' are represented 898 by E: y^2 = x^3 + 5 and E': y^2 = x^3 - u + 2, respectively. The 899 size of p becomes 462-bit length. BN462 is categorized as D-type. 901 We have to note that BN462 is significantly slower than BLS12_381, 902 but has 134-bit security level [GMT19], so may be more resistant to 903 future small improvements to the exTNFS attack. 905 We note also that CP8_544 is about 20% faster that BN462 [GMT19], has 906 131-bit security level, and that due to its construction will not be 907 affected by future small improvements to the exTNFS attack. However, 908 as this curve is not widely used (it is only implemented in one 909 library), we instead chose BN462 for our 'safe' option. 911 We give the following parameters for BN462. 913 * G_1 is the largest prime-order subgroup of E(GF(p)) 915 - BP = (x,y) : a 'base point', i.e., a generator of G_1 917 * G_2 is an r-order subgroup of E'(GF(p^2)) 919 - BP' = (x',y') : a 'base point', i.e., a generator of G_2 920 (encoded with [I-D.ietf-lwig-curve-representations]) 922 o x' = x'_0 + x'_1 * u (x'_0, x'_1 in GF(p)) 924 o y' = y'_0 + y'_1 * u (y'_0, y'_1 in GF(p)) 926 - h' : the cofactor #E'(GF(p^2))/r 928 p: 929 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908f41c802 930 0ffffffffff6ff66fc6ff687f640000000002401b00840138013 932 r: 933 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908ee1c201 934 f7fffffffff6ff66fc7bf717f7c0000000002401b007e010800d 936 x: 937 0x21a6d67ef250191fadba34a0a30160b9ac9264b6f95f63b3edbec3cf4b2e689d 938 b1bbb4e69a416a0b1e79239c0372e5cd70113c98d91f36b6980d 940 y: 941 0x0118ea0460f7f7abb82b33676a7432a490eeda842cccfa7d788c659650426e6a 942 f77df11b8ae40eb80f475432c66600622ecaa8a5734d36fb03de 944 h: 1 946 b: 5 948 x'_0: 949 0x0257ccc85b58dda0dfb38e3a8cbdc5482e0337e7c1cd96ed61c913820408208f 950 9ad2699bad92e0032ae1f0aa6a8b48807695468e3d934ae1e4df 952 x'_1: 953 0x1d2e4343e8599102af8edca849566ba3c98e2a354730cbed9176884058b18134 954 dd86bae555b783718f50af8b59bf7e850e9b73108ba6aa8cd283 956 y'_0: 957 0x0a0650439da22c1979517427a20809eca035634706e23c3fa7a6bb42fe810f13 958 99a1f41c9ddae32e03695a140e7b11d7c3376e5b68df0db7154e 960 y'_1: 961 0x073ef0cbd438cbe0172c8ae37306324d44d5e6b0c69ac57b393f1ab370fd725c 962 c647692444a04ef87387aa68d53743493b9eba14cc552ca2a93a 964 h': 965 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908fa1ce02 966 27fffffffff6ff66fc63f5f7f4c0000000002401b008a0168019 968 b': -u + 2 970 4.3. For 256-bit Security 972 As shown in Table 1, there are three candidates of pairing-friendly 973 curves for 256-bit security. According to our selection policy, we 974 select BLS48_581, as it is the most widely adopted by cryptographic 975 libraries. 977 The selected BLS48 curve is shown in [KIK17] and it is defined by the 978 parameter 980 t = -1 + 2^7 - 2^10 - 2^30 - 2^32. 982 In this case, the size of p becomes 581-bit. 984 For the finite field GF(p), the towers of extension field GF(p^2), 985 GF(p^4), GF(p^8), GF(p^24) and GF(p^48) are defined by indeterminates 986 u, v, w, z, and s as follows: 988 GF(p^2) = GF(p)[u] / (u^2 + 1) 989 GF(p^4) = GF(p^2)[v] / (v^2 + u + 1) 990 GF(p^8) = GF(p^4)[w] / (w^2 + v) 991 GF(p^24) = GF(p^8)[z] / (z^3 + w) 992 GF(p^48)= GF(p^24)[s] / (s^2 + z). 994 The elliptic curve E and its twist E' are represented by E: y^2 = x^3 995 + 1 and E': y^2 = x^3 - 1 / w. BLS48_581 is categorized as D-type. 997 We then give the parameters for BLS48_581 as follows. 999 * G_1 is the largest prime-order subgroup of E(GF(p)) 1001 - BP = (x,y) : a 'base point', i.e., a generator of G_1 1003 * G_2 is an r-order subgroup of E'(GF(p^8)) 1005 - BP' = (x',y') : a 'base point', i.e., a generator of G_2 1006 (encoded with [I-D.ietf-lwig-curve-representations]) 1008 o x' = x'_0 + x'_1 * u + x'_2 * v + x'_3 * u * v + x'_4 * w + 1009 x'_5 * u * w + x'_6 * v * w + x'_7 * u * v * w (x'_0, ..., 1010 x'_7 in GF(p)) 1012 o y' = y'_0 + y'_1 * u + y'_2 * v + y'_3 * u * v + y'_4 * w + 1013 y'_5 * u * w + y'_6 * v * w + y'_7 * u * v * w (y'_0, ..., 1014 y'_7 in GF(p)) 1016 - h' : the cofactor #E'(GF(p^8))/r 1018 p: 1019 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444 1020 a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac 1021 3edc154e6565912b 1023 r: 1024 0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6 1025 e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c01 1027 x: 1028 0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7 1029 544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d8c 1030 3bce8732315af640 1032 y: 1033 0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279dd41b720e 1034 f7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f37aef7b926b57 1035 6dbb5de3e2587a70 1037 x'_0: 1038 0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156 1039 c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154de 1040 c34fd0b4ace8bfab 1042 x'_1: 1043 0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e 1044 1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa143f 1045 1669b36676b47c57 1047 x'_2: 1048 0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccbab5ab 1049 6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3f0b4 1050 6488156ca55a3e6a 1052 x'_3: 1053 0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f8be0 1054 cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80bc3f 1055 09a7033cbb7feafe 1057 x'_4: 1058 0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386 1059 699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb 1060 739c3a1c53f8cce5 1062 x'_5: 1063 0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb03741 1064 8181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce3370 1065 f2004d914a3c093a 1067 x'_6: 1068 0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0b7a4 1069 49cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c3354 1070 e41607e60750e057 1072 x'_7: 1073 0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7 1074 f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3f8 1075 4e19da00fbc6ae34 1077 y'_0: 1078 0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc435fa 1079 ab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c0ff3 1080 23edd3fe4d2d7971 1082 y'_1: 1083 0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d72964732fcb 1084 f3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ffc7b1 1085 11471db936cd5665 1087 y'_2: 1088 0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d370514 1089 475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b8fde 1090 68332a526a2a8474 1092 y'_3: 1093 0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e122d2 1094 742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e53373 1095 16213da92841589d 1097 y'_4: 1098 0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f112985 1099 7ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf7a43 1100 f47831f982e50137 1102 y'_5: 1103 0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055ab750 1104 4fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226cf3a5 1105 94eedc58cf90bee4 1107 y'_6: 1108 0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c819a6 1109 df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9aa62b 1110 3d41faeafeb23986 1112 y'_7: 1113 0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8eca9a 1114 9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e84069c55 1115 d667ffcb732718b6 1117 h: 0x85555841aaaec4ac 1119 b: 1 1121 h': 1122 0x170e915cb0a6b7406b8d94042317f811d6bc3fc6e211ada42e58ccfcb3ac076a 1123 7e4499d700a0c23dc4b0c078f92def8c87b7fe63e1eea270db353a4ef4d38b5998 1124 ad8f0d042ea24c8f02be1c0c83992fe5d7725227bb27123a949e0876c0a8ce0a67 1125 326db0e955dcb791b867f31d6bfa62fbdd5f44a00504df04e186fae033f1eb43c1 1126 b1a08b6e086eff03c8fee9ebdd1e191a8a4b0466c90b389987de5637d5dd13dab3 1127 3196bd2e5afa6cd19cf0fc3fc7db7ece1f3fac742626b1b02fcee04043b2ea9649 1128 2f6afa51739597c54bb78aa6b0b99319fef9d09f768831018ee6564c68d054c62f 1129 2e0b4549426fec24ab26957a669dba2a2b6945ce40c9aec6afdeda16c79e15546c 1130 d7771fa544d5364236690ea06832679562a68731420ae52d0d35a90b8d10b688e3 1131 1b6aee45f45b7a5083c71732105852decc888f64839a4de33b99521f0984a418d2 1132 0fc7b0609530e454f0696fa2a8075ac01cc8ae3869e8d0fe1f3788ffac4c01aa27 1133 20e431da333c83d9663bfb1fb7a1a7b90528482c6be7892299030bb51a51dc7e91 1134 e9156874416bf4c26f1ea7ec578058563960ef92bbbb8632d3a1b695f954af10e9 1135 a78e40acffc13b06540aae9da5287fc4429485d44e6289d8c0d6a3eb2ece350124 1136 52751839fb48bc14b515478e2ff412d930ac20307561f3a5c998e6bcbfebd97eff 1137 c6433033a2361bfcdc4fc74ad379a16c6dea49c209b1 1139 b': -1 / w 1141 5. Security Considerations 1143 The recommended pairing-friendly curves are selected by considering 1144 the exTNFS proposed by Kim et al. in 2016 [KB16] and they are 1145 categorized in each security level in accordance with [BD18]. 1146 Implementers who will newly develop pairing-based cryptography 1147 applications SHOULD use the recommended parameters. As of 2020, as 1148 far as we've investigated the top cryptographic conferences in the 1149 past, there are no fatal attacks that significantly reduce the 1150 security of pairing-friendly curves after exTNFS. 1152 BLS curves of embedding degree 12 typically require a characteristic 1153 p of 461 bits or larger to achieve the 128-bit security level [BD18]. 1154 Note that the security level of BLS12_381, which is adopted by a lot 1155 of libraries and applications, is slightly below 128 bits because a 1156 381-bit characteristic is used [BD18] [GMT19]. 1158 BN254 is used in most of the existing implementations as shown in 1159 Section 4.1 ( and Appendix D), however, BN curves that were estimated 1160 as the 128-bit security level before exTNFS including BN254 ensure no 1161 more than the 100-bit security level by the effect of exTNFS. 1163 In addition, implementors should be aware of the following points 1164 when they implement pairing-based cryptographic applications using 1165 recommended curves. Regarding the use case and applications of 1166 pairing-based cryptographic applications, please refer Section 1.2. 1168 In applications such as key agreement protocols, users exchange the 1169 elements in G_1 and G_2 as public keys. To check these elements are 1170 so-called sub-group secure [BCM15], implementors should validate if 1171 the elements have the correct order r. Specifically, for public keys 1172 P in G_1 and Q in G_2, a receiver should calculate scalar 1173 multiplications [r]P and [r]Q, and check the results become points at 1174 infinity. 1176 The pairing-based protocols, such as the BLS signatures, use a scalar 1177 multiplication in G_1, G_2 and an exponentiation in G_3 with the 1178 secret key. In order to prevent the leakage of secret key due to 1179 side channel attacks, implementors should apply countermeasure 1180 techniques such as montgomery ladder [Montgomery] [CF06] when they 1181 implement modules of a scalar multiplication and an exponentiation. 1182 Please refer [Montgomery] and [CF06] for the detailed algorithms of 1183 montgomery ladder. 1185 When converting between an element in extension field and an octet 1186 string, implementors should check that the coefficient is within an 1187 appropriate range [IEEE1363]. If the coefficient is out of range, 1188 there is a possible that security vulnerabilities such as the 1189 signature forgery may occur. 1191 Recommended parameters are affected by the Cheon's attack which is a 1192 solving algorithm for the strong DH problem [Cheon06]. The 1193 mathematical problem that provides the security of the strong DH 1194 problem is called ECDLP with Auxiliary Inputs (ECDLPwAI). In 1195 ECDLPwAI, given rational points P, [K]P, [K^i]P, for i=1,...,n, then 1196 we find a secret K. Since the complexity of ECDLPwAI is given as 1197 O(sqrt((r-1)/n + sqrt(n)) where n|r-1 by using Cheon's algorithm 1198 whereas the complexity of ECDLP is given as O(sqrt(r)), the 1199 complexity of ECDLPwAI with the ideal value n becomes dramatically 1200 smaller than that of ECDLP. Please refer [Cheon06] for the details 1201 of Cheon's algorithm. Therefore, implementers should be careful when 1202 they design cryptographic protocols based on the strong DH problem. 1203 For example, in the case of Short Signatures, they can prevent the 1204 Cheon's attack by carefully setting the maximum number of queries 1205 which corresponds to the parameter n. 1207 6. IANA Considerations 1209 This document has no actions for IANA. 1211 7. Acknowledgements 1213 The authors would like to appreciate a lot of authors including 1214 Akihiro Kato for their significant contribution to early versions of 1215 this memo. The authors would also like to acknowledge Kim Taechan, 1216 Hoeteck Wee, Sergey Gorbunov, Michael Scott, Chloe Martindale as an 1217 Expert Reviewer, Watson Ladd, Armando Faz, Rene Struik, and Satoru 1218 Kanno for their valuable comments. 1220 8. References 1222 8.1. Normative References 1224 [BD18] Barbulescu, R. and S. Duquesne, "Updating Key Size 1225 Estimations for Pairings", DOI 10.1007/s00145-018-9280-5, 1226 Journal of Cryptology, January 2018, 1227 . 1229 [BLS02] Barreto, P., Lynn, B., and M. Scott, "Constructing 1230 Elliptic Curves with Prescribed Embedding Degrees", 1231 DOI 10.1007/3-540-36413-7_19, Security in Communication 1232 Networks pp. 257-267, 2003, 1233 . 1235 [BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic 1236 Curves of Prime Order", DOI 10.1007/11693383_22, Selected 1237 Areas in Cryptography pp. 319-331, 2006, 1238 . 1240 [GMT19] Guillevic, A., Masson, S., and E. Thome, "Cocks–Pinch 1241 curves of embedding degrees five to eight and optimal ate 1242 pairing computation", DOI 10.1007/s10623-020-00727-w, 1243 International Journal of Designs, Codes and 1244 Cryptography vol. 88, pp. 1047-1081, 2019, 1245 . 1247 [KB16] Kim, T. and R. Barbulescu, "Extended Tower Number Field 1248 Sieve: A New Complexity for the Medium Prime Case", 1249 DOI 10.1007/978-3-662-53018-4_20, Advances in Cryptology - 1250 CRYPTO 2016 pp. 543-571, 2016, 1251 . 1253 [KIK17] Kiyomura, Y., Inoue, A., Kawahara, Y., Yasuda, M., Takagi, 1254 T., and T. Kobayashi, "Secure and Efficient Pairing at 1255 256-Bit Security Level", DOI 10.1007/978-3-319-61204-1_4, 1256 Applied Cryptography and Network Security pp. 59-79, 2017, 1257 . 1259 [NIST] Barker, E., "NIST special publication 800-57 part 1 1260 (revised) : Recommendation for key management, part 1: 1261 General (revised)", National Institute of Standards and 1262 Technology (NIST), 2020. 1264 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1265 Requirement Levels", BCP 14, RFC 2119, 1266 DOI 10.17487/RFC2119, March 1997, 1267 . 1269 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 1270 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 1271 May 2017, . 1273 [Ver09] Vercauteren, F., "Optimal Pairings", 1274 DOI 10.1109/tit.2009.2034881, IEEE Transactions on 1275 Information Theory Vol. 56, pp. 455-461, January 2010, 1276 . 1278 8.2. Informative References 1280 [AdjointLib] 1281 Adjoint Inc., "Optimised bilinear pairings over elliptic 1282 curves", 2018, . 1284 [AFKMR12] Aranha, D.F., Fuentes-Castaneda, L., Knapp, E., Menezes, 1285 A., and F. Rodríguez-Henríquez, "Implementing Pairings at 1286 the 192-Bit Security Level", 1287 DOI /10.1007/978-3-642-36334-4_11, Pairing 2012 pp. 1288 177-195, 2012, 1289 . 1291 [Algorand] Gorbunov, S., "Efficient and Secure Digital Signatures for 1292 Proof-of-Stake Blockchains", . 1295 [AMCL] The Apache Software Foundation, "The Apache Milagro 1296 Cryptographic Library (AMCL)", 2016, 1297 . 1299 [AMCLv2] The Apache Software Foundation, "Old version of the Apache 1300 Milagro Cryptographic Library", 2016, 1301 . 1303 [BCGMMW20] Bowe, S., Chiesa, A., Green, M., Miers, I., Mishra, P., 1304 and H. Wu, "ZEXE: Enabling Decentralized Private 1305 Computation", DOI 10.1109/SP40000.2020.00050, IEEE 1306 Symposium on Security and Privacy 2020, 2020, 1307 . 1309 [BCM15] Barreto, P. S. L. M., Costello, C., Misoczki, R., Naehrig, 1310 M., Pereira, G. C. C. F., and G. Zanon, "Subgroup security 1311 in pairing-based cryptography", Cryptology ePrint 1312 Archive Report 2015/247, 2015, 1313 . 1315 [BGMORT10] Beuchat, J., González-Díaz, J., Mitsunari, S., Okamoto, 1316 E., Rodríguez-Henríquez, F., and T. Teruya, "High-Speed 1317 Software Implementation of the Optimal Ate Pairing over 1318 Barreto–Naehrig Curves", DOI 10.1007/978-3-642-17455-1_2, 1319 Pairing 2010 pp. 21-39, 2010, 1320 . 1322 [BL10] Brickell, E. and J. Li, "Enhanced Privacy ID from Bilinear 1323 Pairing for Hardware Authentication and Attestation", 1324 DOI 10.1109/socialcom.2010.118, 2010 IEEE Second 1325 International Conference on Social Computing, August 2010, 1326 . 1328 [bls12377js] 1329 The Celo Foundation, "bls12377js", 2019, 1330 . 1332 [BLS12_381] 1333 Bowe, S., "BLS12-381: New zk-SNARK Elliptic Curve 1334 Construction", 1335 . 1337 [BLS48] Kyushu University, "bls48 - C++ library for Optimal Ate 1338 Pairing on BLS48", 2017, 1339 . 1341 [CCS07] Chen, L., Cheng, Z., and N. Smart, "Identity-based key 1342 agreement protocols from pairings", 1343 DOI 10.1007/s10207-006-0011-9, International Journal of 1344 Information Security Vol. 6, pp. 213-241, January 2007, 1345 . 1347 [CF06] Cohen, H. and G. Frey, "Handbook of Elliptic and 1348 Hyperelliptic Curve Cryptography", 1349 DOI 10.1201/9780367801625, Chapman and Hall CRC, 2006, 1350 . 1352 [Cheon06] Cheon, J. H., "Security Analysis of the Strong Diffie- 1353 Hellman Problem", DOI 10.1007/11761679_1, EUROCRYPT 1354 2006 pp. 1-11, 2006, . 1356 [Chia] Chia Network, "BLS signatures in C++, using the relic 1357 toolkit", 1358 . 1360 [CIRCL] Cloudflare, "CIRCL: Cloudflare Interoperable, Reusable 1361 Cryptographic Library", 2019, 1362 . 1364 [CLN09] Costello, C., Lange, T., and M. Naehrig, "Faster Pairing 1365 Computations on Curves with High-Degree Twists", 1366 Cryptology ePrint Archive Report 2009/615, 2009, 1367 . 1369 [Cloudflare] 1370 Sullivan, N., "Geo Key Manager: How It Works", 1371 . 1374 [DFINITY] Williams, D., "DFINITY Technology Overview Series 1375 Consensus System Rev. 1", n.d., . 1378 [DSD07] Devegili, A. J., Scott, M., and R. Dahab, "Implementing 1379 Cryptographic Pairings over Barreto-Naehrig Curves", 1380 DOI 10.1007/978-3-540-73489-5_10, Pairing 2007 pp. 1381 197-207, 2007, 1382 . 1384 [ECRYPT] ECRYPT, "Final Report on Main Computational Assumptions in 1385 Cryptography". 1387 [EPID] Intel Corporation, "Intel (R) SGX: Intel (R) EPID 1388 Provisioning and Attestation Services", 1389 . 1392 [Ethereum] Jordan, R., "Ethereum 2.0 Development Update #17 - 1393 Prysmatic Labs", . 1397 [FIDO] Lindemann, R., "FIDO ECDAA Algorithm - FIDO Alliance 1398 Review Draft 02", . 1402 [FK18] Fotiadis, G. and E. Konstantinou, "TNFS Resistant Families 1403 of Pairing-Friendly Elliptic Curves", Cryptology ePrint 1404 Archive Report 2018/1017, 2018, 1405 . 1407 [FM19] Fotiadis, G. and C. Martindale, "Optimal TNFS-secure 1408 pairings on elliptic curves with composite embedding 1409 degree", Cryptology ePrint Archive Report 2019/555, 2019, 1410 . 1412 [Freeman06] 1413 Freeman, D., "Constructing pairing-friendly elliptic 1414 curves with embedding degree 10", DOI 10.1007/11792086_32, 1415 ANTS 2006 pp. 452-465, 2006, 1416 . 1418 [FSU10] Fujioka, A., Suzuki, K., and B. Ustaoglu, "Ephemeral Key 1419 Leakage Resilient and Efficient ID-AKEs That Can Share 1420 Identities, Private and Master Keys", 1421 DOI 10.1007/978-3-642-17455-1_12, Lecture Notes in 1422 Computer Science pp. 187-205, 2010, 1423 . 1425 [HR83] Hellman, M. and J. Reyneri, "Fast Computation of Discrete 1426 Logarithms in GF (q)", DOI 10.1007/978-1-4757-0602-4_1, 1427 Advances in Cryptology pp. 3-13, 1983, 1428 . 1430 [I-D.boneh-bls-signature] 1431 Boneh, D., Gorbunov, S., Wee, H., and Z. Zhang, "BLS 1432 Signature Scheme", Work in Progress, Internet-Draft, 1433 draft-boneh-bls-signature-00, 8 February 2019, 1434 . 1437 [I-D.ietf-lwig-curve-representations] 1438 Struik, R., "Alternative Elliptic Curve Representations", 1439 Work in Progress, Internet-Draft, draft-ietf-lwig-curve- 1440 representations-08, 24 July 2019, 1441 . 1444 [I-D.irtf-cfrg-hash-to-curve] 1445 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1446 C. Wood, "Hashing to Elliptic Curves", Work in Progress, 1447 Internet-Draft, draft-irtf-cfrg-hash-to-curve-09, 29 June 1448 2020, . 1451 [IEEE1363] "IEEE Standard Specifications for Public-Key 1452 Cryptography", IEEE standard, 1453 DOI 10.1109/IEEESTD.2000.92292, 2000, 1454 . 1456 [Intel-IPP] 1457 Intel Corporation, "Developer Reference for Intel 1458 Integrated Performance Primitives Cryptography 2019", 1459 2018, . 1463 [ISOIEC11770-3] 1464 ISO/IEC, "ISO/IEC 11770-3:2015", ISO/IEC Information 1465 technology -- Security techniques -- Key management -- 1466 Part 3: Mechanisms using asymmetric techniques, 2015. 1468 [ISOIEC15946-5] 1469 ISO/IEC, "ISO/IEC 15946-5:2017", ISO/IEC Information 1470 technology -- Security techniques -- Cryptographic 1471 techniques based on elliptic curves -- Part 5: Elliptic 1472 curve generation, 2017. 1474 [Joux00] Joux, A., "A One Round Protocol for Tripartite Diffie- 1475 Hellman", DOI 10.1007/10722028_23, Lecture Notes in 1476 Computer Science pp. 385-393, 2000, 1477 . 1479 [KSS08] Kachisa, E., Schaefer, E., and M. Scott, "Constructing 1480 Brezing-Weng Pairing-Friendly Elliptic Curves Using 1481 Elements in the Cyclotomic Field", 1482 DOI 10.1007/978-3-540-85538-5_9, Pairing 2008 pp. 126-135, 1483 2008, . 1485 [libsnark] SCIPR Lab, "libsnark: a C++ library for zkSNARK proofs", 1486 2012, . 1488 [M-Pin] Scott, M., "M-Pin: A Multi-Factor Zero Knowledge 1489 Authentication Protocol", July 2019, 1490 . 1493 [MAF19] Mbiang, N.B., Aranha, D.F., and E. Fouotsa, "Computing the 1494 Optimal Ate Pairing over Elliptic Curves with Embedding 1495 Degrees 54 and 48 at the 256-bit security level", 1496 International Journal of Applied Cryptography to appear, 1497 2019, . 1502 [mcl] Mitsunari, S., "mcl - A portable and fast pairing-based 1503 cryptography library", 2016, 1504 . 1506 [MIRACL] MIRACL Ltd., "The MIRACL Core Cryptographic Library", 1507 2019, . 1509 [MNT01] Miyaji, A., Nakabayashi, M., and S. Takano, "New explicit 1510 conditions of Elliptic Curve Traces under FR reduction", 1511 IEICE Trans. Fundamentals. E84-A(5) pp. 1234-1243, 2001. 1513 [Montgomery] 1514 Montgomery, P., "Speeding the Pollard and Elliptic Curve 1515 Methods of Factorization", MATHEMATICS OF COMPUTATION , 1516 January, 1987, . 1520 [MP04] Guillevic, A., Masson, S., and E. Thome, "Cocks–Pinch 1521 curves of embedding degrees five to eight and optimal ate 1522 pairing computation", Cryptology ePrint Archive Report 1523 2019/431, 2019, . 1525 [NASKM08] Nogami, Y., Akane, M., Sakemi, Y., Kato, H., and Y. 1526 Morikawa, "Integer Variable X-Based Ate Pairing", 1527 DOI 10.1007/978-3-540-85538-5_13, Pairing 2008 pp. 1528 178-191, 2008, 1529 . 1531 [PBC] Lynn, B., "PBC Library - The Pairing-Based Cryptography 1532 Library", 2006, . 1534 [Pollard78] 1535 Pollard, J., "Monte Carlo methods for index computation 1536 $({\rm mod}\ p)$", DOI 10.1090/s0025-5718-1978-0491431-9, 1537 Mathematics of Computation Vol. 32, pp. 918-918, September 1538 1978, . 1540 [pureGo-bls] 1541 Meyer, J., "Pure GO bls library", 2019, 1542 . 1544 [RELIC] Gouvea, C.P.L., "RELIC is an Efficient LIbrary for 1545 Cryptography", 2013, 1546 . 1548 [RFC5091] Boyen, X. and L. Martin, "Identity-Based Cryptography 1549 Standard (IBCS) #1: Supersingular Curve Implementations of 1550 the BF and BB1 Cryptosystems", RFC 5091, 1551 DOI 10.17487/RFC5091, December 2007, 1552 . 1554 [RFC6508] Groves, M., "Sakai-Kasahara Key Encryption (SAKKE)", 1555 RFC 6508, DOI 10.17487/RFC6508, February 2012, 1556 . 1558 [RFC6509] Groves, M., "MIKEY-SAKKE: Sakai-Kasahara Key Encryption in 1559 Multimedia Internet KEYing (MIKEY)", RFC 6509, 1560 DOI 10.17487/RFC6509, February 2012, 1561 . 1563 [RFC6539] Cakulev, V., Sundaram, G., and I. Broustis, "IBAKE: 1564 Identity-Based Authenticated Key Exchange", RFC 6539, 1565 DOI 10.17487/RFC6539, March 2012, 1566 . 1568 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1569 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1570 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1571 . 1573 [S86] Silverman, J. H., "The arithmetic of elliptic curves", 1574 Springer GTM 106, 1986. 1576 [SAKKE] 3GPP, "Security of the mission critical service (Release 1577 15)", 3GPP TS 33.180 15.3.0, 2018. 1579 [SEC1] Standards for Efficient Cryptography Group (SECG), "SEC 1: 1580 Elliptic Curve Cryptography", 2009, 1581 . 1583 [SG19] Scott, M. and A. Guillevic, "A New Family of Pairing- 1584 Friendly elliptic curves", Cryptology ePrint 1585 Archive Report 2019/193, 2019, 1586 . 1588 [TEPLA] University of Tsukuba, "TEPLA: University of Tsukuba 1589 Elliptic Curve and Pairing Library", 2013, 1590 . 1592 [TPM] Trusted Computing Group (TCG), "Trusted Platform Module 1593 Library Specification, Family \"2.0\", Level 00, Revision 1594 01.38", . 1597 [W3C] Lundberg, E., "Web Authentication: An API for accessing 1598 Public Key Credentials Level 1 - W3C Recommendation", 1599 . 1601 [Zcash] Lindemann, R., "What are zk-SNARKs?", 1602 . 1604 [ZCashRep] Electric Coin Company, "BLS12-381", July 2017, 1605 . 1608 [zkcrypto] zkcrypto, "zkcrypto - Pairing-friendly elliptic curve 1609 library", 2017, . 1611 Appendix A. Computing the Optimal Ate Pairing 1613 Before presenting the computation of the optimal Ate pairing e(P, Q) 1614 satisfying the properties shown in Section 2.2, we give the 1615 subfunctions used for the pairing computation. 1617 The following algorithm, Line_Function shows the computation of the 1618 line function. It takes Q_1 = (x_1, x_2), Q_2 = (x_2, y_2) in G_2, 1619 and P = (x, y) in G_1 as input, and outputs an element of G_T. 1621 if (Q_1 = Q_2) then 1622 l := (3 * x_1^2) / (2 * y_1); 1623 else if (Q_1 = -Q_2) then 1624 return x - x_1; 1625 else 1626 l := (y_2 - y_1) / (x_2 - x_1); 1627 end if; 1628 return (l * (x - x_1) + y_1 - y); 1630 When implementing the line function, implementers should consider the 1631 isomorphism of E and its twist curve E' so that one can reduce the 1632 computational cost of operations in G_2 [CLN09][KIK17]. We note that 1633 Line_function does not consider such an isomorphism. 1635 The computation of the optimal Ate pairing uses the Frobenius 1636 endomorphism. The p-power Frobenius endomorphism pi for a point Q = 1637 (x, y) over E' is pi(p, Q) = (x^p, y^p). 1639 A.1. Optimal Ate Pairings over Barreto-Naehrig Curves 1641 Let c = 6 * t + 2 for a parameter t and c_0, c_1, ... , c_L in 1642 {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., L) equals c. 1644 The following algorithm shows the computation of the optimal Ate 1645 pairing on BN curves. It takes P in G_1, Q in G_2, an integer c, 1646 c_0, ...,c_L in {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, 1647 ..., L) equals c, and the order r of G_1 as input, and outputs e(P, 1648 Q). 1650 f := 1; T := Q; 1651 if (c_L = -1) then 1652 T := -T; 1653 end if 1654 for i = L-1 downto 0 1655 f := f^2 * Line_function(T, T, P); T := T + T; 1656 if (c_i = 1) then 1657 f := f * Line_function(T, Q, P); T := T + Q; 1658 else if (c_i = -1) then 1659 f := f * Line_function(T, -Q, P); T := T - Q; 1660 end if 1661 end for 1662 Q_1 := pi(p, Q); Q_2 := pi(p, Q_1); 1663 f := f * Line_function(T, Q_1, P); T := T + Q_1; 1664 f := f * Line_function(T, -Q_2, P); 1665 f := f^{(p^k - 1) / r} 1666 return f; 1668 A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves 1670 Let c = t for a parameter t and c_0, c_1, ... , c_L in {-1,0,1} such 1671 that the sum of c_i * 2^i (i = 0, 1, ..., L) equals c. 1673 The following algorithm shows the computation of the optimal Ate 1674 pairing on Barreto-Lynn-Scott curves. It takes P in G_1, Q in G_2, 1675 an integer c, c_0, ...,c_L in {-1,0,1} such that the sum of c_i * 2^i 1676 (i = 0, 1, ..., L) equals c, and the order r of G_1 as input, and 1677 outputs e(P, Q). 1679 f := 1; T := Q; 1680 if (c_L = -1) then 1681 T := -T; 1682 end if 1683 for i = L-1 downto 0 1684 f := f^2 * Line_function(T, T, P); T := T + T; 1685 if (c_i = 1) then 1686 f := f * Line_function(T, Q, P); T := T + Q; 1687 else if (c_i = -1) then 1688 f := f * Line_function(T, -Q, P); T := T - Q; 1689 end if 1690 end for 1691 f := f^{(p^k - 1) / r}; 1692 return f; 1694 Appendix B. Test Vectors of Optimal Ate Pairing 1696 We provide test vectors for Optimal Ate Pairing e(P, Q) given in 1697 Appendix A for the curves BLS12_381, BN462 and BLS48_581 given in 1698 Section 4. Here, the inputs P = (x, y) and Q = (x', y') are the 1699 corresponding base points BP and BP' given in Section 4. 1701 For BLS12_381 and BN462, Q = (x', y') is given by 1703 x' = x'_0 + x'_1 * u and 1704 y' = y'_0 + y'_1 * u, 1706 where u is an indeterminate and x'_0, x'_1, y'_0, y'_1 are elements 1707 of GF(p). 1709 For BLS48_581, Q = (x', y') is given by 1711 x' = x'_0 + x'_1 * u + x'_2 * v + x'_3 * u * v 1712 + x'_4 * w + x'_5 * u * w + x'_6 * v * w + x'_7 * u * v * w and 1713 y' = y'_0 + y'_1 * u + y'_2 * v + y'_3 * u * v 1714 + y'_4 * w + y'_5 * u * w + y'_6 * v * w + y'_7 * u * v * w, 1716 where u, v and w are indeterminates and x'_0, ..., x'_7 and y'_0, 1717 ..., y'_7 are elements of GF(p). The representation of Q = (x', y') 1718 given below is followed by [I-D.ietf-lwig-curve-representations]. 1720 In addition, we use the notation e_i (i = 0, ..., k-1) to represent 1721 each element in e(P, Q), where the extension field that e(P, Q) 1722 belongs is constructed according to 1723 [I-D.ietf-lwig-curve-representations]. 1725 BLS12_381: 1727 Input x value: 1728 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac58 1729 6c55e83ff97a1aeffb3af00adb22c6bb 1731 Input y value: 1732 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3ed 1733 d03cc744a2888ae40caa232946c5e7e1 1735 Input x'_0 value: 1736 0x024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3d177 1737 0bac0326a805bbefd48056c8c121bdb8 1739 Input x'_1 value: 1740 0x13e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049 1741 334cf11213945d57e5ac7d055d042b7e 1743 Input y'_0 value: 1744 0x0ce5d527727d6e118cc9cdc6da2e351aadfd9baa8cbdd3a76d429a695160d12c 1745 923ac9cc3baca289e193548608b82801 1747 Input y'_1 value: 1748 0x0606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af267492ab572e99ab 1749 3f370d275cec1da1aaa9075ff05f79be 1751 e_0: 1752 0x11619b45f61edfe3b47a15fac19442526ff489dcda25e59121d9931438907dfd 1753 448299a87dde3a649bdba96e84d54558 1755 e_1: 1756 0x153ce14a76a53e205ba8f275ef1137c56a566f638b52d34ba3bf3bf22f277d70 1757 f76316218c0dfd583a394b8448d2be7f 1759 e_2: 1760 0x095668fb4a02fe930ed44767834c915b283b1c6ca98c047bd4c272e9ac3f3ba6 1761 ff0b05a93e59c71fba77bce995f04692 1763 e_3: 1764 0x16deedaa683124fe7260085184d88f7d036b86f53bb5b7f1fc5e248814782065 1765 413e7d958d17960109ea006b2afdeb5f 1767 e_4: 1768 0x09c92cf02f3cd3d2f9d34bc44eee0dd50314ed44ca5d30ce6a9ec0539be7a86b 1769 121edc61839ccc908c4bdde256cd6048 1771 e_5: 1772 0x111061f398efc2a97ff825b04d21089e24fd8b93a47e41e60eae7e9b2a38d54f 1773 a4dedced0811c34ce528781ab9e929c7 1775 e_6: 1776 0x01ecfcf31c86257ab00b4709c33f1c9c4e007659dd5ffc4a735192167ce19705 1777 8cfb4c94225e7f1b6c26ad9ba68f63bc 1779 e_7: 1780 0x08890726743a1f94a8193a166800b7787744a8ad8e2f9365db76863e894b7a11 1781 d83f90d873567e9d645ccf725b32d26f 1783 e_8: 1784 0x0e61c752414ca5dfd258e9606bac08daec29b3e2c57062669556954fb227d3f1 1785 260eedf25446a086b0844bcd43646c10 1787 e_9: 1788 0x0fe63f185f56dd29150fc498bbeea78969e7e783043620db33f75a05a0a2ce5c 1789 442beaff9da195ff15164c00ab66bdde 1791 e_10: 1792 0x10900338a92ed0b47af211636f7cfdec717b7ee43900eee9b5fc24f0000c5874 1793 d4801372db478987691c566a8c474978 1795 e_11: 1796 0x1454814f3085f0e6602247671bc408bbce2007201536818c901dbd4d2095dd86 1797 c1ec8b888e59611f60a301af7776be3d 1799 BN462: 1801 Input x value: 1802 0x21a6d67ef250191fadba34a0a30160b9ac9264b6f95f63b3edbec3cf4b2e689d 1803 b1bbb4e69a416a0b1e79239c0372e5cd70113c98d91f36b6980d 1805 Input y value: 1806 0x0118ea0460f7f7abb82b33676a7432a490eeda842cccfa7d788c659650426e6a 1807 f77df11b8ae40eb80f475432c66600622ecaa8a5734d36fb03de 1809 Input x'_0 value: 1810 0x0257ccc85b58dda0dfb38e3a8cbdc5482e0337e7c1cd96ed61c913820408208f 1811 9ad2699bad92e0032ae1f0aa6a8b48807695468e3d934ae1e4df 1813 Input x'_1 value: 1814 0x1d2e4343e8599102af8edca849566ba3c98e2a354730cbed9176884058b18134 1815 dd86bae555b783718f50af8b59bf7e850e9b73108ba6aa8cd283 1817 Input y'_0 value: 1818 0x0a0650439da22c1979517427a20809eca035634706e23c3fa7a6bb42fe810f13 1819 99a1f41c9ddae32e03695a140e7b11d7c3376e5b68df0db7154e 1821 Input y'_1 value: 1822 0x073ef0cbd438cbe0172c8ae37306324d44d5e6b0c69ac57b393f1ab370fd725c 1823 c647692444a04ef87387aa68d53743493b9eba14cc552ca2a93a 1825 e_0: 1826 0x0cf7f0f2e01610804272f4a7a24014ac085543d787c8f8bf07059f93f87ba7e2 1827 a4ac77835d4ff10e78669be39cd23cc3a659c093dbe3b9647e8c 1829 e_1: 1830 0x00ef2c737515694ee5b85051e39970f24e27ca278847c7cfa709b0df408b830b 1831 3763b1b001f1194445b62d6c093fb6f77e43e369edefb1200389 1833 e_2: 1834 0x04d685b29fd2b8faedacd36873f24a06158742bb2328740f93827934592d6f17 1835 23e0772bb9ccd3025f88dc457fc4f77dfef76104ff43cd430bf7 1837 e_3: 1838 0x090067ef2892de0c48ee49cbe4ff1f835286c700c8d191574cb424019de11142 1839 b3c722cc5083a71912411c4a1f61c00d1e8f14f545348eb7462c 1841 e_4: 1842 0x1437603b60dce235a090c43f5147d9c03bd63081c8bb1ffa7d8a2c31d6732308 1843 60bb3dfe4ca85581f7459204ef755f63cba1fbd6a4436f10ba0e 1845 e_5: 1846 0x13191b1110d13650bf8e76b356fe776eb9d7a03fe33f82e3fe5732071f305d20 1847 1843238cc96fd0e892bc61701e1844faa8e33446f87c6e29e75f 1849 e_6: 1850 0x07b1ce375c0191c786bb184cc9c08a6ae5a569dd7586f75d6d2de2b2f075787e 1851 e5082d44ca4b8009b3285ecae5fa521e23be76e6a08f17fa5cc8 1853 e_7: 1854 0x05b64add5e49574b124a02d85f508c8d2d37993ae4c370a9cda89a100cdb5e1d 1855 441b57768dbc68429ffae243c0c57fe5ab0a3ee4c6f2d9d34714 1857 e_8: 1858 0x0fd9a3271854a2b4542b42c55916e1faf7a8b87a7d10907179ac7073f6a1de04 1859 4906ffaf4760d11c8f92df3e50251e39ce92c700a12e77d0adf3 1861 e_9: 1862 0x17fa0c7fa60c9a6d4d8bb9897991efd087899edc776f33743db921a689720c82 1863 257ee3c788e8160c112f18e841a3dd9a79a6f8782f771d542ee5 1865 e_10: 1866 0x0c901397a62bb185a8f9cf336e28cfb0f354e2313f99c538cdceedf8b8aa22c2 1867 3b896201170fc915690f79f6ba75581f1b76055cd89b7182041c 1869 e_11: 1870 0x20f27fde93cee94ca4bf9ded1b1378c1b0d80439eeb1d0c8daef30db0037104a 1871 5e32a2ccc94fa1860a95e39a93ba51187b45f4c2c50c16482322 1873 BLS48_581: 1875 Input x value: 1876 0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7 1877 544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d8c 1878 3bce8732315af640 1880 Input y value: 1881 0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279dd41b720e 1882 f7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f37aef7b926b57 1883 6dbb5de3e2587a70 1885 x'_0: 1886 0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156 1887 c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154de 1888 c34fd0b4ace8bfab 1890 x'_1: 1891 0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e 1892 1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa143f 1893 1669b36676b47c57 1895 x'_2: 1896 0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccbab5ab 1897 6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3f0b4 1898 6488156ca55a3e6a 1900 x'_3: 1901 0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f8be0 1902 cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80bc3f 1903 09a7033cbb7feafe 1905 x'_4: 1906 0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386 1907 699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb 1908 739c3a1c53f8cce5 1910 x'_5: 1911 0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb03741 1912 8181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce3370 1913 f2004d914a3c093a 1915 x'_6: 1916 0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0b7a4 1917 49cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c3354 1918 e41607e60750e057 1920 x'_7: 1921 0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7 1922 f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3f8 1923 4e19da00fbc6ae34 1925 y'_0: 1926 0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc435fa 1927 ab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c0ff3 1928 23edd3fe4d2d7971 1930 y'_1: 1931 0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d72964732fcb 1932 f3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ffc7b1 1933 11471db936cd5665 1935 y'_2: 1936 0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d370514 1937 475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b8fde 1938 68332a526a2a8474 1940 y'_3: 1941 0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e122d2 1942 742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e53373 1943 16213da92841589d 1945 y'_4: 1946 0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f112985 1947 7ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf7a43 1948 f47831f982e50137 1950 y'_5: 1951 0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055ab750 1952 4fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226cf3a5 1953 94eedc58cf90bee4 1955 y'_6: 1956 0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c819a6 1957 df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9aa62b 1958 3d41faeafeb23986 1960 y'_7: 1961 0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8eca9a 1962 9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e84069c55 1963 d667ffcb732718b6 1965 e_0: 1966 0x0e26c3fcb8ef67417814098de5111ffcccc1d003d15b367bad07cef2291a93d3 1967 1db03e3f03376f3beae2bd877bcfc22a25dc51016eda1ab56ee3033bc4b4fec596 1968 2f02dffb3af5e38e 1970 e_1: 1971 0x069061b8047279aa5c2d25cdf676ddf34eddbc8ec2ec0f03614886fa828e1fc0 1972 66b26d35744c0c38271843aa4fb617b57fa9eb4bd256d17367914159fc18b10a10 1973 85cb626e5bedb145 1975 e_2: 1976 0x02b9bece645fbf9d8f97025a1545359f6fe3ffab3cd57094f862f7fb9ca01c88 1977 705c26675bcc723878e943da6b56ce25d063381fcd2a292e0e7501fe572744184f 1978 b4ab4ca071a04281 1980 e_3: 1981 0x0080d267bf036c1e61d7fc73905e8c630b97aa05ef3266c82e7a111072c0d205 1982 6baa8137fba111c9650dfb18cb1f43363041e202e3192fced29d2b0501c882543f 1983 b370a56bfdc2435b 1985 e_4: 1986 0x03c6b4c12f338f9401e6a493a405b33e64389338db8c5e592a8dd79eac7720dd 1987 83dd6b0c189eeda20809160cd57cdf3e2edc82db15f553c1f6c953ea27114cb6bd 1988 8a38e273f407dae0 1990 e_5: 1991 0x016e46224f28bfd8833f76ac29ee6e406a9da1bde55f5e82b3bd977897a9104f 1992 18b9ee41ea9af7d4183d895102950a12ce9975669db07924e1b432d9680f5ce7e5 1993 c67ed68f381eba45 1995 e_6: 1996 0x008ddce7a4a1b94be5df3ceea56bef0077dcdde86d579938a50933a47296d337 1997 b7629934128e2457e24142b0eeaa978fd8e70986d7dd51fccbbeb8a1933434fec4 1998 f5bc538de2646e90 2000 e_7: 2001 0x060ef6eae55728e40bd4628265218b24b38cdd434968c14bfefb87f0dcbfc76c 2002 c473ae2dc0cac6e69dfdf90951175178dc75b9cc08320fcde187aa58ea047a2ee0 2003 0b1968650eec2791 2005 e_8: 2006 0x0c3943636876fd4f9393414099a746f84b2633dfb7c36ba6512a0b48e66dcb2e 2007 409f1b9e150e36b0b4311165810a3c721525f0d43a021f090e6a27577b42c7a57b 2008 ed3327edb98ba8f8 2010 e_9: 2011 0x02d31eb8be0d923cac2a8eb6a07556c8951d849ec53c2848ee78c5eed40262eb 2012 21822527a8555b071f1cd080e049e5e7ebfe2541d5b42c1e414341694d6f16d287 2013 e4a8d28359c2d2f9 2015 e_10: 2016 0x07f19673c5580d6a10d09a032397c5d425c3a99ff1dd0abe5bec40a0d47a6b8d 2017 aabb22edb6b06dd8691950b8f23faefcdd80c45aa3817a840018965941f4247f9f 2018 97233a84f58b262e 2020 e_11: 2021 0x0d3fe01f0c114915c3bdf8089377780076c1685302279fd9ab12d07477aac03b 2022 69291652e9f179baa0a99c38aa8851c1d25ffdb4ded2c8fe8b30338c14428607d6 2023 d822610d41f51372 2025 e_12: 2026 0x0662eefd5fab9509aed968866b68cff3bc5d48ecc8ac6867c212a2d82cee5a68 2027 9a3c9c67f1d611adac7268dc8b06471c0598f7016ca3d1c01649dda4b43531cffc 2028 4eb41e691e27f2eb 2030 e_13: 2031 0x0aad8f4a8cfdca8de0985070304fe4f4d32f99b01d4ea50d9f7cd2abdc0aeea9 2032 9311a36ec6ed18208642cef9e09b96795b27c42a5a744a7b01a617a91d9fb7623d 2033 636640d61a6596ec 2035 e_14: 2036 0x0ffcf21d641fd9c6a641a749d80cab1bcad4b34ee97567d905ed9d5cfb74e9ae 2037 f19674e2eb6ce3dfb706aa814d4a228db4fcd707e571259435393a27cac68b59a1 2038 b690ae8cde7a94c3 2040 e_15: 2041 0x0cbe92a53151790cece4a86f91e9b31644a86fc4c954e5fa04e707beb69fc60a 2042 858fed8ebd53e4cfd51546d5c0732331071c358d721ee601bfd3847e0e904101c6 2043 2822dd2e4c7f8e5c 2045 e_16: 2046 0x0202db83b1ff33016679b6cfc8931deea6df1485c894dcd113bacf564411519a 2047 42026b5fda4e16262674dcb3f089cd7d552f8089a1fec93e3db6bca43788cdb06f 2048 c41baaa5c5098667 2050 e_17: 2051 0x070a617ed131b857f5b74b625c4ef70cc567f619defb5f2ab67534a1a8aa7297 2052 5fc4248ac8551ce02b68801703971a2cf1cb934c9c354cadd5cfc4575cde8dbde6 2053 122bd54826a9b3e9 2055 e_18: 2056 0x070e1ebce457c141417f88423127b7a7321424f64119d5089d883cb953283ee4 2057 e1f2e01ffa7b903fe7a94af4bb1acb02ca6a36678e41506879069cee11c9dcf6a0 2058 80b6a4a7c7f21dc9 2060 e_19: 2061 0x058a06be5a36c6148d8a1287ee7f0e725453fa1bb05cf77239f235b417127e37 2062 0cfa4f88e61a23ea16df3c45d29c203d04d09782b39e9b4037c0c4ac8e8653e7c5 2063 33ad752a640b233e 2065 e_20: 2066 0x0dfdfaaeb9349cf18d21b92ad68f8a7ecc509c35fcd4b8abeb93be7a204ac871 2067 f2195180206a2c340fccb69dbc30b9410ed0b122308a8fc75141f673ae5ec82b6a 2068 45fc2d664409c6b6 2070 e_21: 2071 0x0d06c8adfdd81275da2a0ce375b8df9199f3d359e8cf50064a3dc10a59241712 2072 4a3b705b05a7ffe78e20f935a08868ecf3fc5aba0ace7ce4497bb59085ca277c16 2073 b3d53dd7dae5c857 2075 e_22: 2076 0x0708effd28c4ae21b6969cb9bdd0c27f8a3e341798b6f6d4baf27be259b4a476 2077 88b50cb68a69a917a4a1faf56cec93f69ac416512c32e9d5e69bd8836b6c2ba9c6 2078 889d507ad571dbc4 2080 e_23: 2081 0x09da7c7aa48ce571f8ece74b98431b14ae6fb4a53ae979cd6b2e82320e8d25a0 2082 ece1ca1563aa5aa6926e7d608358af8399534f6b00788e95e37ef1b549f43a58ad 2083 250a71f0b2fdb2bf 2085 e_24: 2086 0x0a7150a14471994833d89f41daeaa999dfc24a9968d4e33d88ed9e9f07aa2432 2087 c53e486ba6e3b6e4f4b8d9c989010a375935c06e4b8d6c31239fad6a61e2647b84 2088 a0e3f76e57005ff7 2090 e_25: 2091 0x084696f31ff27889d4dccdc4967964a5387a5ae071ad391c5723c9034f16c255 2092 7915ada07ec68f18672b5b2107f785c15ddf9697046dc633b5a23cc0e442d28ef6 2093 eea9915d0638d4d8 2095 e_26: 2096 0x0398e76e3d2202f999ac0f73e0099fe4e0fe2de9d223e78fc65c56e209cdf48f 2097 0d1ad8f6093e924ce5f0c93437c11212b7841de26f9067065b1898f48006bcc6f2 2098 ab8fa8e0b93f4ba4 2100 e_27: 2101 0x06d683f556022368e7a633dc6fe319fd1d4fc0e07acff7c4d4177e83a911e733 2102 13e0ed980cd9197bd17ac45942a65d90e6cb9209ede7f36c10e009c9d337ee97c4 2103 068db40e34d0e361 2105 e_28: 2106 0x0d764075344b70818f91b13ee445fd8c1587d1c0664002180bbac9a396ad4a8d 2107 c1e695b0c4267df4a09081c1e5c256c53fd49a73ffc817e65217a44fc0b20ef5ee 2108 92b28d4bc3e38576 2110 e_29: 2111 0x0aa6a32fdc4423b1c6d43e5104159bcd8e03a676d055d4496f7b1bc8761164a2 2112 908a3ff0e4c4d1f4362015c14824927011e2909531b8d87ee0acd676e7221a1ca1 2113 c21a33e2cf87dc51 2115 e_30: 2116 0x1147719959ac8eeab3fc913539784f1f947df47066b6c0c1beafecdb5fa784c3 2117 be9de5ab282a678a2a0cbef8714141a6c8aaa76500819a896b46af20509953495e 2118 2a85eff58348b38d 2120 e_31: 2121 0x11a377bcebd3c12702bb34044f06f8870ca712fb5caa6d30c48ace96898fcbcd 2122 dbcf31f331c9e524684c02c90db7f30b9fc470d6e651a7e8b1f684383f3705d7a4 2123 7a1b4fe463d623c8 2125 e_32: 2126 0x0b8b4511f451ba2cc58dc28e56d5e1d0a8f557ecb242f4d994a627e07cf3fa44 2127 e6d83cb907deacf303d2f761810b5d943b46c4383e1435ec23fec196a70e339461 2128 73c78be3c75dfc83 2130 e_33: 2131 0x090962d632ee2a57ce4208052ce47a9f76ea0fdad724b7256bb07f3944e9639a 2132 981d3431087241e30ae9bf5e2ea32af323ce7ed195d383b749cb25bc09f678d385 2133 a49a0c09f6d9efca 2135 e_34: 2136 0x0931c7befc80acd185491c68af886fa8ee39c21ed3ebd743b9168ae3b298df48 2137 5bfdc75b94f0b21aecd8dca941dfc6d1566cc70dc648e6ccc73e4cbf2a1ac83c82 2138 94d447c66e74784d 2140 e_35: 2141 0x020ac007bf6c76ec827d53647058aca48896916269c6a2016b8c06f0130901c8 2142 975779f1672e581e2dfdbcf504e96ecf6801d0d39aad35cf79fbe7fe193c6c882c 2143 15bce593223f0c7c 2145 e_36: 2146 0x0c0aed0d890c3b0b673bf4981398dcbf0d15d36af6347a39599f3a2258418482 2147 8f78f91bbbbd08124a97672963ec313ff142c456ec1a2fc3909fd4429fd699d827 2148 d48777d3b0e0e699 2150 e_37: 2151 0x0ef7799241a1ba6baaa8740d5667a1ace50fb8e63accc3bc30dc07b11d78dc54 2152 5b68910c027489a0d842d1ba3ac406197881361a18b9fe337ff22d730fa44afabb 2153 9f801f759086c8e4 2155 e_38: 2156 0x016663c940d062f4057257c8f4fb9b35e82541717a34582dd7d55b41ebadf40d 2157 486ed74570043b2a3c4de29859fdeae9b6b456cb33bb401ecf38f9685646692300 2158 517e9b035d6665fc 2160 e_39: 2161 0x1184a79510edf25e3bd2dc793a5082fa0fed0d559fa14a5ce9ffca4c61f17196 2162 e1ffbb84326272e0d079368e9a735be1d05ec80c20dc6198b50a22a765defdc151 2163 d437335f1309aced 2165 e_40: 2166 0x120e47a747d942a593d202707c936dafa6fed489967dd94e48f317fd3c881b10 2167 41e3b6bbf9e8031d44e39c1ab5ae41e487eac9acd90e869129c38a8e6c97cf55d6 2168 666d22299951f91a 2170 e_41: 2171 0x026b6e374108ecb2fe8d557087f40ab7bac8c5af0644a655271765d57ad71742 2172 aa331326d871610a8c4c30ccf5d8adbeec23cdff20d9502a5005fce2593caf0682 2173 c82e4873b89d6d71 2175 e_42: 2176 0x041be63a2fa643e5a66faeb099a3440105c18dca58d51f74b3bf281da4e689b1 2177 3f365273a2ed397e7b1c26bdd4daade710c30350318b0ae9a9b16882c29fe31ca3 2178 b884c92916d6d07a 2180 e_43: 2181 0x124018a12f0f0af881e6765e9e81071acc56ebcddadcd107750bd8697440cc16 2182 f190a3595633bb8900e6829823866c5769f03a306f979a3e039e620d6d2f576793 2183 d36d840b168eeedd 2185 e_44: 2186 0x0d422de4a83449c535b4b9ece586754c941548f15d50ada6740865be9c0b0667 2187 88b6078727c7dee299acc15cbdcc7d51cdc5b17757c07d9a9146b01d2fdc7b8c56 2188 2002da0f9084bde5 2190 e_45: 2191 0x1119f6c5468bce2ec2b450858dc073fea4fb05b6e83dd20c55c9cf694cbcc57f 2192 c0effb1d33b9b5587852d0961c40ff114b7493361e4cfdff16e85fbce667869b6f 2193 7e9eb804bcec46db 2195 e_46: 2196 0x061eaa8e9b0085364a61ea4f69c3516b6bf9f79f8c79d053e646ea637215cf65 2197 90203b275290872e3d7b258102dd0c0a4a310af3958165f2078ff9dc3ac9e995ce 2198 5413268d80974784 2200 e_47: 2201 0x0add8d58e9ec0c9393eb8c4bc0b08174a6b421e15040ef558da58d241e5f906a 2202 d6ca2aa5de361421708a6b8ff6736efbac6b4688bf752259b4650595aa395c40d0 2203 0f4417f180779985 2205 Appendix C. ZCash serialization format for BLS12_381 2207 This section describes the serialization format defined by 2208 [ZCashRep]. It is not officially standardized by the standards 2209 organization, however we show it in this appendix as a useful 2210 reference for implementers. This format applies to points on the 2211 BLS12_381 elliptic curves E and E', whose parameters are given in 2212 Section 4.2.1. Note that this serialization method is based on the 2213 representation shown in [SEC1] and it is a tiny tweak so as to apply 2214 to GF(p^m). 2216 At a high level, the serialization format is defined as follows: 2218 * Serialized points include three metadata bits that indicate 2219 whether a point is compressed or not, whether a point is the point 2220 at infinity or not, and (for compressed points) the sign of the 2221 point's y-coordinate. 2223 * Points on E are serialized into 48 bytes (compressed) or 96 bytes 2224 (uncompressed). Points on E' are serialized into 96 bytes 2225 (compressed) or 192 bytes (uncompressed). 2227 * The serialization of a point at infinity comprises a string of 2228 zero bytes, except that the metadata bits may be nonzero. 2230 * The serialization of a compressed point other than the point at 2231 infinity comprises a serialized x-coordinate. 2233 * The serialization of an uncompressed point other than the point at 2234 infinity comprises a serialized x-coordinate followed by a 2235 serialized y-coordinate. 2237 Below, we give detailed serialization and de-serialization 2238 procedures. The following notation is used in the rest of this 2239 section: 2241 * Elements of GF(p^2) are represented as polynomial with GF(p) 2242 coefficients like Section 2.5. 2244 * For a byte string str, str[0] is defined as the first byte of str. 2246 * The function sign_GF_p(y) returns one bit representing the sign of 2247 an element of GF(p). This function is defined as follows: 2249 sign_GF_p(y) := { 1 if y > (p - 1) / 2, else 2250 { 0 otherwise. 2252 * The function sign_GF_p^2(y') returns one bit representing the sign 2253 of an element in GF(p^2). This function is defined as follows: 2255 sign_GF_p^2(y') := { sign_GF_p(y'_0) if y'_1 equals 0, else 2256 { 1 if y'_1 > (p - 1) / 2, else 2257 { 0 otherwise. 2259 C.1. Point Serialization Procedure 2261 The serialization procedure is defined as follows for a point P = (x, 2262 y). This procedure uses the I2OSP function defined in [RFC8017]. 2264 1. Compute the metadata bits C_bit, I_bit, and S_bit, as follows: 2266 * C_bit is 1 if point compression should be used, otherwise it 2267 is 0. 2269 * I_bit is 1 if P is the point at infinity, otherwise it is 0. 2271 * S_bit is 0 if P is the point at infinity or if point 2272 compression is not used. Otherwise (i.e., when point 2273 compression is used and P is not the point at infinity), if P 2274 is a point on E, S_bit = sign_GF_p(y), else if P is a point on 2275 E', S_bit = sign_GF_p^2(y). 2277 2. Let m_byte = (C_bit * 2^7) + (I_bit * 2^6) + (S_bit * 2^5). 2279 3. Let x_string be the serialization of x, which is defined as 2280 follows: 2282 * If P is the point at infinity on E, let x_string = I2OSP(0, 2283 48). 2285 * If P is a point on E other than the point at infinity, then x 2286 is an element of GF(p), i.e., an integer in the inclusive 2287 range [0, p - 1]. In this case, let x_string = I2OSP(x, 48). 2289 * If P is the point at infinity on E', let x_string = I2OSP(0, 2290 96). 2292 * If P is a point on E' other than the point at infinity, then x 2293 can be represented as (x_0, x_1) where x_0 and x_1 are 2294 elements of GF(p), i.e., integers in the inclusive range [0, p 2295 - 1] (see discussion of vector representations above). In 2296 this case, let x_string = I2OSP(x_1, 48) || I2OSP(x_0, 48). 2298 Notice that in all of the above cases, the 3 most significant 2299 bits of x_string[0] are guaranteed to be 0. 2301 4. If point compression is used, let y_string be the empty string. 2302 Otherwise (i.e., when point compression is not used), let 2303 y_string be the serialization of y, which is defined in Step 3. 2305 5. Let s_string = x_string || y_string. 2307 6. Set s_string[0] = x_string[0] OR m_byte, where OR is computed 2308 bitwise. After this operation, the most significant bit of 2309 s_string[0] equals C_bit, the next bit equals I_bit, and the next 2310 equals S_bit. (This is true because the three most significant 2311 bits of x_string[0] are guaranteed to be zero, as discussed 2312 above.) 2314 7. Output s_string. 2316 C.2. Point deserialization procedure 2318 The deserialization procedure is defined as follows for a string 2319 s_string. This procedure uses the OS2IP function defined in 2320 [RFC8017]. 2322 1. Let m_byte = s_string[0] AND 0xE0, where AND is computed bitwise. 2323 In other words, the three most significant bits of m_byte equal 2324 the three most significant bits of s_string[0], and the remaining 2325 bits are 0. 2327 If m_byte equals any of 0x20, 0x60, or 0xE0, output INVALID and 2328 stop decoding. 2330 Otherwise: 2332 * Let C_bit equal the most significant bit of m_byte, 2334 * Let I_bit equal the second most significant bit of m_byte, and 2336 * Let S_bit equal the third most significant bit of m_byte. 2338 2. If C_bit is 1: 2340 * If s_string has length 48 bytes, the output point is on the 2341 curve E. 2343 * If s_string has length 96 bytes, the output point is on the 2344 curve E'. 2346 * If s_string has any other length, output INVALID and stop 2347 decoding. 2349 If C_bit is 0: 2351 * If s_string has length 96 bytes, the output point is on E. 2353 * If s_string has length 192 bytes, the output point is on E'. 2355 * If s_string has any other length, output INVALID and stop 2356 decoding. 2358 3. Let s_string[0] = s_string[0] AND 0x1F, where AND is computed 2359 bitwise. In other words, set the three most significant bits of 2360 s_string[0] to 0. 2362 4. If I_bit is 1: 2364 * If s_string is not the all zeros string, output INVALID and 2365 stop decoding. 2367 * Otherwise (i.e., if s_string is the all zeros string), output 2368 the point at infinity on the curve that was determined in step 2369 2 and stop decoding. 2371 Otherwise, I_bit must be 0. Continue decoding. 2373 5. If C_bit is 0: 2375 * Let x_string be the first half of s_string. 2377 * Let y_string be the last half of s_string. 2379 * Let x = OS2IP(x_string). 2381 * Let y = OS2IP(y_string). 2383 * If the point P = (x, y) is not a valid point on the curve that 2384 was determined in step 2, output INVALID and stop decoding. 2386 * Otherwise, output the point P = (x, y) and stop decoding. 2388 Otherwise, C_bit must be 1. Continue decoding. 2390 6. Let x = OS2IP(s_string). 2392 7. If the curve that was determined in step 2 is E: 2394 * Let y2 = x^3 + 4 in GF(p). 2396 * If y2 is not square in GF(p), output INVALID and stop 2397 decoding. 2399 * Otherwise, let y = sqrt(y2) in GF(p) and let Y_bit = 2400 sign_GF_p(y). 2402 Otherwise, (i.e., when the curve that was determined in step 2 is 2403 E'): 2405 * Let y2 = x^3 + 4 * (u + 1) in GF(p^2). 2407 * If y2 is not square in GF(p^2), output INVALID and stop 2408 decoding. 2410 * Otherwise, let y = sqrt(y2) in GF(p^2) and let Y_bit = 2411 sign_GF_p^2(y). 2413 8. If S_bit equals Y_bit, output P = (x, y) and stop decoding. 2414 Otherwise, output P = (x, -y) and stop decoding. 2416 Appendix D. Adoption Status of Pairing-Friendly Curves with the 100-bit 2417 Security Level 2419 BN curves including BN254 that were estimated as the 128-bit security 2420 level before exTNFS ensure no more than the 100-bit security level by 2421 the effect of exTNFS. Table 2 summarizes the adoption status of the 2422 parameters with a security level lower than the "Arnd 128-bit" range. 2423 Please refer the Section 4 for the naming conventions for each curve 2424 listed in Table 2. 2426 +=============+===========+==========================+ 2427 | Category | Name | Supported 100-bit Curves | 2428 +=============+===========+==========================+ 2429 | Standard | ISO/IEC | BN256I | 2430 | +-----------+--------------------------+ 2431 | | TCG | BN256I | 2432 | +-----------+--------------------------+ 2433 | | FIDO/W3C | BN256I | 2434 | | +--------------------------+ 2435 | | | BN256D | 2436 +-------------+-----------+--------------------------+ 2437 | Library | mcl | BN254N | 2438 | | +--------------------------+ 2439 | | | BN_SNARK1 | 2440 | +-----------+--------------------------+ 2441 | | TEPLA | BN254B | 2442 | | +--------------------------+ 2443 | | | BN254N | 2444 | +-----------+--------------------------+ 2445 | | RELIC | BN254N | 2446 | | +--------------------------+ 2447 | | | BN256D | 2448 | +-----------+--------------------------+ 2449 | | AMCL | BN254N | 2450 | | +--------------------------+ 2451 | | | BN254CX | 2452 | | +--------------------------+ 2453 | | | BN256I | 2454 | +-----------+--------------------------+ 2455 | | Intel IPP | BN256I | 2456 | +-----------+--------------------------+ 2457 | | MIRACL | BN254N | 2458 | | +--------------------------+ 2459 | | | BN254CX | 2460 | | +--------------------------+ 2461 | | | BN256I | 2462 | +-----------+--------------------------+ 2463 | | Adjoint | BN_SNARK1 | 2464 | | +--------------------------+ 2465 | | | BN254B | 2466 | | +--------------------------+ 2467 | | | BN254N | 2468 | | +--------------------------+ 2469 | | | BN254S1 | 2470 | | +--------------------------+ 2471 | | | BN254S2 | 2472 +-------------+-----------+--------------------------+ 2473 | Application | Zcash | BN_SNARK1 | 2474 | +-----------+--------------------------+ 2475 | | DFINITY | BN254N | 2476 | | +--------------------------+ 2477 | | | BN_SNARK1 | 2478 +-------------+-----------+--------------------------+ 2480 Table 2: Adoption Status of Pairing-Friendly 2481 Curves with 100-bit Security Level(Legacy) 2483 Authors' Addresses 2485 Yumi Sakemi (editor) 2486 Infours 2488 Email: yumi.sakemi@infours.co.jp 2490 Tetsutaro Kobayashi 2491 NTT 2493 Email: tetsutaro.kobayashi.dr@hco.ntt.co.jp 2495 Tsunekazu Saito 2496 NTT 2498 Email: tsunekazu.saito.hg@hco.ntt.co.jp 2500 Riad S. Wahby 2501 Stanford University 2503 Email: rsw@cs.stanford.edu