idnits 2.17.1 draft-irtf-cfrg-pairing-friendly-curves-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 24, 2020) is 1522 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: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 1163 -- Looks like a reference, but probably isn't: '2' on line 1163 == Outdated reference: A later version (-23) exists of draft-ietf-lwig-curve-representations-08 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG Y. Sakemi 3 Internet-Draft Lepidum 4 Intended status: Experimental T. Kobayashi 5 Expires: August 27, 2020 T. Saito 6 NTT 7 February 24, 2020 9 Pairing-Friendly Curves 10 draft-irtf-cfrg-pairing-friendly-curves-01 12 Abstract 14 This memo introduces pairing-friendly curves used for constructing 15 pairing-based cryptography. It describes recommended parameters for 16 each security level and recent implementations of pairing-friendly 17 curves. 19 Status of This Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at https://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on August 27, 2020. 36 Copyright Notice 38 Copyright (c) 2020 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (https://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 54 1.1. Pairing-Based Cryptography . . . . . . . . . . . . . . . 2 55 1.2. Applications of Pairing-Based Cryptography . . . . . . . 3 56 1.3. Goal . . . . . . . . . . . . . . . . . . . . . . . . . . 4 57 1.4. Requirements Terminology . . . . . . . . . . . . . . . . 4 58 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 4 59 2.1. Elliptic Curve . . . . . . . . . . . . . . . . . . . . . 4 60 2.2. Pairing . . . . . . . . . . . . . . . . . . . . . . . . . 5 61 2.3. Barreto-Naehrig Curve . . . . . . . . . . . . . . . . . . 6 62 2.4. Barreto-Lynn-Scott Curve . . . . . . . . . . . . . . . . 6 63 2.5. Representation Convention for an Extension Field . . . . 7 64 3. Security of Pairing-Friendly Curves . . . . . . . . . . . . . 8 65 3.1. Evaluating the Security of Pairing-Friendly Curves . . . 8 66 3.2. Impact of the Recent Attack . . . . . . . . . . . . . . . 9 67 4. Security Evaluation of Pairing-Friendly Curves . . . . . . . 9 68 4.1. For 100 Bits of Security . . . . . . . . . . . . . . . . 9 69 4.2. For 128 Bits of Security . . . . . . . . . . . . . . . . 10 70 4.2.1. BN Curves . . . . . . . . . . . . . . . . . . . . . . 10 71 4.2.2. BLS Curves . . . . . . . . . . . . . . . . . . . . . 12 72 4.3. For 192 Bits of Security . . . . . . . . . . . . . . . . 14 73 4.4. For 256 Bits of Security . . . . . . . . . . . . . . . . 14 74 5. Implementations of Pairing-Friendly Curves . . . . . . . . . 17 75 6. Security Considerations . . . . . . . . . . . . . . . . . . . 20 76 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 77 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 20 78 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 79 9.1. Normative References . . . . . . . . . . . . . . . . . . 20 80 9.2. Informative References . . . . . . . . . . . . . . . . . 21 81 Appendix A. Computing Optimal Ate Pairing . . . . . . . . . . . 25 82 A.1. Optimal Ate Pairings over Barreto-Naehrig Curves . . . . 26 83 A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves . . . 26 84 Appendix B. Test Vectors of Optimal Ate Pairing . . . . . . . . 27 85 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 35 87 1. Introduction 89 1.1. Pairing-Based Cryptography 91 Elliptic curve cryptography is one of the important areas in recent 92 cryptography. The cryptographic algorithms based on elliptic curve 93 cryptography, such as ECDSA (Elliptic Curve Digital Signature 94 Algorithm), are widely used in many applications. 96 Pairing-based cryptography, a variant of elliptic curve cryptography, 97 has attracted the attention for its flexible and applicable 98 functionality. Pairing is a special map defined over elliptic 99 curves. Thanks to the characteristics of pairing, it can be applied 100 to construct several cryptographic algorithms and protocols such as 101 identity-based encryption (IBE), attribute-based encryption (ABE), 102 authenticated key exchange (AKE), short signatures and so on. 103 Several applications of pairing-based cryptography are now in 104 practical use. 106 As the importance of pairing grows, elliptic curves where pairing is 107 efficiently computable are studied and the special curves called 108 pairing-friendly curves are proposed. 110 1.2. Applications of Pairing-Based Cryptography 112 Several applications using pairing-based cryptography are 113 standardized and implemented. We show example applications available 114 in the real world. 116 IETF publishes RFCs for pairing-based cryptography such as Identity- 117 Based Cryptography [RFC5091], Sakai-Kasahara Key Encryption (SAKKE) 118 [RFC6508], and Identity-Based Authenticated Key Exchange (IBAKE) 119 [RFC6539]. SAKKE is applied to Multimedia Internet KEYing (MIKEY) 120 [RFC6509] and used in 3GPP [SAKKE]. 122 Pairing-based key agreement protocols are standardized in ISO/IEC 123 [ISOIEC11770-3]. In [ISOIEC11770-3], a key agreement scheme by Joux 124 [Joux00], identity-based key agreement schemes by Smart-Chen-Cheng 125 [CCS07] and by Fujioka-Suzuki-Ustaoglu [FSU10] are specified. 127 MIRACL implements M-Pin, a multi-factor authentication protocol 128 [M-Pin]. M-Pin protocol includes a kind of zero-knowledge proof, 129 where pairing is used for its construction. 131 Trusted Computing Group (TCG) specifies ECDAA (Elliptic Curve Direct 132 Anonymous Attestation) in the specification of Trusted Platform 133 Module (TPM) [TPM]. ECDAA is a protocol for proving the attestation 134 held by a TPM to a verifier without revealing the attestation held by 135 that TPM. Pairing is used for constructing ECDAA. FIDO Alliance 136 [FIDO] and W3C [W3C] also published ECDAA algorithm similar to TCG. 138 Intel introduces Intel Enhanced Privacy ID (EPID) which enables 139 remote attestation of a hardware device while preserving the privacy 140 of the device as a functionality of Intel Software Guard Extensions 141 (SGX) [EPID]. They extend TPM ECDAA to realize such functionality. 142 A pairing-based EPID has been proposed [BL10] and distributed along 143 with Intel SGX applications. 145 Zcash implements their own zero-knowledge proof algorithm named zk- 146 SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of 147 Knowledge) [Zcash]. zk-SNARKs is used for protecting privacy of 148 transactions of Zcash. They use pairing for constructing zk-SNARKS. 150 Cloudflare introduces Geo Key Manager [Cloudflare] to restrict 151 distribution of customers' private keys to the subset of their data 152 centers. To achieve this functionality, attribute-based encryption 153 is used and pairing takes a role as a building block. 155 Recently, Boneh-Lynn-Shacham (BLS) signature schemes are being 156 standardized [I-D.boneh-bls-signature] and utilized in several 157 blockchain projects such as Ethereum [Ethereum], Algorand [Algorand], 158 Chia Network [Chia] and DFINITY [DFINITY]. The aggregation 159 functionality of BLS signatures is effective for their applications 160 of decentralization and scalability. 162 1.3. Goal 164 The goal of this memo is to consider the security of pairing-friendly 165 curves used in pairing-based cryptography and introduce secure 166 parameters of pairing-friendly curves. Specifically, we explain the 167 recent attack against pairing-friendly curves and how much the 168 security of the curves is reduced. We show how to evaluate the 169 security of pairing-friendly curves and give the parameters for 100 170 bits of security, which is no longer secure, 128, 192 and 256 bits of 171 security. 173 1.4. Requirements Terminology 175 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 176 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 177 "OPTIONAL" in this document are to be interpreted as described in BCP 178 14 [RFC2119] [RFC8174] when, and only when, they appear in all 179 capitals, as shown here. 181 2. Preliminaries 183 2.1. Elliptic Curve 185 Let p > 3 be a prime and q = p^n for a natural number n. Let F_q be 186 a finite field. The curve defined by the following equation E is 187 called an elliptic curve. 189 E : y^2 = x^3 + A * x + B, 191 where x and y are in F_q, and A and B in F_q satisfy the discriminant 192 inequality 4 * A^3 + 27 * B^2 != 0 mod q. This is called Weierstrass 193 normal form of an elliptic curve. 195 Solutions (x, y) for an elliptic curve E, as well as the point at 196 infinity, O_E, are called F_q-rational points. If P and Q are two 197 points on the curve E, we can define R = P + Q as the opposite point 198 of the intersection between the curve E and the line that passes 199 through P and Q. 200 We can define P + O_E = P = O_E + P as well. Similarly, we can 201 define 2P = P + P and a scalar multiplication S = [a]P for a positive 202 integer a can be defined as an (a-1)-time addition of P. 204 The additive group, denoted by E(F_q), is constructed by the set of 205 F_q-rational points and the addition law described above. We can 206 define the cyclic additive group with a prime order r by taking a 207 base point BP in E(F_q) as a generator. This group is used for the 208 elliptic curve cryptography. 210 We define terminology used in this memo as follows. 212 O_E: the point at infinity over an elliptic curve E. 214 E(F_q): a group constructed by F_q-rational points of E. 216 #E(F_q): the number of F_q-rational points of E. 218 h: a cofactor such that h = #E(F_q) / r. 220 2.2. Pairing 222 Pairing is a kind of the bilinear map defined over two elliptic 223 curves E and E'. Examples include Weil pairing, Tate pairing, 224 optimal Ate pairing [Ver09] and so on. Especially, optimal Ate 225 pairing is considered to be efficient to compute and mainly used for 226 practical implementation. 228 Let E be an elliptic curve defined over a prime field F_p and E' be 229 an elliptic curve defined over an extension field of F_p. Let k be a 230 minimum integer such that r is a divisor of p^k - 1, which is called 231 an embedding degree. Let G_1 be a cyclic subgroup on the elliptic 232 curve E with order r, and G_2 be a cyclic subgroup on the elliptic 233 curve E' with order r. Let G_T be an order r subgroup of a 234 multiplicative group (F_p^k)^*. 236 Pairing is defined as a bilinear map e: (G_1, G_2) -> G_T satisfying 237 the following properties: 239 1. Bilinearity: for any S in G_1, T in G_2, and integers a and b, 240 e([a]S, [b]T) = e(S, T)^{a * b}. 242 2. Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S = 243 O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T = 244 O_E. 246 3. Computability: for any S in G_1 and T in G_2, the bilinear map is 247 efficiently computable. 249 2.3. Barreto-Naehrig Curve 251 A BN curve [BN05] is one of the instantiations of pairing-friendly 252 curves proposed in 2005. A pairing over BN curves constructs optimal 253 Ate pairings. 255 A BN curve is defined by elliptic curves E and E' parameterized by a 256 well chosen integer t. E is defined over F_p, where p is a prime 257 more than or equal to 5, and E(F_p) has a subgroup of prime order r. 258 The characteristic p and the order r are parameterized by 260 p = 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1 261 r = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1 263 for an integer t. 265 The elliptic curve E has an equation of the form E: y^2 = x^3 + b, 266 where b is an element of multiplicative group of order p. 268 BN curves always have order 6 twists. If m is an element which is 269 neither a square nor a cube in an extension field F_p^2, the twisted 270 curve E' of E is defined over an extension field F_p^2 by the 271 equation E': y^2 = x^3 + b' with b' = b / m or b' = b * m. BN curves 272 are called D-type if b' = b / m, and M-type if b' = b * m. The 273 embedded degree k is 12. 275 A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order 276 r, G_2 as a subgroup of E'(F_p^2), and G_T as a subgroup of a 277 multiplicative group (F_p^12)^* of order r. 279 2.4. Barreto-Lynn-Scott Curve 281 A BLS curve [BLS02] is another instantiations of pairings proposed in 282 2002. Similar to BN curves, a pairing over BLS curves constructs 283 optimal Ate pairings. 285 A BLS curve is elliptic curves E and E' parameterized by a well 286 chosen integer t. E is defined over a finite field F_p by an 287 equation of the form E: y^2 = x^3 + b, and its twisted curve, E': y^2 288 = x^3 + b', is defined in the same way as BN curves. In contrast to 289 BN curves, E(F_p) does not have a prime order. Instead, its order is 290 divisible by a large parameterized prime r and denoted by h * r with 291 cofactor h. The pairing will be defined on the r-torsions points. 292 In the same way as BN curves, BLS curves can be categorized into 293 D-type and M-type. 295 BLS curves vary according to different embedding degrees. In this 296 memo, we deal with BLS12 and BLS48 families with embedding degrees 12 297 and 48 with respect to r, respectively. 299 In BLS curves, parameterized p and r are given by the following 300 equations: 302 BLS12: 303 p = (t - 1)^2 * (t^4 - t^2 + 1) / 3 + t 304 r = t^4 - t^2 + 1 305 BLS48: 306 p = (t - 1)^2 * (t^16 - t^8 + 1) / 3 + t 307 r = t^16 - t^8 + 1 309 for a well chosen integer t. 311 A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order 312 r, G_2 as an order r subgroup of E'(F_p^2) for BLS12 and of E'(F_p^8) 313 for BLS48, and G_T as an order r subgroup of a multiplicative group 314 (F_p^12)^* for BLS12 and of a multiplicative group (F_p^48)^* for 315 BLS48. 317 2.5. Representation Convention for an Extension Field 319 Pairing-friendly curves use a tower of some extension fields. In 320 order to encode an element of an extension field, we adopt the 321 representation convention shown in Appendix J.4 of 322 [I-D.draft-lwig-curve-representations] . 324 Let F_p be a finite field of characteristic p and F_p^d be an 325 extension field of F_p of degree d and an indeterminate i. 327 For an element s in F_p^d such that s = s_0 + s_1 * i + ... + s_{d - 328 1} * i^{d - 1} for s_0, s_1, ... , s_{d - 1} in a basefield F_p, s 329 is represented as octet string by oct(s) = s_0 || s_1 || ... || s_{d 330 - 1}. 332 Let F_p^d' be an extension field of F_p^d of degree d' / d and an 333 indeterminate j. 335 For an element s' in F_p^d' such that s' = s'_0 + s'_1 * j + ... + 336 s'_{d' / d - 1} * j^{d' / d - 1} for s'_0, s'_1, ..., s'_{d' / d - 1} 337 in a basefield F_p^d, s' is represented as integer by oct(s') = 338 oct(s'_0) || oct(s'_1) || ... || oct(s'_{d' / d - 1}), where 339 oct(s'_0), ... , oct(s'_{d' / d - 1}) are octet strings encoded by 340 above convention. 342 In general, one can define encoding between integer and an element of 343 any finite field tower by inductively applying the above convention. 345 The parameters and test vectors of extension fields described in this 346 memo are encoded by this convention and represented in octet stream. 348 3. Security of Pairing-Friendly Curves 350 3.1. Evaluating the Security of Pairing-Friendly Curves 352 The security of pairing-friendly curves is evaluated by the hardness 353 of the following discrete logarithm problems. 355 - The elliptic curve discrete logarithm problem (ECDLP) in G_1 and 356 G_2 358 - The finite field discrete logarithm problem (FFDLP) in G_T 360 There are other hard problems over pairing-friendly curves used for 361 proving the security of pairing-based cryptography. Such problems 362 include computational bilinear Diffie-Hellman (CBDH) problem and 363 bilinear Diffie-Hellman (BDH) Problem, decision bilinear Diffie- 364 Hellman (DBDH) problem, gap DBDH problem, etc [ECRYPT]. Almost all 365 of these variants are reduced to the hardness of discrete logarithm 366 problems described above and believed to be easier than the discrete 367 logarithm problems. 369 There would be the case where the attacker solves these reduced 370 problems to break pairing-based cryptography. Since such attacks 371 have not been discovered yet, we discuss the hardness of the discrete 372 logarithm problems in this memo. 374 The security level of pairing-friendly curves is estimated by the 375 computational cost of the most efficient algorithm to solve the above 376 discrete logarithm problems. The well-known algorithms for solving 377 the discrete logarithm problems include Pollard's rho algorithm 378 [Pollard78], Index Calculus [HR83] and so on. In order to make index 379 calculus algorithms more efficient, number field sieve (NFS) 380 algorithms are utilized. 382 3.2. Impact of the Recent Attack 384 In 2016, Kim and Barbulescu proposed a new variant of the NFS 385 algorithms, the extended tower number field sieve (exTNFS), which 386 drastically reduces the complexity of solving FFDLP [KB16]. Due to 387 exTNFS, the security level of pairing-friendly curves asymptotically 388 dropped down. For instance, Barbulescu and Duquesne estimated that 389 the security of the BN curves which had been believed to provide 128 390 bits of security (BN256, for example) dropped down to approximately 391 100 bits [BD18]. 393 Some papers showed the minimum bit length of the parameters of 394 pairing-friendly curves for each security level when applying exTNFS 395 as an attacking method for FFDLP. For 128 bits of security, Menezes, 396 Sarkar and Singh estimated the minimum bit length of p of BN curves 397 after exTNFS as 383 bits, and that of BLS12 curves as 384 bits 398 [MSS17]. For 256 bits of security, Kiyomura et al. estimated the 399 minimum bit length of p^k of BLS48 curves as 27,410 bits, which 400 implied 572 bits of p [KIK17]. 402 4. Security Evaluation of Pairing-Friendly Curves 404 We give security evaluation for pairing-friendly curves based on the 405 evaluating method presented in Section 3. We also introduce secure 406 parameters of pairing-friendly curves for each security level. The 407 parameters introduced here are chosen with the consideration of 408 security, efficiency and global acceptance. 410 For security, we introduce the parameters with 100 bits, 128 bits, 411 192 bits and 256 bits of security. We note that 100 bits of security 412 is no longer secure and recommend 128 bits, 192 bits and 256 bits of 413 security for secure applications. We follow TLS 1.3 [RFC8446] which 414 specifies the cipher suites with 128 bits and 256 bits of security as 415 mandatory-to-implement for the choice of the security level. 417 Implementers of the applications have to choose the parameters with 418 appropriate security level according to the security requirements of 419 the applications. For efficiency, we refer to the benchmark by mcl 420 [mcl] for 128 bits of security, and by Kiyomura et al. [KIK17] for 421 256 bits of security, and then choose sufficiently efficient 422 parameters. For global acceptance, we give the implementations of 423 pairing-friendly curves in Section 5. 425 4.1. For 100 Bits of Security 427 Before exTNFS, BN curves with 256-bit size of underlying finite field 428 (so-called BN256) were considered to achieve 128 bits of security. 430 After exTNFS, however, the security level of BN curves with 256-bit 431 size of underlying finite field fell into 100 bits. 433 Implementers who will newly develop the applications of pairing-based 434 cryptography SHOULD NOT use pairing-friendly curves with 100 bits of 435 security (i.e. BN256). 437 There exists applications which already implemented pairing-based 438 cryptography with 100-bit secure pairing-friendly curves. In such a 439 case, implementers MAY use 100 bits of security only if they need to 440 keep interoperability with the existing applications. 442 4.2. For 128 Bits of Security 444 4.2.1. BN Curves 446 A BN curve with 128 bits of security is shown in [BD18], which we 447 call BN462. BN462 is defined by a parameter 449 t = 2^114 + 2^101 - 2^14 - 1 451 for the definition in Section 2.3. 453 For the finite field F_p, the towers of extension field F_p^2, F_p^6 454 and F_p^12 are defined by indeterminates u, v, w as follows: 456 F_p^2 = F_p[u] / (u^2 + 1) 457 F_p^6 = F_p^2[v] / (v^3 - u - 2) 458 F_p^12 = F_p^6[w] / (w^2 - v). 460 Defined by t, the elliptic curve E and its twisted curve E' are 461 represented by E: y^2 = x^3 + 5 and E': y^2 = x^3 - u + 2, 462 respectively. The size of p becomes 462-bit length. A pairing e is 463 defined by taking G_1 as a cyclic group of order r generated by a 464 base point BP = (x, y) in F_p, G_2 as a cyclic group of order r 465 generated by a based point BP' = (x', y') in F_p^2, and G_T as a 466 subgroup of a multiplicative group (F_p^12)^* of order r. BN462 is 467 D-type. 469 We give the following parameters for BN462. 471 - G_1 defined over E: y^2 = x^3 + b 473 o p : a characteristic 475 o r : an order 477 o BP = (x, y) : a base point 478 o h : a cofactor 480 o b : a coefficient of E 482 - G_2 defined over E': y^2 = x^3 + b' 484 o r' : an order 486 o BP' = (x', y') : a base point (encoded with 487 [I-D.draft-lwig-curve-representations]) 489 * x' = x'_0 + x'_1 * u (x'_0, x'_1 in F_p) 491 * y' = y'_0 + y'_1 * u (y'_0, y'_1 in F_p) 493 o h' : a cofactor 495 o b' : a coefficient of E' 497 p: 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908f41c802 498 0ffffffffff6ff66fc6ff687f640000000002401b00840138013 500 r: 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908ee1c201 501 f7fffffffff6ff66fc7bf717f7c0000000002401b007e010800d 503 x: 0x21a6d67ef250191fadba34a0a30160b9ac9264b6f95f63b3edbec3cf4b2e689d 504 b1bbb4e69a416a0b1e79239c0372e5cd70113c98d91f36b6980d 506 y: 0x0118ea0460f7f7abb82b33676a7432a490eeda842cccfa7d788c659650426e6a 507 f77df11b8ae40eb80f475432c66600622ecaa8a5734d36fb03de 509 h: 1 511 b: 5 513 r': 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908ee1c2 514 01f7fffffffff6ff66fc7bf717f7c0000000002401b007e010800d 516 x'_0: 0x0257ccc85b58dda0dfb38e3a8cbdc5482e0337e7c1cd96ed61c913820408 517 208f9ad2699bad92e0032ae1f0aa6a8b48807695468e3d934ae1e4df 519 x'_1: 0x1d2e4343e8599102af8edca849566ba3c98e2a354730cbed9176884058b1 520 8134dd86bae555b783718f50af8b59bf7e850e9b73108ba6aa8cd283 522 y'_0: 0x0a0650439da22c1979517427a20809eca035634706e23c3fa7a6bb42fe81 523 0f1399a1f41c9ddae32e03695a140e7b11d7c3376e5b68df0db7154e 525 y'_1: 0x073ef0cbd438cbe0172c8ae37306324d44d5e6b0c69ac57b393f1ab370fd 526 725cc647692444a04ef87387aa68d53743493b9eba14cc552ca2a93a 528 h': 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908fa1ce 529 0227fffffffff6ff66fc63f5f7f4c0000000002401b008a0168019 531 b': -u + 2 533 4.2.2. BLS Curves 535 A BLS12 curve with 128 bits of security shown in [BLS12-381], 536 BLS12-381, is defined by a parameter 538 t = -2^63 - 2^62 - 2^60 - 2^57 - 2^48 - 2^16 540 and the size of p becomes 381-bit length. 542 For the finite field F_p, the towers of extension field F_p^2, F_p^6 543 and F_p^12 are defined by indeterminates u, v, w as follows: 545 F_p^2 = F_p[u] / (u^2 + 1) 546 F_p^6 = F_p^2[v] / (v^3 - u - 1) 547 F_p^12 = F_p^6[w] / (w^2 - v). 549 Defined by t, the elliptic curve E and its twisted curve E' are 550 represented by E: y^2 = x^3 + 4 and E': y^2 = x^3 + 4(u + 1). 552 A pairing e is defined by taking G_1 as a cyclic group of order r 553 generated by a base point BP = (x, y) in F_p, G_2 as a cyclic group 554 of order r generated by a based point BP' = (x', y') in F_p^2, and 555 G_T as a subgroup of a multiplicative group (F_p^12)^* of order r. 556 BLS12-381 is M-type. 558 We have to note that, according to [MSS17], the bit length of p for 559 BLS12 to achieve 128 bits of security is calculated as 384 bits and 560 more, which BLS12-381 does not satisfy. They state that BLS12-381 561 achieves 127-bit security level evaluated by the computational cost 562 of Pollard's rho, whereas NCC group estimated that the security level 563 of BLS12-381 is between 117 and 120 bits at most [NCCG]. Therefore, 564 we regard BN462 as a "conservative" parameter, and BLS12-381 as an 565 "optimistic" parameter. 567 We give the following parameters for BLS12-381. 569 - G_1 defined over E: y^2 = x^3 + b 571 o p : a characteristic 572 o r : an order 574 o BP = (x, y) : a base point 576 o h : a cofactor 578 o b : a coefficient of E 580 - G_2 defined over E': y^2 = x^3 + b' 582 o r' : an order 584 o BP' = (x', y') : a base point (encoded with 585 [I-D.draft-lwig-curve-representations]) 587 * x' = x'_0 + x'_1 * u (x'_0, x'_1 in F_p) 589 * y' = y'_0 + y'_1 * u (y'_0, y'_1 in F_p) 591 o h' : a cofactor 593 o b' : a coefficient of E' 595 p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f624 596 1eabfffeb153ffffb9feffffffffaaab 598 r: 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 600 x: 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac58 601 6c55e83ff97a1aeffb3af00adb22c6bb 603 y: 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3ed 604 d03cc744a2888ae40caa232946c5e7e1 606 h: 0x396c8c005555e1568c00aaab0000aaab 608 b: 4 610 r': 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6 611 241eabfffeb153ffffb9feffffffffaaab 613 x'_0: 0x024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3 614 d1770bac0326a805bbefd48056c8c121bdb8 616 x'_1: 0x13e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f 617 5049334cf11213945d57e5ac7d055d042b7e 619 y'_0: 0x0ce5d527727d6e118cc9cdc6da2e351aadfd9baa8cbdd3a76d429a695160 620 d12c923ac9cc3baca289e193548608b82801 622 y'_1: 0x0606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af267492ab572e 623 99ab3f370d275cec1da1aaa9075ff05f79be 625 h': 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7dd 626 fa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5 628 b': 4 * (u + 1) 630 4.3. For 192 Bits of Security 632 (TBD) 634 4.4. For 256 Bits of Security 636 As shown in Section 3.2, it is unrealistic to achieve 256 bits of 637 security by BN curves since the minimum size of p becomes too large 638 to implement. Hence, we consider BLS48 for 256 bits of security. 640 A BLS48 curve with 256 bits of security is shown in [KIK17], which we 641 call BLS48-581. It is defined by a parameter 643 t = -1 + 2^7 - 2^10 - 2^30 - 2^32. 645 For the finite field F_p, the towers of extension field F_p^2, F_p^4, 646 F_p^8, F_p^24 and F_p^48 are defined by indeterminates u, v, w, z, s 647 as follows: 649 F_p^2 = F_p[u] / (u^2 + 1) 650 F_p^4 = F_p^2[v] / (v^2 + u + 1) 651 F_p^8 = F_p^4[w] / (w^2 + v) 652 F_p^24 = F_p^8[z] / (z^3 + w) 653 F_p^48 = F_p^24[s] / (s^2 + z). 655 The elliptic curve E and its twisted curve E' are represented by E: 656 y^2 = x^3 + 1 and E': y^2 = x^3 - 1 / w. A pairing e is defined by 657 taking G_1 as a cyclic group of order r generated by a base point BP 658 = (x, y) in F_p, G_2 as a cyclic group of order r generated by a 659 based point BP' = (x', y') in F_p^8, and G_T as a subgroup of a 660 multiplicative group (F_p^48)^* of order r. The size of p becomes 661 581-bit length. BLS48-581 is D-type. 663 We then give the parameters for BLS48-581 as follows. 665 - G_1 defined over E: y^2 = x^3 + b 666 o p : a characteristic 668 o r : a prime which divides an order of G_1 670 o BP = (x, y) : a base point 672 o h : a cofactor 674 o b : a coefficient of E 676 - G_2 defined over E': y^2 = x^3 + b' 678 o r' : an order 680 o BP' = (x', y') : a base point (encoded with 681 [I-D.draft-lwig-curve-representations]) 683 * x' = x'_0 + x'_1 * u + x'_2 * v + x'_3 * u * v + x'_4 * w + 684 x'_5 * u * w + x'_6 * v * w + x'_7 * u * v * w (x'_0, ..., 685 x'_7 in F_p) 687 * y' = y'_0 + y'_1 * u + y'_2 * v + y'_3 * u * v + y'_4 * w + 688 y'_5 * u * w + y'_6 * v * w + y'_7 * u * v * w (y'_0, ..., 689 y'_7 in F_p) 691 o h' : a cofactor 693 o b' : a coefficient of E' 695 p: 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444 696 a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac 697 3edc154e6565912b 699 r: 0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6 700 e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c01 702 x: 0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7 703 544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d8c 704 3bce8732315af640 706 y: 0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279dd41b720e 707 f7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f37aef7b926b57 708 6dbb5de3e2587a70 710 x'_0: 0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2e 711 f156c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b797663221 712 54dec34fd0b4ace8bfab 714 x'_1: 0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da1230 715 7f4e1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa 716 143f1669b36676b47c57 718 x'_2: 0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccba 719 b5ab6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3 720 f0b46488156ca55a3e6a 722 x'_3: 0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f 723 8be0cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80 724 bc3f09a7033cbb7feafe 726 x'_4: 0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c580 727 5386699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d 728 4cbb739c3a1c53f8cce5 730 x'_5: 0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb0 731 37418181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce 732 3370f2004d914a3c093a 734 x'_6: 0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0 735 b7a449cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c 736 3354e41607e60750e057 738 x'_7: 0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf7417197 739 28a7f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97 740 c3f84e19da00fbc6ae34 742 y'_0: 0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc4 743 35faab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c 744 0ff323edd3fe4d2d7971 746 y'_1: 0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d7296473 747 2fcbf3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ff 748 c7b111471db936cd5665 750 y'_2: 0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d37 751 0514475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b 752 8fde68332a526a2a8474 754 y'_3: 0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e1 755 22d2742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e5 756 337316213da92841589d 758 y'_4: 0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f11 759 29857ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf 760 7a43f47831f982e50137 762 y'_5: 0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055a 763 b7504fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226c 764 f3a594eedc58cf90bee4 766 y'_6: 0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c8 767 19a6df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9a 768 a62b3d41faeafeb23986 770 y'_7: 0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8e 771 ca9a9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e8406 772 9c55d667ffcb732718b6 774 h: 0x85555841aaaec4ac 776 b: 1 778 r': 0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2 779 e6e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c 780 01 782 h': 0x170e915cb0a6b7406b8d94042317f811d6bc3fc6e211ada42e58ccfcb3ac07 783 6a7e4499d700a0c23dc4b0c078f92def8c87b7fe63e1eea270db353a4ef4d38b59 784 98ad8f0d042ea24c8f02be1c0c83992fe5d7725227bb27123a949e0876c0a8ce0a 785 67326db0e955dcb791b867f31d6bfa62fbdd5f44a00504df04e186fae033f1eb43 786 c1b1a08b6e086eff03c8fee9ebdd1e191a8a4b0466c90b389987de5637d5dd13da 787 b33196bd2e5afa6cd19cf0fc3fc7db7ece1f3fac742626b1b02fcee04043b2ea96 788 492f6afa51739597c54bb78aa6b0b99319fef9d09f768831018ee6564c68d054c6 789 2f2e0b4549426fec24ab26957a669dba2a2b6945ce40c9aec6afdeda16c79e1554 790 6cd7771fa544d5364236690ea06832679562a68731420ae52d0d35a90b8d10b688 791 e31b6aee45f45b7a5083c71732105852decc888f64839a4de33b99521f0984a418 792 d20fc7b0609530e454f0696fa2a8075ac01cc8ae3869e8d0fe1f3788ffac4c01aa 793 2720e431da333c83d9663bfb1fb7a1a7b90528482c6be7892299030bb51a51dc7e 794 91e9156874416bf4c26f1ea7ec578058563960ef92bbbb8632d3a1b695f954af10 795 e9a78e40acffc13b06540aae9da5287fc4429485d44e6289d8c0d6a3eb2ece3501 796 2452751839fb48bc14b515478e2ff412d930ac20307561f3a5c998e6bcbfebd97e 797 ffc6433033a2361bfcdc4fc74ad379a16c6dea49c209b1 799 b': -1 / w 801 5. Implementations of Pairing-Friendly Curves 803 We show the pairing-friendly curves selected by existing standards, 804 cryptographic libraries and applications. 806 ISO/IEC 15946-5 [ISOIEC15946-5] shows examples of BN curves with the 807 size of 160, 192, 224, 256, 384 and 512 bits of p. There is no 808 action so far after the proposal of exTNFS. 810 TCG adopts an BN curve of 256 bits specified in ISO/IEC 15946-5 811 (TPM_ECC_BN_P256) and that of 638 bits specified by their own 812 (TPM_ECC_BN_P638). FIDO Alliance [FIDO] and W3C [W3C] adopt the same 813 BN curves as TCG, a 512-bit BN curve shown in ISO/IEC 15946-5 and 814 another 256-bit BN curve. 816 Cryptographic libraries which implement pairings include PBC [PBC], 817 mcl [mcl], RELIC [RELIC], TEPLA [TEPLA], AMCL [AMCL], Intel IPP 818 [Intel-IPP] and a library by Kyushu University [BLS48]. 820 Cloudflare published a new cryptographic library CIRCL (Cloudflare 821 Interoperable, Reusable Cryptographic Library) in 2019 [CIRCL]. The 822 plan for the implementation of secure pairing-friendly curves is 823 stated in their roadmap. 825 MIRACL implements BN curves and BLS12 curves [MIRACL]. 827 Zcash implements a BN curve (named BN128) in their library libsnark 828 [libsnark]. After exTNFS, they propose a new parameter of BLS12 as 829 BLS12-381 [BLS12-381] and publish its experimental implementation 830 [zkcrypto]. 832 Ethereum 2.0 adopts BLS12-381 (BLS12_381), BN curves with 254 bits of 833 p (CurveFp254BNb) and 382 bits of p (CurveFp382_1 and CurveFp382_2) 834 [go-bls]. Their implementation calls mcl [mcl] for pairing 835 computation. Chia Network publishs their implementation [Chia] by 836 integrating the RELIC toolkit [RELIC]. 838 Table 1 shows the adoption of pairing-friendly curves in existing 839 standards, cryptographic libraries and applications. In this table, 840 the curves marked as (*) indicate that the security level is 841 evaluated less than the one labeld in the table. 843 +------------+--------------+-----------------------+-------+-------+ 844 | Name | 100 bit | 128 bit | 192 | 256 | 845 | | | | bit | bit | 846 +------------+--------------+-----------------------+-------+-------+ 847 | ISO/IEC | BN256 | BN384 | | | 848 | 15946-5 | | | | | 849 | | | | | | 850 | TCG | BN256 | | | | 851 | | | | | | 852 | FIDO/W3C | BN256 | | | | 853 | | | | | | 854 | PBC | BN | | | | 855 | | | | | | 856 | mcl | BN254 / | BN381_1 (*) / BN462 / | | | 857 | | BN_SNARK1 | BLS12-381 | | | 858 | | | | | | 859 | RELIC | BN254 / | BLS12-381 / BLS12-455 | | | 860 | | BN256 | | | | 861 | | | | | | 862 | TEPLA | BN254 | | | | 863 | | | | | | 864 | AMCL | BN254 / | BLS12-381 (*) / | | BLS48 | 865 | | BN256 | BLS12-383 (*) / | | | 866 | | | BLS12-461 | | | 867 | | | | | | 868 | Intel IPP | BN256 | | | | 869 | | | | | | 870 | Kyushu | | | | BLS48 | 871 | Univ. | | | | | 872 | | | | | | 873 | MIRACL | BN254 | BLS12 | | | 874 | | | | | | 875 | Zcash | BN128 | BLS12-381 | | | 876 | | (CurveSNARK) | | | | 877 | | | | | | 878 | Ethereum | BN254 | BN382 (*) / BLS12-381 | | | 879 | | | (*) | | | 880 | | | | | | 881 | Chia | | BLS12-381 (*) | | | 882 | Network | | | | | 883 +------------+--------------+-----------------------+-------+-------+ 885 Table 1: Adoption of Pairing-Friendly Curves 887 6. Security Considerations 889 This memo entirely describes the security of pairing-friendly curves, 890 and introduces secure parameters of pairing-friendly curves. We give 891 these parameters in terms of security, efficiency and global 892 acceptance. The parameters for 100, 128, 192 and 256 bits of 893 security are introduced since the security level will different in 894 the requirements of the pairing-based applications. Implementers can 895 select these parameters according to their security requirements. 897 7. IANA Considerations 899 This document has no actions for IANA. 901 8. Acknowledgements 903 The authors would like to thank Akihiro Kato and Shoko Yonezawa for 904 their significant contribution to the early version of this memo. 905 The authors would also like to acknowledge Sakae Chikara, Hoeteck 906 Wee, Sergey Gorbunov and Michael Scott for their valuable comments. 908 9. References 910 9.1. Normative References 912 [BD18] Barbulescu, R. and S. Duquesne, "Updating Key Size 913 Estimations for Pairings", Journal of Cryptology, 914 DOI 10.1007/s00145-018-9280-5, January 2018. 916 [BLS02] Barreto, P., Lynn, B., and M. Scott, "Constructing 917 Elliptic Curves with Prescribed Embedding Degrees", 918 Security in Communication Networks pp. 257-267, 919 DOI 10.1007/3-540-36413-7_19, 2003. 921 [BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic 922 Curves of Prime Order", Selected Areas in Cryptography pp. 923 319-331, DOI 10.1007/11693383_22, 2006. 925 [KB16] Kim, T. and R. Barbulescu, "Extended Tower Number Field 926 Sieve: A New Complexity for the Medium Prime Case", 927 Advances in Cryptology - CRYPTO 2016 pp. 543-571, 928 DOI 10.1007/978-3-662-53018-4_20, 2016. 930 [KIK17] Kiyomura, Y., Inoue, A., Kawahara, Y., Yasuda, M., Takagi, 931 T., and T. Kobayashi, "Secure and Efficient Pairing at 932 256-Bit Security Level", Applied Cryptography and Network 933 Security pp. 59-79, DOI 10.1007/978-3-319-61204-1_4, 2017. 935 [MSS17] Menezes, A., Sarkar, P., and S. Singh, "Challenges with 936 Assessing the Impact of NFS Advances on the Security of 937 Pairing-Based Cryptography", Lecture Notes in Computer 938 Science pp. 83-108, DOI 10.1007/978-3-319-61273-7_5, 2017. 940 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 941 Requirement Levels", BCP 14, RFC 2119, 942 DOI 10.17487/RFC2119, March 1997, 943 . 945 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 946 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 947 May 2017, . 949 [Ver09] Vercauteren, F., "Optimal Pairings", IEEE Transactions on 950 Information Theory Vol. 56, pp. 455-461, 951 DOI 10.1109/tit.2009.2034881, January 2010. 953 9.2. Informative References 955 [Algorand] 956 Gorbunov, S., "Efficient and Secure Digital Signatures for 957 Proof-of-Stake Blockchains", . 960 [AMCL] The Apache Software Foundation, "The Apache Milagro 961 Cryptographic Library (AMCL)", 2016, 962 . 964 [BL10] Brickell, E. and J. Li, "Enhanced Privacy ID from Bilinear 965 Pairing for Hardware Authentication and Attestation", 2010 966 IEEE Second International Conference on Social Computing, 967 DOI 10.1109/socialcom.2010.118, August 2010. 969 [BLS12-381] 970 Bowe, S., "BLS12-381: New zk-SNARK Elliptic Curve 971 Construction", 972 . 974 [BLS48] Kyushu University, "bls48 - C++ library for Optimal Ate 975 Pairing on BLS48", 2017, 976 . 978 [CCS07] Chen, L., Cheng, Z., and N. Smart, "Identity-based key 979 agreement protocols from pairings", International Journal 980 of Information Security Vol. 6, pp. 213-241, 981 DOI 10.1007/s10207-006-0011-9, January 2007. 983 [Chia] Chia Network, "BLS signatures in C++, using the relic 984 toolkit", 985 . 987 [CIRCL] Cloudflare, "CIRCL: Cloudflare Interoperable, Reusable 988 Cryptographic Library", 2019, 989 . 991 [Cloudflare] 992 Sullivan, N., "Geo Key Manager: How It Works", 993 . 996 [DFINITY] Williams, D., "DFINITY Technology Overview Series 997 Consensus System Rev. 1", n.d., . 1000 [ECRYPT] ECRYPT, "Final Report on Main Computational Assumptions in 1001 Cryptography". 1003 [EPID] Intel Corporation, "Intel (R) SGX: Intel (R) EPID 1004 Provisioning and Attestation Services", 1005 . 1008 [Ethereum] 1009 Jordan, R., "Ethereum 2.0 Development Update #17 - 1010 Prysmatic Labs", . 1014 [FIDO] Lindemann, R., "FIDO ECDAA Algorithm - FIDO Alliance 1015 Review Draft 02", . 1019 [FSU10] Fujioka, A., Suzuki, K., and B. Ustaoglu, "Ephemeral Key 1020 Leakage Resilient and Efficient ID-AKEs That Can Share 1021 Identities, Private and Master Keys", Lecture Notes in 1022 Computer Science pp. 187-205, 1023 DOI 10.1007/978-3-642-17455-1_12, 2010. 1025 [go-bls] Prysmatic Labs, "go-bls - Go wrapper for a BLS12-381 1026 Signature Aggregation implementation in C++", 2018, 1027 . 1029 [HR83] Hellman, M. and J. Reyneri, "Fast Computation of Discrete 1030 Logarithms in GF (q)", Advances in Cryptology pp. 3-13, 1031 DOI 10.1007/978-1-4757-0602-4_1, 1983. 1033 [I-D.boneh-bls-signature] 1034 Boneh, D., Gorbunov, S., Wee, H., and Z. Zhang, "BLS 1035 Signature Scheme", draft-boneh-bls-signature-00 (work in 1036 progress), February 2019. 1038 [I-D.draft-lwig-curve-representations] 1039 Struik, R., "Alternative Elliptic Curve Representations", 1040 draft-ietf-lwig-curve-representations-08 (work in 1041 progress), July 2019. 1043 [Intel-IPP] 1044 Intel Corporation, "Developer Reference for Intel 1045 Integrated Performance Primitives Cryptography 2019", 1046 2018, . 1050 [ISOIEC11770-3] 1051 ISO/IEC, "ISO/IEC 11770-3:2015", ISO/IEC Information 1052 technology -- Security techniques -- Key management -- 1053 Part 3: Mechanisms using asymmetric techniques, 2015. 1055 [ISOIEC15946-5] 1056 ISO/IEC, "ISO/IEC 15946-5:2017", ISO/IEC Information 1057 technology -- Security techniques -- Cryptographic 1058 techniques based on elliptic curves -- Part 5: Elliptic 1059 curve generation, 2017. 1061 [Joux00] Joux, A., "A One Round Protocol for Tripartite Diffie- 1062 Hellman", Lecture Notes in Computer Science pp. 385-393, 1063 DOI 10.1007/10722028_23, 2000. 1065 [libsnark] 1066 SCIPR Lab, "libsnark: a C++ library for zkSNARK proofs", 1067 2012, . 1069 [M-Pin] Scott, M., "M-Pin: A Multi-Factor Zero Knowledge 1070 Authentication Protocol", July 2019, 1071 . 1074 [mcl] Mitsunari, S., "mcl - A portable and fast pairing-based 1075 cryptography library", 2016, 1076 . 1078 [MIRACL] MIRACL Ltd., "MIRACL Cryptographic SDK", 2018, 1079 . 1081 [NCCG] NCC Group, "Zcash Overwinter Consensus and Sapling 1082 Cryptography Review", . 1086 [PBC] Lynn, B., "PBC Library - The Pairing-Based Cryptography 1087 Library", 2006, . 1089 [Pollard78] 1090 Pollard, J., "Monte Carlo methods for index computation 1091 $({\rm mod}\ p)$", Mathematics of Computation Vol. 32, pp. 1092 918-918, DOI 10.1090/s0025-5718-1978-0491431-9, September 1093 1978. 1095 [RELIC] Gouvea, C., "RELIC is an Efficient LIbrary for 1096 Cryptography", 2013, 1097 . 1099 [RFC5091] Boyen, X. and L. Martin, "Identity-Based Cryptography 1100 Standard (IBCS) #1: Supersingular Curve Implementations of 1101 the BF and BB1 Cryptosystems", RFC 5091, 1102 DOI 10.17487/RFC5091, December 2007, 1103 . 1105 [RFC6508] Groves, M., "Sakai-Kasahara Key Encryption (SAKKE)", 1106 RFC 6508, DOI 10.17487/RFC6508, February 2012, 1107 . 1109 [RFC6509] Groves, M., "MIKEY-SAKKE: Sakai-Kasahara Key Encryption in 1110 Multimedia Internet KEYing (MIKEY)", RFC 6509, 1111 DOI 10.17487/RFC6509, February 2012, 1112 . 1114 [RFC6539] Cakulev, V., Sundaram, G., and I. Broustis, "IBAKE: 1115 Identity-Based Authenticated Key Exchange", RFC 6539, 1116 DOI 10.17487/RFC6539, March 2012, 1117 . 1119 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 1120 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 1121 . 1123 [SAKKE] 3GPP, "Security of the mission critical service (Release 1124 15)", 3GPP TS 33.180 15.3.0, 2018. 1126 [TEPLA] University of Tsukuba, "TEPLA: University of Tsukuba 1127 Elliptic Curve and Pairing Library", 2013, 1128 . 1130 [TPM] Trusted Computing Group (TCG), "Trusted Platform Module 1131 Library Specification, Family \"2.0\", Level 00, Revision 1132 01.38", . 1135 [W3C] Lundberg, E., "Web Authentication: An API for accessing 1136 Public Key Credentials Level 1 - W3C Recommendation", 1137 . 1139 [Zcash] Lindemann, R., "What are zk-SNARKs?", 1140 . 1142 [zkcrypto] 1143 zkcrypto, "zkcrypto - Pairing-friendly elliptic curve 1144 library", 2017, . 1146 Appendix A. Computing Optimal Ate Pairing 1148 Before presenting the computation of optimal Ate pairing e(P, Q) 1149 satisfying the properties shown in Section 2.2, we give subfunctions 1150 used for pairing computation. 1152 The following algorithm Line_Function shows the computation of the 1153 line function. It takes A = (A[1], A[2]), B = (B[1], B[2]) in G_2 1154 and P = ((P[1], P[2])) in G_1 as input and outputs an element of G_T. 1156 if (A = B) then 1157 l := (3 * A[1]^2) / (2 * A[2]); 1158 else if (A = -B) then 1159 return P[1] - A[1]; 1160 else 1161 l := (B[2] - A[2]) / (B[1] - A[1]); 1162 end if; 1163 return (l * (P[1] -A[1]) + A[2] -P[2]); 1165 When implementing the line function, implementers should consider the 1166 isomorphism of E and its twisted curve E' so that one can reduce the 1167 computational cost of operations in G_2. We note that the function 1168 Line_function does not consider such isomorphism. 1170 Computation of optimal Ate pairing for BN curves uses Frobenius map. 1171 Let a Frobenius map pi for a point Q = (x, y) over E' be pi(p, Q) = 1172 (x^p, y^p). 1174 A.1. Optimal Ate Pairings over Barreto-Naehrig Curves 1176 Let c = 6 * t + 2 for a parameter t and c_0, c_1, ... , c_L in 1177 {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., L) equals to 1178 c. 1180 The following algorithm shows the computation of optimal Ate pairing 1181 over Barreto-Naehrig curves. It takes P in G_1, Q in G_2, an integer 1182 c, c_0, ...,c_L in {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, 1183 ..., L) equals to c, and an order r as input, and outputs e(P, Q). 1185 f := 1; T := Q; 1186 if (c_L = -1) 1187 T := -T; 1188 end if 1189 for i = L-1 to 0 1190 f := f^2 * Line_function(T, T, P); T := 2 * T; 1191 if (c_i = 1 | c_i = -1) 1192 f := f * Line_function(T, c_i * Q); T := T + c_i * Q; 1193 end if 1194 end for 1195 Q_1 := pi(p, Q); Q_2 := pi(p, Q_1); 1196 f := f * Line_function(T, Q_1, P); T := T + Q_1; 1197 f := f * Line_function(T, -Q_2, P); 1198 f := f^{(p^k - 1) / r} 1199 return f; 1201 A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves 1203 Let c = t for a parameter t and c_0, c_1, ... , c_L in {-1,0,1} such 1204 that the sum of c_i * 2^i (i = 0, 1, ..., L) equals to c. The 1205 following algorithm shows the computation of optimal Ate pairing over 1206 Barreto-Lynn-Scott curves. It takes P in G_1, Q in G_2, a parameter 1207 c, c_0, c_1, ..., c_L in {-1,0,1} such that the sum of c_i * 2^i (i = 1208 0, 1, ..., L), and an order r as input, and outputs e(P, Q). 1210 f := 1; T := Q; 1211 if (c_L = -1) 1212 T := -T; 1213 end if 1214 for i = L-1 to 0 1215 f := f^2 * Line_function(T, T, P); T := 2 * T; 1216 if (c_i = 1 | c_i = -1) 1217 f := f * Line_function(T, c_i * Q, P); T := T + c_i * Q; 1218 end if 1219 end for 1220 f := f^{(p^k - 1) / r}; 1221 return f; 1223 Appendix B. Test Vectors of Optimal Ate Pairing 1225 We provide test vectors for Optimal Ate Pairing e(P, Q) given in 1226 Appendix A for the curves BN462, BLS12-381 and BLS48-581 given in 1227 Section 4. Here, the inputs P = (x, y) and Q = (x', y') are the 1228 corresponding base points BP and BP' given in Section 4. 1230 For BN462 and BLS12-381, Q = (x', y') is given by 1232 x' = x'_0 + x'_1 * u and 1233 y' = y'_0 + y'_1 * u, 1235 where u is a indeterminate and x'_0, x'_1, y'_0, y'_1 are elements of 1236 F_p. 1238 For BLS48-581, Q = (x', y') is given by 1240 x' = x'_0 + x'_1 * u + x'_2 * v + x'_3 * u * v 1241 + x'_4 * w + x'_5 * u * w + x'_6 * v * w + x'_7 * u * v * w and 1242 y' = y'_0 + y'_1 * u + y'_2 * v + y'_3 * u * v 1243 + y'_4 * w + y'_5 * u * w + y'_6 * v * w + y'_7 * u * v * w, 1245 where u, v and w are indeterminates and x'_0, ..., x'_7 and y'_0, 1246 ..., y'_7 are elements of F_p. The representation of Q = (x', y') 1247 given below is followed by [I-D.draft-lwig-curve-representations]. 1249 BN462: 1251 Input x value: 0x21a6d67ef250191fadba34a0a30160b9ac9264b6f95f63b3edb 1252 ec3cf4b2e689db1bbb4e69a416a0b1e79239c0372e5cd70113c98d91f36b6980d 1254 Input y value: 0x0118ea0460f7f7abb82b33676a7432a490eeda842cccfa7d788 1255 c659650426e6af77df11b8ae40eb80f475432c66600622ecaa8a5734d36fb03de 1257 Input x'_0 value: 0x0257ccc85b58dda0dfb38e3a8cbdc5482e0337e7c1cd96ed 1258 61c913820408208f9ad2699bad92e0032ae1f0aa6a8b48807695468e3d934ae1e4 1259 df 1261 Input x'_1 value: 0x1d2e4343e8599102af8edca849566ba3c98e2a354730cbed 1262 9176884058b18134dd86bae555b783718f50af8b59bf7e850e9b73108ba6aa8cd2 1263 83 1265 Input y'_0 value: 0x0a0650439da22c1979517427a20809eca035634706e23c3f 1266 a7a6bb42fe810f1399a1f41c9ddae32e03695a140e7b11d7c3376e5b68df0db715 1267 4e 1269 Input y'_1 value: 0x073ef0cbd438cbe0172c8ae37306324d44d5e6b0c69ac57b 1270 393f1ab370fd725cc647692444a04ef87387aa68d53743493b9eba14cc552ca2a9 1271 3a 1273 e_0: 0x0cf7f0f2e01610804272f4a7a24014ac085543d787c8f8bf07059f93f87ba 1274 7e2a4ac77835d4ff10e78669be39cd23cc3a659c093dbe3b9647e8c 1276 e_1: 0x00ef2c737515694ee5b85051e39970f24e27ca278847c7cfa709b0df408b8 1277 30b3763b1b001f1194445b62d6c093fb6f77e43e369edefb1200389 1279 e_2: 0x04d685b29fd2b8faedacd36873f24a06158742bb2328740f93827934592d6 1280 f1723e0772bb9ccd3025f88dc457fc4f77dfef76104ff43cd430bf7 1282 e_3: 0x090067ef2892de0c48ee49cbe4ff1f835286c700c8d191574cb424019de11 1283 142b3c722cc5083a71912411c4a1f61c00d1e8f14f545348eb7462c 1285 e_4: 0x1437603b60dce235a090c43f5147d9c03bd63081c8bb1ffa7d8a2c31d6732 1286 30860bb3dfe4ca85581f7459204ef755f63cba1fbd6a4436f10ba0e 1288 e_5: 0x13191b1110d13650bf8e76b356fe776eb9d7a03fe33f82e3fe5732071f305 1289 d201843238cc96fd0e892bc61701e1844faa8e33446f87c6e29e75f 1291 e_6: 0x07b1ce375c0191c786bb184cc9c08a6ae5a569dd7586f75d6d2de2b2f0757 1292 87ee5082d44ca4b8009b3285ecae5fa521e23be76e6a08f17fa5cc8 1294 e_7: 0x05b64add5e49574b124a02d85f508c8d2d37993ae4c370a9cda89a100cdb5 1295 e1d441b57768dbc68429ffae243c0c57fe5ab0a3ee4c6f2d9d34714 1297 e_8: 0x0fd9a3271854a2b4542b42c55916e1faf7a8b87a7d10907179ac7073f6a1d 1298 e044906ffaf4760d11c8f92df3e50251e39ce92c700a12e77d0adf3 1300 e_9: 0x17fa0c7fa60c9a6d4d8bb9897991efd087899edc776f33743db921a689720 1301 c82257ee3c788e8160c112f18e841a3dd9a79a6f8782f771d542ee5 1303 e_10: 0x0c901397a62bb185a8f9cf336e28cfb0f354e2313f99c538cdceedf8b8aa 1304 22c23b896201170fc915690f79f6ba75581f1b76055cd89b7182041c 1306 e_11: 0x20f27fde93cee94ca4bf9ded1b1378c1b0d80439eeb1d0c8daef30db0037 1307 104a5e32a2ccc94fa1860a95e39a93ba51187b45f4c2c50c16482322 1309 BLS12-381: 1311 Input x value: 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14 1312 e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb 1314 Input y value: 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600d 1315 b18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1 1317 Input x'_0 value: 0x024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02 1318 b4510b647ae3d1770bac0326a805bbefd48056c8c121bdb8 1320 Input x'_1 value: 0x13e02b6052719f607dacd3a088274f65596bd0d09920b61a 1321 b5da61bbdc7f5049334cf11213945d57e5ac7d055d042b7e 1323 Input y'_0 value: 0x0ce5d527727d6e118cc9cdc6da2e351aadfd9baa8cbdd3a7 1324 6d429a695160d12c923ac9cc3baca289e193548608b82801 1326 Input y'_1 value: 0x0606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af 1327 267492ab572e99ab3f370d275cec1da1aaa9075ff05f79be 1329 e_0: 0x11619b45f61edfe3b47a15fac19442526ff489dcda25e59121d9931438907 1330 dfd448299a87dde3a649bdba96e84d54558 1332 e_1: 0x153ce14a76a53e205ba8f275ef1137c56a566f638b52d34ba3bf3bf22f277 1333 d70f76316218c0dfd583a394b8448d2be7f 1335 e_2: 0x095668fb4a02fe930ed44767834c915b283b1c6ca98c047bd4c272e9ac3f3 1336 ba6ff0b05a93e59c71fba77bce995f04692 1338 e_3: 0x16deedaa683124fe7260085184d88f7d036b86f53bb5b7f1fc5e248814782 1339 065413e7d958d17960109ea006b2afdeb5f 1341 e_4: 0x09c92cf02f3cd3d2f9d34bc44eee0dd50314ed44ca5d30ce6a9ec0539be7a 1342 86b121edc61839ccc908c4bdde256cd6048 1344 e_5: 0x111061f398efc2a97ff825b04d21089e24fd8b93a47e41e60eae7e9b2a38d 1345 54fa4dedced0811c34ce528781ab9e929c7 1347 e_6: 0x01ecfcf31c86257ab00b4709c33f1c9c4e007659dd5ffc4a735192167ce19 1348 7058cfb4c94225e7f1b6c26ad9ba68f63bc 1350 e_7: 0x08890726743a1f94a8193a166800b7787744a8ad8e2f9365db76863e894b7 1351 a11d83f90d873567e9d645ccf725b32d26f 1353 e_8: 0x0e61c752414ca5dfd258e9606bac08daec29b3e2c57062669556954fb227d 1354 3f1260eedf25446a086b0844bcd43646c10 1356 e_9: 0x0fe63f185f56dd29150fc498bbeea78969e7e783043620db33f75a05a0a2c 1357 e5c442beaff9da195ff15164c00ab66bdde 1359 e_10: 0x10900338a92ed0b47af211636f7cfdec717b7ee43900eee9b5fc24f0000c 1360 5874d4801372db478987691c566a8c474978 1362 e_11: 0x1454814f3085f0e6602247671bc408bbce2007201536818c901dbd4d2095 1363 dd86c1ec8b888e59611f60a301af7776be3d 1365 BLS48-581: 1367 Input x value: 0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61 1368 abdbaedffb9f7544550546a9df6f9645847665d859236ebdbc57db368b11786cb7 1369 4da5d3a1e6d8c3bce8732315af640 1371 Input y value: 0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e99 1372 1279dd41b720ef7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f 1373 37aef7b926b576dbb5de3e2587a70 1375 x'_0: 0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2e 1376 f156c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b797663221 1377 54dec34fd0b4ace8bfab 1379 x'_1: 0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da1230 1380 7f4e1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa 1381 143f1669b36676b47c57 1383 x'_2: 0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccba 1384 b5ab6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3 1385 f0b46488156ca55a3e6a 1387 x'_3: 0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f 1388 8be0cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80 1389 bc3f09a7033cbb7feafe 1391 x'_4: 0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c580 1392 5386699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d 1393 4cbb739c3a1c53f8cce5 1395 x'_5: 0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb0 1396 37418181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce 1397 3370f2004d914a3c093a 1399 x'_6: 0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0 1400 b7a449cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c 1401 3354e41607e60750e057 1403 x'_7: 0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf7417197 1404 28a7f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97 1405 c3f84e19da00fbc6ae34 1407 y'_0: 0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc4 1408 35faab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c 1409 0ff323edd3fe4d2d7971 1411 y'_1: 0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d7296473 1412 2fcbf3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ff 1413 c7b111471db936cd5665 1415 y'_2: 0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d37 1416 0514475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b 1417 8fde68332a526a2a8474 1419 y'_3: 0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e1 1420 22d2742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e5 1421 337316213da92841589d 1423 y'_4: 0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f11 1424 29857ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf 1425 7a43f47831f982e50137 1427 y'_5: 0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055a 1428 b7504fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226c 1429 f3a594eedc58cf90bee4 1431 y'_6: 0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c8 1432 19a6df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9a 1433 a62b3d41faeafeb23986 1435 y'_7: 0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8e 1436 ca9a9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e8406 1437 9c55d667ffcb732718b6 1439 e_0: 0x0e26c3fcb8ef67417814098de5111ffcccc1d003d15b367bad07cef2291a9 1440 3d31db03e3f03376f3beae2bd877bcfc22a25dc51016eda1ab56ee3033bc4b4fec 1441 5962f02dffb3af5e38e 1443 e_1: 0x069061b8047279aa5c2d25cdf676ddf34eddbc8ec2ec0f03614886fa828e1 1444 fc066b26d35744c0c38271843aa4fb617b57fa9eb4bd256d17367914159fc18b10 1445 a1085cb626e5bedb145 1447 e_2: 0x02b9bece645fbf9d8f97025a1545359f6fe3ffab3cd57094f862f7fb9ca01 1448 c88705c26675bcc723878e943da6b56ce25d063381fcd2a292e0e7501fe5727441 1449 84fb4ab4ca071a04281 1451 e_3: 0x0080d267bf036c1e61d7fc73905e8c630b97aa05ef3266c82e7a111072c0d 1452 2056baa8137fba111c9650dfb18cb1f43363041e202e3192fced29d2b0501c8825 1453 43fb370a56bfdc2435b 1455 e_4: 0x03c6b4c12f338f9401e6a493a405b33e64389338db8c5e592a8dd79eac772 1456 0dd83dd6b0c189eeda20809160cd57cdf3e2edc82db15f553c1f6c953ea27114cb 1457 6bd8a38e273f407dae0 1459 e_5: 0x016e46224f28bfd8833f76ac29ee6e406a9da1bde55f5e82b3bd977897a91 1460 04f18b9ee41ea9af7d4183d895102950a12ce9975669db07924e1b432d9680f5ce 1461 7e5c67ed68f381eba45 1463 e_6: 0x008ddce7a4a1b94be5df3ceea56bef0077dcdde86d579938a50933a47296d 1464 337b7629934128e2457e24142b0eeaa978fd8e70986d7dd51fccbbeb8a1933434f 1465 ec4f5bc538de2646e90 1467 e_7: 0x060ef6eae55728e40bd4628265218b24b38cdd434968c14bfefb87f0dcbfc 1468 76cc473ae2dc0cac6e69dfdf90951175178dc75b9cc08320fcde187aa58ea047a2 1469 ee00b1968650eec2791 1471 e_8: 0x0c3943636876fd4f9393414099a746f84b2633dfb7c36ba6512a0b48e66dc 1472 b2e409f1b9e150e36b0b4311165810a3c721525f0d43a021f090e6a27577b42c7a 1473 57bed3327edb98ba8f8 1475 e_9: 0x02d31eb8be0d923cac2a8eb6a07556c8951d849ec53c2848ee78c5eed4026 1476 2eb21822527a8555b071f1cd080e049e5e7ebfe2541d5b42c1e414341694d6f16d 1477 287e4a8d28359c2d2f9 1479 e_10: 0x07f19673c5580d6a10d09a032397c5d425c3a99ff1dd0abe5bec40a0d47a 1480 6b8daabb22edb6b06dd8691950b8f23faefcdd80c45aa3817a840018965941f424 1481 7f9f97233a84f58b262e 1483 e_11: 0x0d3fe01f0c114915c3bdf8089377780076c1685302279fd9ab12d07477aa 1484 c03b69291652e9f179baa0a99c38aa8851c1d25ffdb4ded2c8fe8b30338c144286 1485 07d6d822610d41f51372 1487 e_12: 0x0662eefd5fab9509aed968866b68cff3bc5d48ecc8ac6867c212a2d82cee 1488 5a689a3c9c67f1d611adac7268dc8b06471c0598f7016ca3d1c01649dda4b43531 1489 cffc4eb41e691e27f2eb 1491 e_13: 0x0aad8f4a8cfdca8de0985070304fe4f4d32f99b01d4ea50d9f7cd2abdc0a 1492 eea99311a36ec6ed18208642cef9e09b96795b27c42a5a744a7b01a617a91d9fb7 1493 623d636640d61a6596ec 1495 e_14: 0x0ffcf21d641fd9c6a641a749d80cab1bcad4b34ee97567d905ed9d5cfb74 1496 e9aef19674e2eb6ce3dfb706aa814d4a228db4fcd707e571259435393a27cac68b 1497 59a1b690ae8cde7a94c3 1499 e_15: 0x0cbe92a53151790cece4a86f91e9b31644a86fc4c954e5fa04e707beb69f 1500 c60a858fed8ebd53e4cfd51546d5c0732331071c358d721ee601bfd3847e0e9041 1501 01c62822dd2e4c7f8e5c 1503 e_16: 0x0202db83b1ff33016679b6cfc8931deea6df1485c894dcd113bacf564411 1504 519a42026b5fda4e16262674dcb3f089cd7d552f8089a1fec93e3db6bca43788cd 1505 b06fc41baaa5c5098667 1507 e_17: 0x070a617ed131b857f5b74b625c4ef70cc567f619defb5f2ab67534a1a8aa 1508 72975fc4248ac8551ce02b68801703971a2cf1cb934c9c354cadd5cfc4575cde8d 1509 bde6122bd54826a9b3e9 1511 e_18: 0x070e1ebce457c141417f88423127b7a7321424f64119d5089d883cb95328 1512 3ee4e1f2e01ffa7b903fe7a94af4bb1acb02ca6a36678e41506879069cee11c9dc 1513 f6a080b6a4a7c7f21dc9 1515 e_19: 0x058a06be5a36c6148d8a1287ee7f0e725453fa1bb05cf77239f235b41712 1516 7e370cfa4f88e61a23ea16df3c45d29c203d04d09782b39e9b4037c0c4ac8e8653 1517 e7c533ad752a640b233e 1519 e_20: 0x0dfdfaaeb9349cf18d21b92ad68f8a7ecc509c35fcd4b8abeb93be7a204a 1520 c871f2195180206a2c340fccb69dbc30b9410ed0b122308a8fc75141f673ae5ec8 1521 2b6a45fc2d664409c6b6 1523 e_21: 0x0d06c8adfdd81275da2a0ce375b8df9199f3d359e8cf50064a3dc10a5924 1524 17124a3b705b05a7ffe78e20f935a08868ecf3fc5aba0ace7ce4497bb59085ca27 1525 7c16b3d53dd7dae5c857 1527 e_22: 0x0708effd28c4ae21b6969cb9bdd0c27f8a3e341798b6f6d4baf27be259b4 1528 a47688b50cb68a69a917a4a1faf56cec93f69ac416512c32e9d5e69bd8836b6c2b 1529 a9c6889d507ad571dbc4 1531 e_23: 0x09da7c7aa48ce571f8ece74b98431b14ae6fb4a53ae979cd6b2e82320e8d 1532 25a0ece1ca1563aa5aa6926e7d608358af8399534f6b00788e95e37ef1b549f43a 1533 58ad250a71f0b2fdb2bf 1535 e_24: 0x0a7150a14471994833d89f41daeaa999dfc24a9968d4e33d88ed9e9f07aa 1536 2432c53e486ba6e3b6e4f4b8d9c989010a375935c06e4b8d6c31239fad6a61e264 1537 7b84a0e3f76e57005ff7 1539 e_25: 0x084696f31ff27889d4dccdc4967964a5387a5ae071ad391c5723c9034f16 1540 c2557915ada07ec68f18672b5b2107f785c15ddf9697046dc633b5a23cc0e442d2 1541 8ef6eea9915d0638d4d8 1543 e_26: 0x0398e76e3d2202f999ac0f73e0099fe4e0fe2de9d223e78fc65c56e209cd 1544 f48f0d1ad8f6093e924ce5f0c93437c11212b7841de26f9067065b1898f48006bc 1545 c6f2ab8fa8e0b93f4ba4 1547 e_27: 0x06d683f556022368e7a633dc6fe319fd1d4fc0e07acff7c4d4177e83a911 1548 e73313e0ed980cd9197bd17ac45942a65d90e6cb9209ede7f36c10e009c9d337ee 1549 97c4068db40e34d0e361 1551 e_28: 0x0d764075344b70818f91b13ee445fd8c1587d1c0664002180bbac9a396ad 1552 4a8dc1e695b0c4267df4a09081c1e5c256c53fd49a73ffc817e65217a44fc0b20e 1553 f5ee92b28d4bc3e38576 1555 e_29: 0x0aa6a32fdc4423b1c6d43e5104159bcd8e03a676d055d4496f7b1bc87611 1556 64a2908a3ff0e4c4d1f4362015c14824927011e2909531b8d87ee0acd676e7221a 1557 1ca1c21a33e2cf87dc51 1559 e_30: 0x1147719959ac8eeab3fc913539784f1f947df47066b6c0c1beafecdb5fa7 1560 84c3be9de5ab282a678a2a0cbef8714141a6c8aaa76500819a896b46af20509953 1561 495e2a85eff58348b38d 1563 e_31: 0x11a377bcebd3c12702bb34044f06f8870ca712fb5caa6d30c48ace96898f 1564 cbcddbcf31f331c9e524684c02c90db7f30b9fc470d6e651a7e8b1f684383f3705 1565 d7a47a1b4fe463d623c8 1567 e_32: 0x0b8b4511f451ba2cc58dc28e56d5e1d0a8f557ecb242f4d994a627e07cf3 1568 fa44e6d83cb907deacf303d2f761810b5d943b46c4383e1435ec23fec196a70e33 1569 946173c78be3c75dfc83 1571 e_33: 0x090962d632ee2a57ce4208052ce47a9f76ea0fdad724b7256bb07f3944e9 1572 639a981d3431087241e30ae9bf5e2ea32af323ce7ed195d383b749cb25bc09f678 1573 d385a49a0c09f6d9efca 1575 e_34: 0x0931c7befc80acd185491c68af886fa8ee39c21ed3ebd743b9168ae3b298 1576 df485bfdc75b94f0b21aecd8dca941dfc6d1566cc70dc648e6ccc73e4cbf2a1ac8 1577 3c8294d447c66e74784d 1579 e_35: 0x020ac007bf6c76ec827d53647058aca48896916269c6a2016b8c06f01309 1580 01c8975779f1672e581e2dfdbcf504e96ecf6801d0d39aad35cf79fbe7fe193c6c 1581 882c15bce593223f0c7c 1583 e_36: 0x0c0aed0d890c3b0b673bf4981398dcbf0d15d36af6347a39599f3a225841 1584 84828f78f91bbbbd08124a97672963ec313ff142c456ec1a2fc3909fd4429fd699 1585 d827d48777d3b0e0e699 1587 e_37: 0x0ef7799241a1ba6baaa8740d5667a1ace50fb8e63accc3bc30dc07b11d78 1588 dc545b68910c027489a0d842d1ba3ac406197881361a18b9fe337ff22d730fa44a 1589 fabb9f801f759086c8e4 1591 e_38: 0x016663c940d062f4057257c8f4fb9b35e82541717a34582dd7d55b41ebad 1592 f40d486ed74570043b2a3c4de29859fdeae9b6b456cb33bb401ecf38f968564669 1593 2300517e9b035d6665fc 1595 e_39: 0x1184a79510edf25e3bd2dc793a5082fa0fed0d559fa14a5ce9ffca4c61f1 1596 7196e1ffbb84326272e0d079368e9a735be1d05ec80c20dc6198b50a22a765defd 1597 c151d437335f1309aced 1599 e_40: 0x120e47a747d942a593d202707c936dafa6fed489967dd94e48f317fd3c88 1600 1b1041e3b6bbf9e8031d44e39c1ab5ae41e487eac9acd90e869129c38a8e6c97cf 1601 55d6666d22299951f91a 1603 e_41: 0x026b6e374108ecb2fe8d557087f40ab7bac8c5af0644a655271765d57ad7 1604 1742aa331326d871610a8c4c30ccf5d8adbeec23cdff20d9502a5005fce2593caf 1605 0682c82e4873b89d6d71 1607 e_42: 0x041be63a2fa643e5a66faeb099a3440105c18dca58d51f74b3bf281da4e6 1608 89b13f365273a2ed397e7b1c26bdd4daade710c30350318b0ae9a9b16882c29fe3 1609 1ca3b884c92916d6d07a 1611 e_43: 0x124018a12f0f0af881e6765e9e81071acc56ebcddadcd107750bd8697440 1612 cc16f190a3595633bb8900e6829823866c5769f03a306f979a3e039e620d6d2f57 1613 6793d36d840b168eeedd 1615 e_44: 0x0d422de4a83449c535b4b9ece586754c941548f15d50ada6740865be9c0b 1616 066788b6078727c7dee299acc15cbdcc7d51cdc5b17757c07d9a9146b01d2fdc7b 1617 8c562002da0f9084bde5 1619 e_45: 0x1119f6c5468bce2ec2b450858dc073fea4fb05b6e83dd20c55c9cf694cbc 1620 c57fc0effb1d33b9b5587852d0961c40ff114b7493361e4cfdff16e85fbce66786 1621 9b6f7e9eb804bcec46db 1623 e_46: 0x061eaa8e9b0085364a61ea4f69c3516b6bf9f79f8c79d053e646ea637215 1624 cf6590203b275290872e3d7b258102dd0c0a4a310af3958165f2078ff9dc3ac9e9 1625 95ce5413268d80974784 1627 e_47: 0x0add8d58e9ec0c9393eb8c4bc0b08174a6b421e15040ef558da58d241e5f 1628 906ad6ca2aa5de361421708a6b8ff6736efbac6b4688bf752259b4650595aa395c 1629 40d00f4417f180779985 1631 Authors' Addresses 1633 Yumi Sakemi 1634 Lepidum 1636 Email: yumi.sakemi@lepidum.co.jp 1638 Tetsutaro Kobayashi 1639 NTT 1641 Email: tetsutaro.kobayashi.dr@hco.ntt.co.jp 1643 Tsunekazu Saito 1644 NTT 1646 Email: tsunekazu.saito.hg@hco.ntt.co.jp