idnits 2.17.1 draft-kato-threat-pairing-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 : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet has text resembling RFC 2119 boilerplate text. -- The document date (March 18, 2018) is 2230 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 ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Kato 3 Internet-Draft NTT TechnoCross Corporation 4 Intended status: Experimental T. Kobayashi 5 Expires: September 19, 2018 Y. Kawahara 6 T. Kim 7 T. Saito 8 NTT 9 March 18, 2018 11 The threat of Pairing based cryptographic protocols. 12 draft-kato-threat-pairing-01 14 Abstract 16 Pairing is a special map from two elliptic curves that called 17 Pairing-friendly curves to a finite field and is useful mathematical 18 tools for constructing cryptographic primitives. 20 At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field 21 sieve algorithm for the discrete logarithm problem in a finite field. 22 The security of pairing-based cryptography is based on the difficulty 23 in solving the DLP. Hence, it has become necessary to shift the 24 parameters that the DLP is computationally infeasible against the 25 efficient number field sieve algorithms. 27 This memo introduce Optimal Ate Pairing and two pairing-friendly 28 curves with parameters of pairing against efficient number field 29 sieve algorithms. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at https://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on September 19, 2018. 48 Copyright Notice 50 Copyright (c) 2018 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (https://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.1. Requirements Terminology . . . . . . . . . . . . . . . . 3 67 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 4 68 2.1. Elliptic Curve . . . . . . . . . . . . . . . . . . . . . 4 69 2.2. Bilinear Map . . . . . . . . . . . . . . . . . . . . . . 4 70 3. Pairing-friend curves and Domain Parameter Specification . . 5 71 3.1. Notation for Domain Parameters . . . . . . . . . . . . . 5 72 3.2. Efficient Domain Parameters for BN462 . . . . . . . . . . 7 73 3.2.1. Domain Parameters by Beuchat et al. . . . . . . . . . 7 74 3.3. Efficient Domain Parameters for BLS48 . . . . . . . . . . 9 75 3.3.1. Domain Parameters by Kiyomura et al. . . . . . . . . 9 76 4. Optimal Ate Pairing . . . . . . . . . . . . . . . . . . . . . 12 77 4.1. Guide for Decision on Parameters for Optimal Ate Pairing 13 78 4.2. Miller Loop . . . . . . . . . . . . . . . . . . . . . . . 14 79 4.3. Straight Line Function . . . . . . . . . . . . . . . . . 15 80 5. Algorithm Identifiers . . . . . . . . . . . . . . . . . . . . 15 81 6. Security Considerations . . . . . . . . . . . . . . . . . . . 15 82 6.1. 128-bit Secure PFC . . . . . . . . . . . . . . . . . . . 16 83 6.2. 256-bit Secure PFC . . . . . . . . . . . . . . . . . . . 16 84 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 17 85 8. Change log . . . . . . . . . . . . . . . . . . . . . . . . . 17 86 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 17 87 9.1. Normative References . . . . . . . . . . . . . . . . . . 17 88 9.2. Informative References . . . . . . . . . . . . . . . . . 17 89 Appendix A. Test Vectors of Optimal Ate Pairing . . . . . . . . 19 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 92 1. Introduction 94 Pairing is a special map from two elliptic curves that called Pairing 95 friendly curves (PFCs) to a finite field and is useful mathematical 96 tools for constructing cryptographic primitives. It allows us to 97 construct powerful primitives like Identity-Based Encryption (IBE) 98 [5] and Functional Encryption (FE) [6]. The IBE and FE provide a 99 rich decryption condition. Some Pairing-Based Cryptography is 100 specified in IETF. (e.g. [3] and [4]) 102 There are some types of pairing[14] and its choice has an impact on 103 the performance of the primitive. For example, primitives by using 104 Tate Pairing [3] and Ate Pairing [4] are specified in IETF. 106 We need to choose an appropriate type of elliptic curve and 107 parameters for the pairing-based cryptographic schemes, because the 108 choice has great impact on security and efficiency of these schemes. 109 However, an RFC on elliptic curves with pairings has not yet been 110 provided in the IETF. 112 In some open source softwares ([7], [8], and [9]) are implemented by 113 Optimal Ate Pairing which is an improvement of Ate Pairing with 114 254-bit prime order Barreto and Naehrig curve. 116 At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field 117 sieve(NSF) algorithm for the discrete logarithm problem in a finite 118 field[11]. The security of pairing-based cryptography is based on 119 the difficulty in solving the DLP. Hence, it has become necessary to 120 shift the parameters that the DLP is computationally infeasible 121 against the efficient NSF algorithms. 123 This memo introduce Optimal Ate Pairing [2] for two PFCs to be able 124 to shift the parameters. It enables us to reduce the cost for 125 describing the body of Optimal Ate Pairing when Optimal Ate Pairing 126 is specified over additional curves in IETF. Furthermore, this memo 127 provides concrete algorithm for Optimal Ate Pairing over BLS-curves 128 Section 3 and its test vectors. This memo is expected to use by 129 combining Optimal Ate Pairing with a suitable PFC for a primitive in 130 order to realize same functional structure of ECDSA and ECDH. (i.e., 131 DSA over elliptic curve and DH over elliptic curve) 133 1.1. Requirements Terminology 135 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 136 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 137 memo are to be interpreted as described in [1]. 139 2. Preliminaries 141 In this section, we introduce the definition of elliptic curve and 142 bilinear map, notation used in this memo. 144 2.1. Elliptic Curve 146 Throughout this memo, let p > 3 be a prime, q = p^n, and n be a 147 natural number. Also, let F_q be a finite field. The curve defined 148 by the following equation E is called an elliptic curve. 150 E : y^2 = x^3 + A * x + B such that A, B are in F_q, 151 4 * A^3 + 27 * B^2 != 0 mod F_q 153 Solutions (x, y) for an elliptic curve E, as well as the point at 154 infinity, are called F_q-rational points. The additive group is 155 constructed by an well-defined operation in the set of F_q-rational 156 points. Typically, the cyclic additive group with prime order r and 157 the base point G in its group is used for the cryptographic 158 applications. Furthermore, we define terminology used in this memo 159 as follows. 161 O_E: the point at infinity over elliptic curve E. 163 #E(F_q): number of points on an elliptic curve E over F_q. 165 cofactor h: h = #E(F_p)/r. 167 embedding degree k: minimum integer k such that r is a divisor of 168 q^k - 1 170 2.2. Bilinear Map 172 Let G_1 be an additive group of prime order r and let G_2 and G_3 be 173 additive and multiplicative groups, respectively, of the same order. 174 Let P, Q be generators of G_1, G_2 respectively. We say that (G_1, 175 G_2, G_3) are asymmetric bilinear map groups if there exists a 176 bilinear map e: (G_1, G_2) -> G_3 satisfying the following 177 properties: 179 (1) Bilinearity: for any S in G_1, for any T in G_2, for any a, b in 180 Z_r, we have the relation e([a]S, [b]T) = e(S, T)^{a * b}. 182 (2) Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S = 183 O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T 184 = O_E. 186 (3) Computability: for any S in G_1, for any T in G_2, the bilinear 187 map is efficiently computable. 189 3. Pairing-friend curves and Domain Parameter Specification 191 In this section, this memo specifies the domain parameters for 192 128-bit and 256-bit secure elliptic curves which allow us to 193 efficiently compute the operation of a pairing at appropriate levels 194 of security. 196 We introduce 462-bit Barreto Naehrig (BN462)[13] curve as 128-bit 197 secure elliptic curve and 581-bit Barreto Lynn Scott (BLS48)[12]. 198 curve as 256-bit secure elliptic curve. 200 3.1. Notation for Domain Parameters 202 Here, we define notations for specifying domain parameters and 203 explain types of pairing friendly curves. 205 The elliptic curves E over F_p satisfy following equation. 207 y^2 = x^3 + B for B in F_p 209 These domain parameters are described in the following way. 211 For the elliptic curve E(F_p) on BN462 213 G1-Curve-ID is an identifier of the G_1 curve with which the curve 214 can be referenced. 216 p_b is a prime specifying a base field F_p. 218 B is the coefficient of the equation y^2 = x^3 + B mod p defining 219 E. 221 G = (x, y) is the base point, i.e., a point with x and y being its 222 x- and y-coordinates in E, respectively. 224 r is the prime order of the group generated by G. 226 h is the cofactor of G in E(F_p) 228 For twisted curve E'(F_{p^2}) on BN462 230 G2-Curve-ID is an identifier of the G_2 curve with which the curve 231 can be referenced. 233 p_b is a prime specifying a base field. 235 B' is the coefficient of the equation y'^2 = x'^3 + B' mod F_p^2 236 defining E'. 238 G' = (x', y') is the base point, i.e., a point with x' and y' 239 being its x'- and y'-coordinates in E', respectively. 241 r' is the prime order of the group generated by G'. 243 h' is the cofactor of r' in #E'(F_{p^2}) 245 For F_{p^12}^* on BN462 247 G3-Field-ID is an identifier of the F_{p^12}^*. 249 p_b is a prime specifying base field. 251 r'' is the prime order of the group. 253 h'' is the cofactor of r in F_{p^12}^* s.t. h'' = h''_1 * h''_2 255 h''_1 is the part of cofactor of r in F_{p^12}^* s.t. h''_1 = (p^4 256 - p^2 + 1)/r 258 h''_2 is the part of cofactor of r in F_{p^12}^* s.t. h''_2 = (p^6 259 - 1) * (p^2 + 1) 261 For the elliptic curve E(F_p) on BLS48 263 G1-Curve-ID is an identifier of the G_1 curve with which the curve 264 can be referenced. 266 p_b is a prime specifying a base field F_p. 268 B is the coefficient of the equation y^2 = x^3 + B mod p defining 269 E. 271 G = (x, y) is the base point, i.e., a point with x and y being its 272 x- and y-coordinates in E, respectively. 274 r is the prime order of the group generated by G. 276 h is the cofactor of G in E(F_p) 278 For twisted curve E'(F_{p^8}) on BLS48 280 G2-Curve-ID is an identifier of the G_2 curve with which the curve 281 can be referenced. 283 p_b' is a prime specifying a base field. 285 B' is the coefficient of the equation y'^2 = x'^3 + B' mod F_p^2 286 defining E'. 288 G' = (x', y') is the base point, i.e., a point with x' and y' 289 being its x'- and y'-coordinates in E', respectively. 291 r' is the prime order of the group generated by G'. 293 h' is the cofactor of r' in #E'(F_{p^8}). 295 For F_{p^48}^* on BLS48 297 G3-Field-ID is an identifier of the F_{p^48}^*. 299 p_b is a prime specifying a base field. 301 r'' is the prime order of the group generated by G'. 303 h'' is the cofactor of r' in #E'(F_{p^48}). 305 For the definition of the pairing parameter 307 Pairing-Param-ID is the set of the identifiers G1-Curve-ID, G2- 308 Curve-ID and G3-Field-ID. 310 3.2. Efficient Domain Parameters for BN462 312 This section specifies the domain parameters for four 128-bit secure 313 elliptic curves BN462. 315 3.2.1. Domain Parameters by Beuchat et al. 317 The domain parameters described in this subsection are defined by 318 elliptic curve E(F_p) : y^2 = x^3 + 5 and sextic twist E'(F_{p^2}) : 319 x'^3 + 5/s = x'^3 + 2 - u, where F_{p^2} = F_p[u]/(u^2 + 1), F_{p^6} 320 = F_{p^2}[v]/(v^3 - u), F_{p^12} = F_{p^6}[w]/(w^2 - v), s = - 5/u. 321 We describe domain parameters of elliptic curves E and E'. The 322 parameter p_b is 1 mod 8. 324 G1-Curve-ID: Fp462nBN 326 p_b = 0x240480360120023ffffffffff6ff0cf6b7d9bfca000000 327 0000d812908f41c8020ffffffffff6ff66fc6ff687f640000 328 000002401b00840138013 329 x = 0x21a6d67ef250191fadba34a0a30160b9ac9264b6f95f 330 63b3edbec3cf4b2e689db1bbb4e69a416a0b1e79239c037 331 2e5cd70113c98d91f36b6980d 333 y = 0x0118ea0460f7f7abb82b33676a7432a490eeda842ccc 334 fa7d788c659650426e6af77df11b8ae40eb80f475432c666 335 00622ecaa8a5734d36fb03de; 337 r = 0x240480360120023ffffffffff6ff0cf6b7d9bfca000000 338 0000d812908ee1c201f7fffffffff6ff66fc7bf717f7c000 339 0000002401b007e010800d 341 h = 1 343 G2-Curve-ID: Fp462n2BN 345 p_b = 0x240480360120023ffffffffff6ff0cf6b7d9bfca000000 346 0000d812908f41c8020ffffffffff6ff66fc6ff687f640000 347 000002401b00840138013 349 B' = 2 - u 351 x' = 0x1d2e4343e8599102af8edca849566ba3c98e2a354730cb 352 ed9176884058b18134dd86bae555b783718f50af8b59bf7e 353 850e9b73108ba6aa8cd283*u + 354 0x257ccc85b58dda0dfb38e3a8cbdc5482e0337e7c1cd9 355 6ed61c913820408208f9ad2699bad92e0032ae1f0aa6a8b4 356 8807695468e3d934ae1e4df 358 y' = 0x73ef0cbd438cbe0172c8ae37306324d44d5e6b0c69ac5 359 7b393f1ab370fd725cc647692444a04ef87387aa68d53743 360 493b9eba14cc552ca2a93a*u + 361 0xa0650439da22c1979517427a20809eca035634706e23c3f 362 a7a6bb42fe810f1399a1f41c9ddae32e03695a140e7b11d 363 7c3376e5b68df0db7154e 365 r' = r 367 h' = 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000 368 d812908fa1ce0227fffffffff6ff66fc63f5f7f4c000000000 369 2401b008a0168019 371 G3-Field-ID: Fp462n12 373 p_b = 0x240480360120023ffffffffff6ff0cf6b7d9bfca000000 374 0000d812908f41c8020ffffffffff6ff66fc6ff687f640000 375 000002401b00840138013 376 r'' = r 378 h'' = (TBD) 380 h''_1 = (TBD) 382 h''_2 = (TBD) 384 Pairing-Param-ID: Fp462BN = { 385 G1-Curve-ID: Fp462nBN 386 G2-Curve-ID: Fp462n2BN 387 G3-Field-ID: Fp462n12BN 388 } 390 3.3. Efficient Domain Parameters for BLS48 392 This section specifies the domain parameters for four 256-bit secure 393 elliptic curves BLS48. 395 3.3.1. Domain Parameters by Kiyomura et al. 397 The domain parameters described in this subsection are defined by 398 elliptic curve E(F_p) : y^2 = x^3 + 1 and following tower structures 399 E'(F_{p^8}) : y^2 = x^3 -1/w, where F_{p^2} = F_p[u]/(u^2 + 1), 400 F_{p^4} = F_{p^2}[v]/(v^2 + u + 1), F_{p^8} = F_{p^4}[w]/(w^2 + v), 401 F_{p^24} = F_{p^8}[z]/(z^3 + w), F_{p^48} = F_{p^24}[s]/(s^2 + z). 403 G1-Curve-ID: Fp581nBLS48 405 p_b = 406 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444 407 a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac 408 3ed c154e6565912b 410 x = 0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdba 411 edffb9f7544550546a9df6f9645847665d859236ebdbc57db368b11786cb 412 74da5d3a1e6d8c3bce8732315af640 414 y = 0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279d 415 d41b720ef7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35 416 f37aef7b926b576dbb5de3e2587a70 418 r = 0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972 419 c2e6e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd6 420 71c01 422 h = 0x85555841aaaec4ac 423 G2-Curve-ID: Fp581n8BLS48 425 p_b' = 426 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444 427 a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac 428 3ed c154e6565912b 430 x' = 0x827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf 431 741719728a7f9f8cfca93f29cff364a7190b7e2b0d4585479bd6ae 432 bf9fc44e56af2fc9e97c3f84e19da00fbc6ae34*u*v*w + b9b795 433 1c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0b 434 7a449cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d633 435 34b5b0e205c3354e41607e60750e057*v*w + c96c7797eb073860 436 3f1311e4ecda088f7b8f35dcef0977a3d1a58677bb037418181df6 437 3835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fc 438 e3370f2004d914a3c093a*u*w + 38b91c600b35913a3c598e4caa 439 9dd63007c675d0b1642b5675ff0e7c5805386699981f9e48199d5a 440 c10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb739c3 441 a1c53f8cce5*w + be2218c25ceb6185c78d8012954d4bfe8f5985 442 ac62f3e5821b7b92a393f8be0cc218a95f63e1c776e6ec143b1b27 443 9b9468c31c5257c200ca52310b8cb4e80bc3f09a7033cbb7feafe *u*v + 444 1fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca 445 7a6d6957ccbab5ab6860161c1dbd19242ffae766f0d2a6d55f028c 446 bdfbb879d5fea8ef4cded6b3f0b46488156ca55a3e6a*v + 7c497 447 3ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da1230 448 7f4e1c3943a00abfedf16214a76affa62504f0c3c7630d979630ff 449 d75556a01afa143f1669b36676b47c57*u + 5d615d9a7871e4a38 450 237fa45a2775debabbefc70344dbccb7de64db3a2ef156c46ff79b 451 aad1a8c42281a63ca0612f400503004d80491f510317b797663221 452 54dec34fd0b4ace8bfab 454 y' = 0x35e2524ff89029d393a5c07e84f981b5e068f1406be8e50c8754 455 9b6ef8eca9a9533a3f8e69c31e97e1ad0333ec719205417300d8c4 456 ab33f748e5ac66e84069c55d667ffcb732718b6*u*v*w + 896767 457 811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c81 458 9a6df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc 459 9e884017d9aa62b3d41faeafeb23986*v*w + 7d0d03745736b7a5 460 13d339d5ad537b90421ad66eb16722b589d82e2055ab7504fa8342 461 0e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226 462 cf3a594eedc58cf90bee4*u*w + d209d5a223a9c46916503fa5a8 463 8325a2554dc541b43dd93b5a959805f1129857ed85c77fa238cdce 464 8a1e2ca4e512b64f59f430135945d137b08857fdddfcf7a43f4783 465 1f982e50137*w + aec25a4621edc0688223fbbd478762b1c2cded 466 3360dcee23dd8b0e710e122d2742c89b224333fa40dced28177427 467 70ba10d67bda503ee5e578fb3d8b8a1e5337316213da92841589d *u*v + 468 b36a201dd008523e421efb70367669ef2c2fc5030216d5b 469 119d3a480d370514475f7d5c99d0e90411515536ca3295e5e2f0c1 470 d35d51a652269cbc7c46fc3b8fde68332a526a2a8474*v + 284dc 471 75979e0ff144da6531815fcadc2b75a422ba325e6fba01d7296473 472 2fcbf3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e 473 588b423525ffc7b111471db936cd5665*u + eb53356c375b5dfa4 474 97216452f3024b918b4238059a577e6f3b39ebfc435faab0906235 475 afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c0 476 ff323edd3fe4d2d7971 478 r' = r 480 h' = 0x170e915cb0a6b7406b8d94042317f811d6bc3fc6e211ada42e 481 58ccfcb3ac076a7e4499d700a0c23dc4b0c078f92def8c87b7 482 fe63e1eea270db353a4ef4d38b5998ad8f0d042ea24c8f02be 483 1c0c83992fe5d7725227bb27123a949e0876c0a8ce0a67326d 484 b0e955dcb791b867f31d6bfa62fbdd5f44a00504df04e186fa 485 e033f1eb43c1b1a08b6e086eff03c8fee9ebdd1e191a8a4b04 486 66c90b389987de5637d5dd13dab33196bd2e5afa6cd19cf0fc 487 3fc7db7ece1f3fac742626b1b02fcee04043b2ea96492f6afa 488 51739597c54bb78aa6b0b99319fef9d09f768831018ee6564c 489 68d054c62f2e0b4549426fec24ab26957a669dba2a2b6945ce 490 40c9aec6afdeda16c79e15546cd7771fa544d5364236690ea0 491 6832679562a68731420ae52d0d35a90b8d10b688e31b6aee45 492 f45b7a5083c71732105852decc888f64839a4de33b99521f09 493 84a418d20fc7b0609530e454f0696fa2a8075ac01cc8ae3869 494 e8d0fe1f3788ffac4c01aa2720e431da333c83d9663bfb1fb7 495 a1a7b90528482c6be7892299030bb51a51dc7e91e915687441 496 6bf4c26f1ea7ec578058563960ef92bbbb8632d3a1b695f954 497 af10e9a78e40acffc13b06540aae9da5287fc4429485d44e62 498 89d8c0d6a3eb2ece35012452751839fb48bc14b515478e2ff4 499 12d930ac20307561f3a5c998e6bcbfebd97effc6433033a236 500 1bfcdc4fc74ad379a16c6dea49c209b1 502 G3-Field-ID: Fp581n48BLS48 504 p_b = 505 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444 506 a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac 507 3ed c154e6565912b 509 r'' = 510 0x33325e51b8485cacb1cf7e79521a2c07ed618593bc2b823693827cddd501 412 511 8f299770734d9658ec3da72c829e2bfdfa5bc0dcac0f0dd385da0b70a1f1800f3 512 920706ac684379b30abec1422f3428ce3b9ea1d92e0995ded30bb3f127dd47570d 513 12 1a8200c4091f4c1a039e4dea3f3e733d60d4788b3a2db1954fa31287ef5b2f8 514 d31c9 b5f5107074dc917ffa3ebef388907b3e2400a0108fb4b983592be1718c4a 515 206f401d 2fd25126d86f05bd447da88d3240e4ebfd3c06ffacd5a6035b8599108 516 3e27f7ec56e 001b64a11949e1c61fca24a0634794818600eebf30801a216d1dc7 517 e2ac05b743e9bd 89e033b09757a9e3f9dd4bcdfd8c7ca6e2b5c39833111583a14 518 a800b430ae5ea8a3c 6ab3ad627523d1e7dedcf79a56483a81cf6a6deb7505ed45 519 dc8a3d557237ef0f98ac 7ca9e577d5c7d429fdbdc87a0a0b056dd44b9c8ae1432 520 ac96dde432512ea1782c476 727732b7ace3a30d90fd4ad586edd8ee2b5b10e3cf 521 f6cc31e9137f98d3debad7ca51 2af4f876915edb46c3d5d51c4c3c7e268727ab9 522 14ae89f05c7a7f9fa1df8ee053622 b60033bc7970f902d6a9ebc1b6ff316d5457 523 cdbd926cf183a6114ae6448650286067 ababbd5d747a5117b691e1e7138f2e4f8 524 d8025df47f695681f0555463005c211ac9c 52c56b7c96d4dbc30e86bcb3c7013d 525 e1913fa60e2e58f1877fa6bd690f7f37858d69 9dcc083c27cd1837efb00d0bdda 526 265e73adca2760f99d911463fa51614aaf308a54f 46a15f08ad24c378210c60aa 527 64ff1772ec3d6d84fcaadd697aef4f87423b215d4ab9 aee8f260865b1 529 h'' = 530 0x170e915cb0a6b7406b8d94042317f811d6bc3fc6e211ada42e58ccfcb3ac 076 531 a7e4499d700a0c23dc4b0c078f92def8c87b7fe63e1eea270db353a4ef4d38b59 532 98ad8f0d042ea24c8f02be1c0c83992fe5d7725227bb27123a949e0876c0a8ce0a 533 67 326db0e955dcb791b867f31d6bfa62fbdd5f44a00504df04e186fae033f1eb4 534 3c1b1 a08b6e086eff03c8fee9ebdd1e191a8a4b0466c90b389987de5637d5dd13 535 dab33196 bd2e5afa6cd19cf0fc3fc7db7ece1f3fac742626b1b02fcee04043b2e 536 a96492f6afa 51739597c54bb78aa6b0b99319fef9d09f768831018ee6564c68d0 537 54c62f2e0b4549 426fec24ab26957a669dba2a2b6945ce40c9aec6afdeda16c79 538 e15546cd7771fa544 d5364236690ea06832679562a68731420ae52d0d35a90b8d 539 10b688e31b6aee45f45b 7a5083c71732105852decc888f64839a4de33b99521f0 540 984a418d20fc7b0609530e4 54f0696fa2a8075ac01cc8ae3869e8d0fe1f3788ff 541 ac4c01aa2720e431da333c83d9 663bfb1fb7a1a7b90528482c6be7892299030bb 542 51a51dc7e91e9156874416bf4c26f 1ea7ec578058563960ef92bbbb8632d3a1b6 543 95f954af10e9a78e40acffc13b06540a ae9da5287fc4429485d44e6289d8c0d6a 544 3eb2ece35012452751839fb48bc14b51547 8e2ff412d930ac20307561f3a5c998 545 e6bcbfebd97effc6433033a2361bfcdc4fc74a d379a16c6dea49c209b1 547 Pairing-Param-ID: Fp581BLS48 = { 548 G1-Curve-ID: Fp581BLS48n 549 G2-Curve-ID: Fp581BLS48n8 550 G3-Field-ID: Fp581BLS48n48 551 } 553 4. Optimal Ate Pairing 555 This section specifies Optimal Ate Pairing e for c_0, ..., c_l and 556 s_i = sum_{j=i}^l c_j * q^j with the following conditions 558 1. c_l is not 0 560 2. r is a divisor of s_0 562 3. r^2 is not a divisor of s_0 564 4. r does not divide s_0 * k * q^{k-1} - (q^k - 1)/r * sum_{i=0}^l i 565 * c_i * q^{i - 1} 567 Section 4.1 shows a guide to decide these parameters c_0, ..., c_l. 568 Optimal Ate Pairing is specified below and Miller Loop f which are 569 its building blocks are introduced in Section 4.2. Straight Line 570 Function l which is building blocks of Optimal Ate Pairing and Miller 571 Loop are defined in Section 4.3. Section 4.3 only show the 572 definitions because its descriptions are based on the form (of the 573 PFC?). Practically, concrete algorithms need to be specified for a 574 form of PFC. 576 Input: 578 o A point P in G_1 580 o A point Q in G_2 582 Output: 584 o The value e(P, Q) in G_3 586 Method: 588 1. f = 1 590 2. ln = 1 592 3. for i = 0 to l 594 (a) f = f * f_{c_i, Q}^{q^i}(P) 596 end for 598 4. for i = 0 to l - 1 600 (a) ln = ln * l_{[s_i + 1]Q, [c_i * q^i]Q}(P) 602 end for 604 5. return (f * ln)^{(q^k - 1)/r} 606 4.1. Guide for Decision on Parameters for Optimal Ate Pairing 608 This subsection shows a guide for decision on parameters c_0, ..., 609 c_l for Optimal Ate Pairing. According to [2], a way is to choose 610 coefficients of short vector of the following lattice L with a 611 minimal number of coefficients as parameters c_0, ..., c_l. 613 L = (v_1, ..., v_phi(k)) where 614 o v_1 is column vector t(r, -q, -q^2, ..., -q^{phi(k) - 1}) 616 o v_i is column vector whose i-th component is 1 and other 617 components is 0 for i = 2, ..., phi(k) 619 4.2. Miller Loop 621 In this subsection, we specify Miller Loop f which is building block 622 of Optimal Ate Pairing. 624 Input: 626 o A point P in G_1 628 o A point Q in G_2 630 o An integer s 632 Output: 634 o f_{s, Q}(P) 636 Method: 638 1. compute s_0, ..., s_L such that |s| = sum_{j=0}^L s_j * 2^j with 639 s_j is in {0, 1} and s_L = 1 641 2. T = Q 643 3. f = 1 645 4. for j = L - 1 down to 0 647 (A) Doubling Step 649 (a) ln = l_{T, T}(P) 651 (b) T = 2 * T 653 (B) f = f^2 * ln 655 (C) if s_j = 1 657 (a) Addition Step 659 (i) ln = l_{T, Q}(P) 661 (ii) T = T + Q 663 (b) f = f' * ln 665 end if 667 end for 669 5. if s < 0, then f = f^{-1} 671 6. return f 673 4.3. Straight Line Function 675 Straight Line Function l_{Q, Q'}(P) is calculated by a point P for 676 linear equation defined as a line l though points Q, Q'. Note that 677 Straight Line Function l_{Q, Q'}(P) is calculated by a point P for 678 linear equation defined as a tangent line to an elliptic curve E at a 679 point Q of E on condition that Q = Q'. The function is used for 680 Optimal Ate Pairing in Section 4 and Miller Loop in Section 4.2 682 5. Algorithm Identifiers 684 (TBD) 686 6. Security Considerations 688 The pairing is a map from two elliptic curves G1 and G2 to a 689 multiplicative subgroup of a finite field. 691 Typically, G1 (respectively G2) is a cyclic subgroup in E(F_p) 692 (respectively E'(F_{p^{k/d})) of prime order r, where k is the 693 embedding degree and d is the degree of the twist. The group G3 is a 694 set of r-th roots of unity in F_{p^k}^*. In this section, G_1', G_2' 695 and G_3' denote E(F_p), E'(F_{p^{k/d}}) and F_{p^k}^* respectively. 697 Pairing-based cryptographic primitives are often based on the 698 hardness of the following problems. 700 The elliptic curve discrete logarithm problem in G_1' and G_2' 701 (ECDLP) 703 The finite field discrete logarithm problem in G_3' (FFDLP) 705 The elliptic curve computational Diffie-Hellman (CDH) problem in 706 G_1' and G_2' 708 The elliptic curve computational co-Diffie-Hellman problem in G_1' 709 and G_2' 710 The elliptic curve decisional Diffie-Hellman (DDH) problem in G_1' 712 The bilinear Diffie-Hellman (BDH) problem 714 On the side of G1' and G2', the best known algorithm (for instance, 715 Pollard-rho algorithm [10]) to solve ECDLP has a running time of 716 O(sqrt(r)), which is exponential in r, where r is the order of the 717 target group. Thus, for a security parameter l, one should set r so 718 that log_2(r)>2*l. 720 On the side of G3', one has more efficient algorithm based on Number 721 Field Sieve methods (cite Gordon93 paper here, if you want). The 722 complexity of the NFS (including its variants) is subexponential in 723 the size of the finite field and is independent from the size of the 724 subgroup order r. Recall the classical L-notation, L(q, a, c)= exp( 725 (c+o(1))*log(q)^a * log(log(q))^(1-a) ). Before 2016, the best known 726 algorithm for FFDLP has had a running time of L(p^k, 1/3, 1.92) and 727 the parameters of currently used pairings are derived from the above 728 value. At CRYPTO2016, however, Kim and Barbulescu proposed a new 729 variant of the NFS method that drastically reduces the complexity of 730 solving FFDLP from L(p^k, 1/3, 1.92) to L(p^k, 1/3, 1.53) in the best 731 case[11]. For instance, Barbulescu estimates that the security of 732 the pairing over BN curve, which was believed to have 128-bit 733 security, drops to approximately 100-bit security. Hence, it has 734 become necessary to revise the bit length of q=p^k so that the FFDLP 735 over F_{p^k} is computationally infeasible against this new efficient 736 NFS algorithm. 738 G_3' to be larger than G_1' and G_2', because FFDLP can be computed 739 more efficiently than ECDLP in most cases. Security level of schemes 740 based on pairing depends most weak level for each problems. Thus 741 implementers should necessary to ensure adequate security level for 742 both of problems. 744 6.1. 128-bit Secure PFC 746 Barreto and Naehrig showed how to construct pairing-friendly 747 curves[13]. We have chosen 462-bit prime order curve and described 748 in Section 3. 750 6.2. 256-bit Secure PFC 752 Five 256-bit secure domain parameters have been proposed by 753 Kiyomura[12]. We have chosen the BLS48 as 256-bit secure PFC and 754 described in Section 3. 756 7. Acknowledgements 758 (TBD) 760 8. Change log 762 NOTE TO RFC EDITOR: Please remove this section in before final RFC 763 publication. 765 9. References 767 9.1. Normative References 769 [1] Bradner, S., "Key words for use in RFCs to Indicate 770 Requirement Levels", RFC 2119, March 1997. 772 [2] Vercauteren, F., "Optimal pairings", Proceedings IEEE 773 Transactions on Information Theory 56(1): 455-461 (2010), 774 2010. 776 9.2. Informative References 778 [3] Boyen, X. and l. Martin, "Identity-Based Cryptography 779 Standard (IBCS) #1: Supersingular Curve Implementations of 780 the BF and BB1 Cryptosystems", RFC 5091, December 2007. 782 [4] Hitt, L., "ZSS Short Signature Scheme for Supersingular 783 and BN Curves", draft-irtf-cfrg-zss-02 (work in progress), 784 2013. 786 [5] Boneh, D. and M. Franklin, "Identity-based encryption from 787 the Weil pairing", Proceedings Lecture notes in computer 788 sciences; CRYPTO --CRYPTO2001, 2001. 790 [6] Okamoto, T. and K. Takashima, "Fully Secure Functional 791 Encryption with General Relations from the Decisional 792 Linear Assumption", Proceedings Lecture notes in computer 793 sciences; CRYPTO --CRYPTO2011, 2010. 795 [7] "University of Tsukuba Elliptic Curve and Pairing 796 Library", 2013, 797 . 799 [8] Aranha, D. and C. Gouv, "RELIC is an Efficient LIbrary for 800 Cryptography", 2013, 801 . 803 [9] Scott, M., "The MIRACL IoT Multi-Lingual Crypto Library", 804 2015, . 806 [10] Pollard, J., "Monte Carlo Methods for Index Computation ( 807 mod p)", Proceedings Mathematics of Computation, Vol.32, 808 1978. 810 [11] Kim, T. and R. Barbulescu, "Extended tower number field 811 sieve: a new complexity for the medium prime case.", 812 CRYPTO 2016 LNCS, vol. 9814, pp. 543.571, 2016. 814 [12] Kiyomura, Y., Inoue, A., Kawahara, Y., Yasuda, M., Takagi, 815 T., and T. Kobayashi, "Secure and Efficient Pairing at 816 256-Bit Security Level", ACNS 2017 LNCS, vol. 10355, pp. 817 59.79, 2017, 2017. 819 [13] Barreto, Paulo. and Michael. Naehrig, "Pairing-Friendly 820 Elliptic Curves of Prime Order", Selected Areas in 821 Cryptography-SAC 2005. volume 3897 of Lecture Notes in 822 Computer Science, pages 319-331, 2006. 824 [14] "ISO/IEC 14888-3:2016", ISO/IEC Information technology -- 825 Security techniques -- Digital signatures with appendix -- 826 Part 3: Discrete logarithm based mechanisms, 2016. 828 Appendix A. Test Vectors of Optimal Ate Pairing 830 In this section, we specify test vectors of Optimal Ate Pairing over 831 BN-curve and BLS-curve which are specified by Section 3 in the 832 following way. 834 Parameter: 836 Pairing-Param-ID is an identifier with which the pairing parameter 837 set can be referenced. 839 Input: 841 P is a point of E in G_1 843 Q is a point of E' in G_2 845 Output: 847 e(P, Q) is computation of pairing in G_3 849 (TBD) 851 Authors' Addresses 853 Akihiro Kato 854 NTT TechnoCross Corporation 856 EMail: kato.akihiro-at-po.ntt-tx.co.jp 858 Tetsutaro Kobayashi 859 NTT 861 EMail: kobayashi.tetsutaro-at-lab.ntt.co.jp 863 Yuto Kawahara 864 NTT 866 EMail: kawahara.yuto-at-lab.ntt.co.jp 868 Taechan Kim 869 NTT 871 EMail: taechan.kim-at-lab.ntt.co.jp 872 Tsunekazu Saito 873 NTT 875 EMail: saito.tsunekazu-at-lab.ntt.co.jp