idnits 2.17.1 draft-kato-optimal-ate-pairings-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.) ** The abstract seems to contain references ([2], [3], [4], [7]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. 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, 2016) is 2960 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 2 errors (**), 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 Software Corporation 4 Intended status: Informational M. Scott 5 Expires: September 19, 2016 CertiVox 6 T. Kobayashi 7 Y. Kawahara 8 NTT 9 March 18, 2016 11 Optimal Ate Pairing 12 draft-kato-optimal-ate-pairings-01 14 Abstract 16 Pairing is a special map from two elliptic curve that called Pairing- 17 friend curves to a finite field and is useful mathematical tools for 18 constructing cryptographic primitives. It allows us to construct 19 powerful primitives. (e.g. [3] and [4]) 21 There are some types of pairing and its choice has an impact on the 22 performance of the primitive. For example, Tate Pairing [3] and Ate 23 Pairing [4] are specified in IETF. This memo focuses on Optimal Ate 24 Pairing [2] which is an improvement of Ate Pairing. 26 This memo defines Optimal Ate Pairing for any pairing-friendly curve. 27 We can obtain concrete algorithm by deciding parameters and building 28 blocks based on the form of a curve and the description in this memo. 29 It enables us to reduce the cost for specifying Optimal Ate Pairing 30 over additional curves. Furthermore, this memo provides concrete 31 algorithm for Optimal Ate Pairing over BN-curves [7] and its test 32 vectors. 34 Status of This Memo 36 This Internet-Draft is submitted in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at http://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on September 19, 2016. 50 Copyright Notice 52 Copyright (c) 2016 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2. Requirements Terminology . . . . . . . . . . . . . . . . . . 3 69 3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 3 70 3.1. Elliptic Curve . . . . . . . . . . . . . . . . . . . . . 3 71 3.2. Bilinear Map . . . . . . . . . . . . . . . . . . . . . . 4 72 4. Optimal Ate Pairing . . . . . . . . . . . . . . . . . . . . . 4 73 4.1. Guide for Decision on Parameters for Optimal Ate Pairing 5 74 4.2. Miller Loop . . . . . . . . . . . . . . . . . . . . . . . 6 75 4.3. Straight Line Function . . . . . . . . . . . . . . . . . 7 76 5. Optimal Ate Pairing over BN-curves . . . . . . . . . . . . . 7 77 5.1. Straight Line Function over BN-curves . . . . . . . . . . 8 78 5.2. Doubling Step of Miller Loop over BN-Curves . . . . . . . 9 79 5.3. Addition Step of Miller Loop over BN-Curves . . . . . . . 10 80 6. Algorithm Identifiers . . . . . . . . . . . . . . . . . . . . 11 81 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 82 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 83 9. Change log . . . . . . . . . . . . . . . . . . . . . . . . . 11 84 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 85 10.1. Normative References . . . . . . . . . . . . . . . . . . 11 86 10.2. Informative References . . . . . . . . . . . . . . . . . 11 87 Appendix A. Perfomance . . . . . . . . . . . . . . . . . . . . . 13 88 Appendix B. Test Vectors of Optimal Ate Pairing over BN-curves . 13 89 B.1. 254-Bit-Curves by Beuchat et al. . . . . . . . . . . . . 13 90 B.2. 254-Bit-Curves by Nogami et al. / Aranha et al. . . . . . 14 91 B.3. 254-Bit-Curves by Scott . . . . . . . . . . . . . . . . . 15 92 B.4. 254-Bit-Curves by BCMNPZ . . . . . . . . . . . . . . . . 16 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 95 1. Introduction 97 Pairing is a special map from two elliptic curve that called Pairing- 98 friend curves (PFCs) to a finite field and is useful mathematical 99 tools for constructing cryptographic primitives. It allows us to 100 construct powerful primitives like Identity-Based Encryption (IBE) 101 [5] and Functional Encryption (FE) [6]. The IBE and FE provide a 102 rich decryption condition. Some Pairing-Based Cryptography is 103 specified in IETF. (e.g. [3] and [4]) 105 There are some types of pairing and its choice has an impact on the 106 performance of the primitive. For example, primitives by using Tate 107 Pairing [3] and Ate Pairing [4] are specified in IETF. This memo 108 focuses on Optimal Ate Pairing which is an improvement of Ate 109 Pairing. Optimal Ate Pairing allows us to construct Pairing-Based 110 Cryptography with high performance and is implemented in some open 111 source softwares. ([8], [9], and [10]) 113 This memo defines Optimal Ate Pairing [2] for any PFC. We can obtain 114 concrete algorithm by deciding parameters and two building blocks 115 based on the form of a curve. It enables us to reduce the cost for 116 describing the body of Optimal Ate Pairing when Optimal Ate Pairing 117 is specified over additional curves in IETF. Furthermore, this memo 118 provides concrete algorithm for Optimal Ate Pairing over BN-curves 119 [7] and its test vectors. This memo is expected to use by combining 120 Optimal Ate Pairing with a suitable PFC for a primitive in order to 121 realize same functional structure of ECDSA and ECDH. (i.e. DSA over 122 elliptic curve and DH over elliptic curve) 124 2. Requirements Terminology 126 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 127 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 128 memo are to be interpreted as described in [1]. 130 3. Preliminaries 132 In this section, we introduce the definition of elliptic curve and 133 bilinear map, notation used in this memo. 135 3.1. Elliptic Curve 137 Throughout this memo, let p > 3 be a prime, q = p^n, and n be a 138 natural number. Also, let F_q be a finite field. The curve defined 139 by the following equation E is called an elliptic curve. 141 E : y^2 = x^3 + A * x + B such that A, B are in F_q, 142 4 * A^3 + 27 * B^2 != 0 mod F_q 144 Solutions (x, y) for an elliptic curve E, as well as the point at 145 infinity, are called F_q-rational points. The additive group is 146 constructed by a well-defined operation in the set of F_q-rational 147 points. Typically, the cyclic additive group with prime order r and 148 the base point G in its group is used for the cryptographic 149 applications. Furthermore, we define terminology used in this memo 150 as follows. 152 O_E: the point at infinity over elliptic curve E. 154 #E(F_q): number of points on an elliptic curve E over F_q. 156 cofactor h: h = #E(F_p)/r. 158 embedding degree k: minimum integer k such that r is a divisor of 159 q^k - 1 161 3.2. Bilinear Map 163 Let G_1 be an additive group of prime order r and let G_2 and G_T be 164 additive and multiplicative groups, respectively, of the same order. 165 Let P, Q be generators of G_1, G_2 respectively. We say that (G_1, 166 G_2, G_T) are asymmetric bilinear map groups if there exists a 167 bilinear map e: (G_1, G_2) -> G_T satisfying the following 168 properties: 170 1. Bilinearity: for any S in G_1, for any T in G_2, for any a, b in 171 Z_r, we have the relation e([a]S, [b]T) = e(S, T)^{a * b}. 173 2. Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S = 174 O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T = 175 O_E. 177 3. Computability: for any S in G_1, for any T in G_2, the bilinear 178 map is efficiently computable. 180 4. Optimal Ate Pairing 182 This section specifies Optimal Ate Pairing e for c_0, ..., c_l and 183 s_i = sum_{j=i}^l c_j * q^j with following conditions 185 1. c_l is not 0 187 2. r is a divisor of s_0 189 3. r^2 is not a divisor of s_0 190 4. r does not divide s_0 * k * q^{k-1} - (q^k - 1)/r * sum_{i=0}^l i 191 * c_i * q^{i - 1} 193 Section 4.1 shows a guide to decide these parameters c_0, ..., c_l. 194 Optimal Ate Pairing is specified below and Miller Loop f which are 195 its building blocks are introduced in Section 4.2. Straight Line 196 Function l which is building blocks of Optimal Ate Pairing and Miller 197 Loop are defined in Section 4.3. Section 4.3 only show the 198 definitions because its descriptions are based on the form (of the 199 PFC?). Practically, concrete algorithms need to be specified for a 200 form of PFC. 202 Input: 204 o A point P in G_1 206 o A point Q in G_2 208 Output: 210 o The value e(P, Q) in G_T 212 Method: 214 1. f = 1 216 2. ln = 1 218 3. for i = 0 to l 220 (a) f = f * f_{c_i, Q}^{q^i}(P) 222 end for 224 4. for i = 0 to l - 1 226 (a) ln = ln * l_{[s_i + 1]Q, [c_i * q^i]Q}(P) 228 end for 230 5. return (f * ln)^{(q^k - 1)/r} 232 4.1. Guide for Decision on Parameters for Optimal Ate Pairing 234 This subsection shows a guide for decision on parameters c_0, ..., 235 c_l for Optimal Ate Pairing. According to [2], a way is to choice 236 coefficients of short vector of the following lattice L with a 237 minimal number of coefficients as parameters c_0, ..., c_l. 239 L = (v_1, ..., v_phi(k)) where 241 o v_1 is column vector t(r, -q, -q^2, ..., -q^{phi(k) - 1}) 243 o v_i is column vector whose i component is 1 and other components 244 is 0 for i = 2, ..., phi(k) 246 4.2. Miller Loop 248 In this subsection, we specify Miller Loop f which is building block 249 of Optimal Ate Pairing. 251 Input: 253 o A point P in G_1 255 o A point Q in G_2 257 o An integer s 259 Output: 261 o f_{s, Q}(P) 263 Method: 265 1. compute s_0, ..., s_L such that |s| = sum_{j=0}^L s_j * 2^j with 266 s_j is in {0, 1} and s_L = 1 268 2. T = Q 270 3. f = 1 272 4. for j = L - 1 down to 0 274 (A) Doubling Step 276 (a) ln = l_{T, T}(P) 278 (b) T = 2 * T 280 (B) f = f^2 * ln 282 (C) if s_j = 1 284 (a) Addition Step 286 (i) ln = l_{T, Q}(P) 287 (ii) T = T + Q 289 (b) f = f' * ln 291 end if 293 end for 295 5. if s < 0, then f = f^{-1} 297 6. return f 299 4.3. Straight Line Function 301 Straight Line Function l_{Q, Q'}(P) is calculated by a point P for 302 linear equation defined as a line l though points Q, Q'. Note that 303 Straight Line Function l_{Q, Q'}(P) is calculated by a point P for 304 linear equation defined as a tangent line to an elliptic curve E at a 305 point Q of E on condition that Q = Q'. The function is used for 306 Optimal Ate Pairing in Section 4 and Miller Loop in Section 4.2 308 5. Optimal Ate Pairing over BN-curves 310 In this section, we specify Optimal Ate Pairing over BN-curves [7]. 311 BN-curves define over a finite field F_p, and have embedding degree k 312 = 12, r(t) = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1, and p(t) = 313 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1, where t is the specific 314 integer in [7]. 316 The extension fields are defined by following: 318 F_{p^2} is set to F_p[u]/(u^2 - e2) 320 F_{p^6} is set to F_{p^2}[v]/(u^3 - e6) 322 F_{p^12} is set to F_{p^6}[w]/(w^2 - e12) 324 The constants e3, e6 and e6 which are varied by G_T are defined in 325 [7]. 327 Hence parameters for Optimal Ate Pairing over D-Type twisted curve 328 are following by the method in Section 4.1: 330 1. l = 3 332 2. c_0 = 6 * t + 2 334 3. c_1 = 1 335 4. c_2 = -1 337 5. c_3 = 1 339 These short vectors are specified in section 4. A of [2]. 341 Algorithm of Optimal Ate Pairing by Miller Loop in Section 4.2 based 342 on building blocks specified in Section 5.2 and Section 5.3 and 343 Straight Line Function f in Section 5.1 over BN-curves is as 344 following: 346 Input: 348 o A point P in G_1 350 o A point Q in G_2 352 Output: 354 o The value e(P, Q) in G_T 356 Method: 358 1. f_1 = f_{c_0, Q}(P) 360 2. l_1 = l_{[p^3]Q}, - [p^2]Q}(P) 362 3. l_2 = l_{[p^3]Q - [p^2]Q, [p]Q}(P) 364 4. l_3 = l_{[p]Q - [p^2]Q + [p^3]Q, [6 * t + 2]Q} 366 5. return (f_1 * l_1 * l_2 * l_3)^{(p^k - 1)/r} 368 5.1. Straight Line Function over BN-curves 370 This subsection shows an operation of Straight Line Function over BN- 371 curves for Optimal Ate Pairing. 373 Input: 375 o A point Q = (x_1, y_1) in G_2 377 o A point Q' = (x_2, y_2) in G_2 379 o A point P = (x, y) in G_1 381 Output: 383 o l_{Q, Q'}(P) 385 Method: 387 1. If Q != +- Q' 389 (A) lambda = (y_2 - y_1)/(x_2 - x_1) 391 (B) t0 = -lambda * x 393 (C) t1 = lambda * x_1 - y_1 395 (D) ln = y + t0 * w + t1 w^3 397 2. If Q = Q' 399 (A) lambda = (3 * x_1^2)/(2 * y_1) 401 (B) t0 = -lambda * x 403 (C) t1 = lambda * x_1 - y_1 405 (D) ln = y + t0 w + t1 w^3 407 (E) return ln 409 3. If Q = -Q' 411 (A) ln = x - x_1 w^3 413 4. return ln 415 5.2. Doubling Step of Miller Loop over BN-Curves 417 This subsection shows an operation of Doubling Step of Miller Loop 418 over BN-curves. (i.e. operation of method 4-(A) in Section 4.2 over 419 BN-curves) 421 Input: 423 o A point P = (x, y) in G_1 425 o A point Q = (x_1, y_1) in G_2 427 Output: 429 o ln such that l_{Q, Q}(P) 430 o A point T = (x_3, y_3) such that [2]Q 432 Method: 434 1. lambda = (3 * x_1^2)/(2 * y_1) 436 2. x_3 = lambda^2 - 2 * x_1 438 3. y_3 = lambda * (x_1 - x_3) - y_1 440 4. t0 = -lambda * x 442 5. t1 = lambda * x_1 - y_1 444 6. ln = y + t0 w + t1 w^3 446 7. return ln and T 448 5.3. Addition Step of Miller Loop over BN-Curves 450 This subsection shows an operation of Addition Step of Miller Loop 451 over BN-curves. (i.e. operation of method 4-(C)-(a) in Section 4.2 452 over BN-curves) 454 Input: 456 o A point Q = (x_1, y_1) in G_2 458 o A point Q' = (x_2, y_2) in G_2 460 o A point P = (x, y) in G_1 462 Output: 464 o ln such that l_{Q, Q'}(P) 466 o A point T = (x_3, y_3) such that Q + Q' 468 Method: 470 1. lambda = (y_2 - y_1)/(x_2 - x_1) 472 2. x_3 = lambda^2 - x_1 - x_2 474 3. y_3 = lambda * (x_1 - x_3) - y_1 476 4. t0 = -lambda * x 477 5. t1 = lambda * x_1 - y_1 479 6. ln = y + t0 w + t1 w^3 481 7. return ln and T 483 6. Algorithm Identifiers 485 TBD 487 7. Security Considerations 489 The security of cryptographic primitive which is constructed by 490 pairing depends on pairing-friendly curves (PFC). PFC must satisfy 491 computational assumption which the primitive requires at the level of 492 security strength in system when the primitive is constructed by 493 using Optimal Ate Pairing. 495 8. Acknowledgements 497 TBD 499 9. Change log 501 NOTE TO RFC EDITOR: Please remove this section in before final RFC 502 publication. 504 10. References 506 10.1. Normative References 508 [1] Bradner, S., "Key words for use in RFCs to Indicate 509 Requirement Levels", RFC 2119, March 1997. 511 [2] Vercauteren, F., "Optimal pairings", Proceedings IEEE 512 Transactions on Information Theory 56(1): 455-461 (2010), 513 2010. 515 10.2. Informative References 517 [3] Boyen, X. and l. Martin, "Identity-Based Cryptography 518 Standard (IBCS) #1: Supersingular Curve Implementations of 519 the BF and BB1 Cryptosystems", RFC 5091, December 2007. 521 [4] Hitt, L., "ZSS Short Signature Scheme for Supersingular 522 and BN Curves", draft-irtf-cfrg-zss-02 (work in progress), 523 2013. 525 [5] Boneh, D. and M. Franklin, "Identity-based encryption from 526 the Weil pairing", Proceedings Lecture notes in computer 527 sciences; CRYPTO --CRYPTO2001, 2001. 529 [6] Okamoto, T. and K. Takashima, "Fully Secure Functional 530 Encryption with General Relations from the Decisional 531 Linear Assumption", Proceedings Lecture notes in computer 532 sciences; CRYPTO --CRYPTO2011, 2010. 534 [7] Kasamatsu, K., Kanno, S., Kobayashi, T., and Y. Kawahara, 535 "Barreto-Naehrig Curves", draft-kasamatsu-bncurves-02 536 (work in progress), 2015. 538 [8] "University of Tsukuba Elliptic Curve and Pairing 539 Library", 2013, 540 . 542 [9] Aranha, D. and C. Gouv, "RELIC is an Efficient LIbrary for 543 Cryptography", 2013, . 546 [10] Scott, M., "The MIRACL IoT Multi-Lingual Crypto Library", 547 2015, . 549 [11] Unterluggauer, T. and E. Wenger, "Efficient Pairings and 550 ECC for Embedded Systems", 2014, 551 . 553 Appendix A. Perfomance 555 T. Unterluggauer and E. Wenger computed the running time of optimal 556 ate paring on an ARM Coretex-M0+ that is small and energy efficient 557 microprocessor [11]. By their result, optimal ate pairing's running 558 time on Coretex-M0+ is 1 sec. 560 Appendix B. Test Vectors of Optimal Ate Pairing over BN-curves 562 In this section, we specify test vectors of optimal ate pairing over 563 BN-curves which are specified by [7] in the following way. 565 Parameter: 567 Pairing-Param-ID is an identifier with which the pairing parameter 568 set can be referenced. 570 Input: 572 P is a point of E in G_1 574 Q is a point of E' in G_2 576 Output: 578 e(P, Q) is computation of pairing in G_T 580 B.1. 254-Bit-Curves by Beuchat et al. 582 This subsection shows test vector of 254-bit curves by Beuchat et al. 583 [7] and reprints its parameters under F_{p^2} = F_p[u]/(u^2 + 5), 584 F_{p^6} = F_{p^2}[v]/(v^3 - u), F_{p^12} = F_{p^6}[w]/(w^2 - v) as a 585 reference. 587 Parameter: 589 Pairing-Param-ID: Beuchat 591 Input: 593 P = (0x0A971735A70FBDD0F94D7D6EFBBC81BEA78D2D92A8510F3344038A41641 594 9AD97, 0x09456E41754237447752A448282C0873785F724447E1299826F53AC55 595 6936D3F) 597 Q = (0x115231D7B49901BA97CB93B5227F7F7F438A346532893DD5FAFD5189509 598 24AA9 + 0x0DF12398FB78695A50BB3499B7E23B0D9035989B91A76D13AF7BC643 599 74BFB8A6 u, 0x051D0E087527BC9F41379FB0272EC91E5F28EE011B183EF7D671 600 2EF3FC9A1A66 + 0x0107E6654DC6C36E163B7867AECB98E4046084734524DBB56 601 2E73E5A811F678A u) 603 Output: 605 e(P,Q) = (0x06A4E0DD1F7FD2F9E5DACAB02CEC9CE8254925C5DC6697E153F05A 606 242CBCA8A8 + 0x22A0E22C097AEC1187087B7632C9B963B0E779BC8D09848C44D 607 3EA95CD1C1F8C u + 0x0751037182B5F93BCAB31B115A2C0A0DCC09C6DB7602E0 608 551DD44925F3D364B3 v + 0x04B6BFFB9EB68AD6A99ACF52B8AAD1D17D328847C 609 6313201A6B659C9DAA5CDFE uv + 0x13BE65D47487BF6D96C146C18855C1F87BF 610 994F9F1048524568EA0CB9DC402AD v^2 + 0x1202BE31EB2BDCBEF9F3CC00F1B2 611 CC35FADBE1A0D66CCBF40B024ADFA84C77D1 uv^2 + 0x15F9E3D10B580FF1AB22 612 82EF1DC39A88E06F93A18303E9520D99B86D665F5380 w + 0x0A1C6D26A6D6830 613 31D95C4369DB90F5FEE36D5008AA498D2CB6F2DDE6258CDA6 uw + 0x1611153BF 614 02F1CF7985B98C3F3CB641D39283DBA55E22D1C614568F84959C6FC vw + 0x10B 615 EF55B7539743CBEAB13E49116A143302F6F28CCD71A69860CEF5208483809 uvw 616 + 0x166BD873D0C65DE66300A168BBDC16F0AB1B57A0809973239F2109A7D25AD3 617 49 v^2w + 0x14D4B5014F840144D03C0C6B6010BB246EE6A69BF704D7542FBAA8 618 F2D2A27308 uv^2w) 620 B.2. 254-Bit-Curves by Nogami et al. / Aranha et al. 622 This subsection shows test vector of 254-bit curves by Nogami et al. 623 / Aranha et al. [7] and reprints its parameters under F_{p^2} = 624 F_p[u]/(u^2 + 1), F_{p^6} = F_{p^2}[v]/(v^3 - (1 + u)), F_{p^12} = 625 F_{p^6}[w]/(w^2 - v) as a reference. 627 Parameter: 629 Pairing-Param-ID: Nogami-Aranha 631 Input: 633 P = (0x2074A81D4402A0B63B947335C14B2FC3C28FEA2973860F686114BEC4670 634 E4EB7, 0x06A41108087B20038771FC89FB94A82B2006034A6E8D871B3BC284846 635 631CBEB) 637 Q = (0x049EEDB108B71A87BFCFC9B65EB5CF1C2F89554E02DF4F8354E4A00F521 638 83C77 + 0x1FB93AB676140E87D97226185BA05BF5EC088A9CC76D966697CFB8FA 639 9AA8845D u, 0x0CD04A1ED14AD3CDF6A1FE4453DA2BB9E686A637FB3FF8E25736 640 44CC1EDF208A + 0x11FF7795CF59D1A1A7D6EE3C3C2DFC765DEF1CAA9F14EA264 641 E71BD7630A43C14 u) 643 Output: 645 e(P,Q) = (0x03E1F2693AC6D549898C78897EB158490A4832E296F888D3014050 646 0DB7BD3D12 + 0x1EBC54A76E844EB5D352945226FB103DE9EC1A4FC689B87FAA6 647 6EF8ABA79D3ED u + 0x0A5A5405542F67384D683A48C281F3676B67554ED5DA17 648 00784169A0B47A57E4 v + 0x048B66DAFCAEE86DB4D46AB71A9FE848443EF81F4 649 88D8366A727B39698CF7201 uv + 0x142715D6482BC6FA77377C9CBC2A51C047C 650 16DE88483D5A889C7EF4DF5F03BDB v^2 + 0x11EE0C12164133041C3DCF312CE1 651 11C845B60092818F7B72805D4AFF61427934 uv^2 + 0x22371AF975DAE562F686 652 988CDBBD02702C959BBF843A1FB3C7532D07BE3D7A3A w + 0x04052CA96090068 653 4A1B26C434B2776AA70736841474C16208CCD1A7C27927E19 uw + 0x05D259DA3 654 F3AAAA54A6AE5FE8272A5B79D7F4E5BDF3B5E3C815AD781113F7548 vw + 0x084 655 3C37BC5BDBF253E3BCE568F5905A63867D8836855B74CBA0C800D5DC41B71 uvw 656 + 0x13CA93E1377EF0F6DD38FC2F96DBD3E8B0922F60D1F274EAC63DC1AF2EE975 657 4C v^2w + 0x0D467F3DA4FB329A5CB406D0A7B743A3A2FFCD09BF95EE8A856B94 658 AF191D96AF uv^2w) 660 B.3. 254-Bit-Curves by Scott 662 This subsection shows test vector of 254-bit curves by Scott [7] and 663 reprints its parameters under F_{p^2} = F_p[u]/(u^2 + 1), F_{p^6} = 664 F_{p^2}[v]/(v^3 - (1 + u)), F_{p^12} = F_{p^6}[w]/(w^2 - v) as a 665 reference. 667 Parameter: 669 Pairing-Param-ID: Scott 671 Input: 673 P = (0x8a9143801f541142f89e498a1c06ba0959b8f9713abda0881e5de80d8af 674 f11a + 0x17df54e2be5e8afeb9a42f412825f79c32841307471fb2b6a14e3a0f 675 c6e010f4) 677 Q = (0x21794a9da7b34b2c1614315d7d90a282c484c8fd49c0c8ba75b079ae304 678 7d566 + 0x1a9b474c4519e6faee5b32c7cb65547d8707137bca00c9c182d10b7e 679 3e305936 u, 0xb00d54bf5a298d0eacdefb0efdb74d1a7e744722f61cc8844884 680 fcce20ff876 + 0x5ecf8bd02e1f5363c8402163c9a235df56b133cc2c8a926c0e 681 65e985d746b7b u) 683 Output: 685 e(P,Q) = (0x13d3127ba07feffc8c1a608afc58a33a25148176968ef0ec0a2e09 686 b62344f984 + 0x1774dfc7361e1d4cd2de4bf62cd9b460f0a78487e75994f9e25 687 51fed2f9d2b78 u + 0x2c7888f053123b5a815125b2c409e3f986594f6c35585c 688 fb1ed1a1cbbd2ea65 v + 0xe7e7af51c459f6e0ef489348664bc4277e023a5031 689 bee98658d5b357c07d7e8 uv + 0x8d0f0dd32f31d3624dd9e179233a1f2f2d13c 690 c1869f2eb933cd3cded75efe0d v^2 + 0x63e676f8cc5be53e8718cc9e61a8c5a 691 018ac47e3a66f83f4c403ec8caaa130e v^2u + 0x1643c6ec6cf54a1970bfea19 692 c55e34a312eb5c825f8d31354200d29339d2ca61 w + 0xaae41d356d24b0234dc 693 2b714b595aa297f585bbe9a7c4840d58d62cdfaa1764 wu+ 0x1ea5e2efa342adc 694 bc3ac757254d03bfde32ef6a8445bfa6a7b13aee776430594 wv + 0x3aa5bc92f 695 95887ce42ef03e666dd1455d640a031b062ed7a65fbf0a59d996b8 wvu + 0xf77 696 35a9655207b2fe6e8e73d8f8c3f79f8a08aaeb670e6b9059d8f0739891ec wv^2 697 + 0x1a501fad47a0406e50b705a544377ee1ad7518adbbb49cbe30ce31770ae9be 698 2e wv^2u) 700 B.4. 254-Bit-Curves by BCMNPZ 702 This subsection shows test vector of 254-bit curves by BCMNPZ [7] and 703 reprints its parameters under F_{p^2} = F_p[u]/(u^2 + 1), F_{p^6} = 704 F_{p^2}[v]/(v^3 - (1 + u)), F_{p^12} = F_{p^6}[w]/(w^2 - v) as a 705 reference. 707 Parameter: 709 Pairing-Param-ID: BCMNPZ 711 Input: 713 P = (0x1bec8eae1f1d3959e394588e49d09f2d3070efda1f836640288cf21af54 714 88765 + 0x2d148d39f9edf5325d9a1f4820774930675669a6fe20284e435f4bfe 715 3d3273c) 717 Q = (0xd62cf33cd0e46fdc338cfab52ca5cdebf1a9348e4460545441584ff4f8d 718 c275 + 0x22701025e0cd2bfed4518febe8e7fa97a3c7f33f2fdd280e24d651be9 719 d17d7a8, 0x1cc6cbd065535e7f83be0cfc4f39d4687558fc21dcdc6e46aca508c 720 4f6cc1f90 + 86ee46779f9e9922a870137d033e484ec5c5ba979b75bba179064a 721 bff0cf2a u) 723 Output: 725 e(P,Q) = (0x20f263ae42e42cfd53cf99dc238ed7b61951c1c767af88a72ad3c1 726 9ca54cdb2d + 0xa96b263aade3501f7201808028c4ce11793dd84127d80525fa5 727 7f892d3043f6 u + 0x3a31ca4864d996d64181d9a0b025e7368d60b1f53a8276a 728 2c39e02a58b6636e v + 0x2301fe7eb607f6dd63b72979753c96d23fdd487f116 729 77644884f86a83c837174 uv + 0xcbe52ab6e1c210cf80215816f38d8964c4534 730 7bd3802c66d85e616ca9786dde v^2 + 0x1c039dee75146d8ae6812568e77d11c 731 fa060d11e0224dc6e28606bfb14090650 v^2u + 0x2344fb2b5dd57710d544583 732 83cd33bd8f928babfe6f7d641887a565790b88e24 w + 0x8e48a543c2a73cca42 733 811a2fea2e79eb3e628e27e54a477b5e1652466629608 wu+ 0x96a48564f586e1 734 d59d8a9393730824b885818e93a3ce4bfae057682efc37aeb wv + 0x17260fa31 735 ed89d4e90d7a1a2652379e4329927e61f15b11a2ce2a93c84050245 wvu + 0x5b 736 d893369435b63a10384db8248dab8908f2173e166129d0cccd6d37c89dce6 wv^2 737 + 0x2a4dec6bbfe98df2c9169b06410c329d4c699747ca649e611d9960416d615 738 b5 wv^2u) 740 Authors' Addresses 742 Akihiro Kato 743 NTT Software Corporation 745 EMail: kato.akihiro-at-po.ntts.co.jp 747 Michael Scott 748 CertiVox 750 EMail: mike.scott-at-certivox.com 752 Tetsutaro Kobayashi 753 NTT 755 EMail: kobayashi.tetsutaro-at-lab.ntt.co.jp 757 Yuto Kawahara 758 NTT 760 EMail: kawahara.yuto-at-lab.ntt.co.jp