PairingFriendly Curves
draftirtfcfrgpairingfriendlycurves04
The information below is for an old version of the document.
Document  Type 
This is an older version of an InternetDraft whose latest revision state is "Expired".



Authors  Yumi Sakemi , Tetsutaro Kobayashi , Tsunekazu Saito  
Last updated  20200526 (Latest revision 20200428)  
Replaces  draftyonezawapairingfriendlycurves  
RFC stream  Internet Research Task Force (IRTF)  
Formats  
Additional resources  Mailing list discussion  
Stream  IRTF state  (None)  
Consensus boilerplate  Unknown  
Document shepherd  Stanislav V. Smyshlyaev  
IESG  IESG state  ID Exists  
Telechat date  (None)  
Responsible AD  (None)  
Send notices to  Stanislav Smyshlyaev <smyshsv@gmail.com> 
draftirtfcfrgpairingfriendlycurves04
CFRG Y. Sakemi, Ed. InternetDraft Lepidum Intended status: Experimental T. Kobayashi Expires: 30 October 2020 T. Saito NTT 28 April 2020 PairingFriendly Curves draftirtfcfrgpairingfriendlycurves04 Abstract Pairingbased cryptography, a variant of elliptic curve cryptography, has received attention for its flexible and applicable functionality. Pairing is a special map defined over elliptic curves and it can be applied to construct several cryptographic protocols such as identitybased encryption, attributebased encryption, and so on. At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field sieve algorithm named exTNFS for the discrete logarithm problem in a finite field. Several types of pairingfriendly curves such as BarretoNaehrig curves are affected by the attack. In particular, a BarretoNaehrig curve with a 254bit characteristic was adopted by a lot of cryptographic libraries as a parameter of 128bit security, however, it ensures no more than a 100bit security level due to the effect of the attack. In this memo, we summarize the adoption status of pairingfriendly curves in standards, libraries and applications, and classify them in 128bit, 192bit, and 256bit security levels. Then, from the viewpoints of "security" and "widely use", we select the recommended pairingfriendly curves considering exTNFS. Status of This Memo This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79. InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current Internet Drafts is at https://datatracker.ietf.org/drafts/current/. InternetDrafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use InternetDrafts as reference material or to cite them other than as "work in progress." This InternetDraft will expire on 30 October 2020. Sakemi, et al. Expires 30 October 2020 [Page 1] InternetDraft PairingFriendly Curves April 2020 Copyright Notice Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ licenseinfo) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Pairingbased Cryptography . . . . . . . . . . . . . . . 3 1.2. Applications of Pairingbased Cryptography . . . . . . . 3 1.3. Motivation and Contribution . . . . . . . . . . . . . . . 5 1.4. Requirements Terminology . . . . . . . . . . . . . . . . 5 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1. Elliptic Curve . . . . . . . . . . . . . . . . . . . . . 5 2.2. Pairing . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3. BarretoNaehrig Curve . . . . . . . . . . . . . . . . . . 7 2.4. BarretoLynnScott Curve . . . . . . . . . . . . . . . . 7 2.5. Representation Convention for an Extension Field . . . . 8 3. Security of PairingFriendly Curves . . . . . . . . . . . . . 9 3.1. Evaluating the Security of PairingFriendly Curves . . . 9 3.2. Impact of the Recent Attack . . . . . . . . . . . . . . . 10 4. Selection of PairingFriendly Curves . . . . . . . . . . . . 10 4.1. Adoption Status of Pairingfriendly Curves . . . . . . . 10 4.1.1. International Standards . . . . . . . . . . . . . . . 14 4.1.2. Cryptographic Libraries . . . . . . . . . . . . . . . 15 4.1.3. Applications . . . . . . . . . . . . . . . . . . . . 16 4.2. For 128bit Security . . . . . . . . . . . . . . . . . . 16 4.2.1. BN Curves . . . . . . . . . . . . . . . . . . . . . . 16 4.3. For 192bit Security . . . . . . . . . . . . . . . . . . 19 4.4. For 256bits Security . . . . . . . . . . . . . . . . . . 19 5. Security Considerations . . . . . . . . . . . . . . . . . . . 23 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 23 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 8.1. Normative References . . . . . . . . . . . . . . . . . . 23 8.2. Informative References . . . . . . . . . . . . . . . . . 24 Appendix A. Computing Optimal Ate Pairing . . . . . . . . . . . 30 A.1. Optimal Ate Pairings over BarretoNaehrig Curves . . . . 31 A.2. Optimal Ate Pairings over BarretoLynnScott Curves . . . 32 Sakemi, et al. Expires 30 October 2020 [Page 2] InternetDraft PairingFriendly Curves April 2020 Appendix B. Test Vectors of Optimal Ate Pairing . . . . . . . . 32 Appendix C. Parameters of the BarretoLynnScott Curve of Embedding Degree 12 . . . . . . . . . . . . . . . . . . . 42 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 44 1. Introduction 1.1. Pairingbased Cryptography Elliptic curve cryptography is an important area in recent cryptography. The cryptographic algorithms based on elliptic curve cryptography, such as the Elliptic Curve Digital Signature Algorithm (ECDSA), are widely used in many applications. Pairingbased cryptography, a variant of elliptic curve cryptography, has attracted much attention for its flexible and applicable functionality. Pairing is a special map defined over elliptic curves. Thanks to the characteristics of pairing, it can be applied to construct several cryptographic algorithms and protocols such as identitybased encryption (IBE), attributebased encryption (ABE), authenticated key exchange (AKE), short signatures, and so on. Several applications of pairingbased cryptography are now in practical use. As the importance of pairing grows, elliptic curves where pairing is efficiently computable are studied and the special curves called pairingfriendly curves are proposed. 1.2. Applications of Pairingbased Cryptography Several applications using pairingbased cryptography are standardized and implemented. We show example applications available in the real world. IETF published RFCs for pairingbased cryptography such as Identity Based Cryptography [RFC5091], SakaiKasahara Key Encryption (SAKKE) [RFC6508], and IdentityBased Authenticated Key Exchange (IBAKE) [RFC6539]. SAKKE is applied to Multimedia Internet KEYing (MIKEY) [RFC6509] and used in 3GPP [SAKKE]. Pairingbased key agreement protocols are standardized in ISO/IEC [ISOIEC117703]. In [ISOIEC117703], a key agreement scheme by Joux [Joux00], identitybased key agreement schemes by SmartChenCheng [CCS07] and FujiokaSuzukiUstaoglu [FSU10] are specified. MIRACL implements MPin, a multifactor authentication protocol [MPin]. The MPin protocol includes a type of zeroknowledge proof, where pairing is used for its construction. Sakemi, et al. Expires 30 October 2020 [Page 3] InternetDraft PairingFriendly Curves April 2020 The Trusted Computing Group (TCG) specified the Elliptic Curve Direct Anonymous Attestation (ECDAA) in the specification of the Trusted Platform Module (TPM) [TPM]. ECDAA is a protocol for proving the attestation held by a TPM to a verifier without revealing the attestation held by that TPM. Pairing is used for constructing ECDAA. FIDO Alliance [FIDO] and W3C [W3C] also published an ECDAA algorithm similar to TCG. Intel introduced Intel Enhanced Privacy ID (EPID) that enables remote attestation of a hardware device while preserving the privacy of the device as a functionality of Intel Software Guard Extensions (SGX) [EPID]. They extended TPM ECDAA to realize such functionality. A pairingbased EPID has been proposed [BL10] and distributed along with Intel SGX applications. Zcash implemented their own zeroknowledge proof algorithm named ZeroKnowledge Succinct NonInteractive Argument of Knowledge (zk SNARKs) [Zcash]. zkSNARKs are used for protecting the privacy of transactions of Zcash. They use pairing to construct zkSNARKs. Cloudflare introduced Geo Key Manager [Cloudflare] to restrict distribution of customers' private keys to the subset of their data centers. To achieve this functionality, ABE is used, and pairing takes a role as a building block. In addition, Cloudflare published a new cryptographic library, the Cloudflare Interoperable, Reusable Cryptographic Library (CIRCL) [CIRCL] in 2019. They plan to support secure pairingfriendly curves in CIRCL. Recently, BonehLynnShacham (BLS) signature schemes are being standardized [ID.bonehblssignature] and utilized in several blockchain projects such as Ethereum [Ethereum], Algorand [Algorand], Chia Network [Chia], and DFINITY [DFINITY]. The aggregation functionality of BLS signatures is effective for their applications of decentralization and scalability. Sakemi, et al. Expires 30 October 2020 [Page 4] InternetDraft PairingFriendly Curves April 2020 1.3. Motivation and Contribution At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field sieve(NSF) algorithm for the discrete logarithm problem in a finite field [KB16]. Several types of pairingfriendly curves such as BarretoNaehrig curves (BN curves)[BN05] and BarretoLynnScott curves (BLS curves)[BLS02] are affected by the attack, since a pairingfriendly curve suitable for cryptographic applications requires that the discrete logarithm problem is sufficiently difficult. In particular, BN254, which is a BN curve with a 254bit characteristic effective for pairing calculations, was adopted by a lot of cryptographic libraries as a parameter of 128bit security, however, BN254 ensures no more than a 100bit security level due to the effect of the attack. To resolve this effect immediately, several research groups and implementers reevaluated the security of pairingfriendly curves and they respectively proposed various curves that are secure against the attack [BD18] [BLS12381]. In this memo, first, we summarize the adoption status of pairing friendly curves in international standards, libraries and applications, and classify them in 128bit, 192bit, and 256bit security levels. Then, from the viewpoints of "security" and "widely used", pairingfriendly curves corresponding to each security level are selected in accordance with the security evaluation by Barbulescu et al.[BD18]. As a result, we recommend the BN curve with the 462bit characteristic and the BLS curves of embedding degree 48 with the 581bit characteristic as parameters for 128bit and 256bit security levels, respectively, and show their specific test vectors. 1.4. Requirements Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 2. Preliminaries 2.1. Elliptic Curve Let p > 3 be a prime and q = p^n for a natural number n. Let F_q be a finite field. The curve defined by the following equation E is called an elliptic curve. Sakemi, et al. Expires 30 October 2020 [Page 5] InternetDraft PairingFriendly Curves April 2020 E : y^2 = x^3 + A * x + B, where x and y are in F_q, and A and B in F_q satisfy the discriminant inequality 4 * A^3 + 27 * B^2 != 0 mod q. This is called the Weierstrass normal form of an elliptic curve. Soluti\ons (x, y) for an elliptic curve E, as well as the point at infinity, O_E, are called F_qrational points. If P and Q are two points on the curve E, we can define R = P + Q as the opposite point of the intersection between the curve E and the line that passes through P and Q. We can define P + O_E = P = O_E + P as well. Similarly, we can define 2P = P + P and a scalar multiplication S = [a]P for a positive integer a can be defined as an (a1)time addition of P. The additive group, denoted by E(F_q), is constructed by the set of F_qrational points and the addition law described above. We can define the cyclic additive group with a prime order r by taking a base point BP in E(F_q) as a generator. This group is used for the elliptic curve cryptography. We define terminology used in this memo as follows. O_E: the point at infinity over an elliptic curve E. E(F_q): a group constructed by F_qrational points of E. #E(F_q): the number of F_qrational points of E. h: a cofactor such that h = #E(F_q) / r. 2.2. Pairing Pairing is a kind of the bilinear map defined over two elliptic curves E and E'. Examples include Weil pairing, Tate pairing, optimal Ate pairing [Ver09], and so on. Optimal Ate pairing is considered to be especially efficient to compute and is mainly used for practical implementation. Let E be an elliptic curve defined over a prime field F_p and E' be an elliptic curve defined over an extension field of F_p. Let k be a minimum integer such that r is a divisor of p^k  1, which is called an embedding degree. Let G_1 be a cyclic subgroup on the elliptic curve E with order r, and G_2 be a cyclic subgroup on the elliptic curve E' with order r. Let G_T be an order r subgroup of a multiplicative group (F_p^k)^*. Sakemi, et al. Expires 30 October 2020 [Page 6] InternetDraft PairingFriendly Curves April 2020 Pairing is defined as a bilinear map e: (G_1, G_2) > G_T satisfying the following properties: 1. Bilinearity: for any S in G_1, T in G_2, and integers a and b, e([a]S, [b]T) = e(S, T)^{a * b}. 2. Nondegeneracy: for any T in G_2, e(S, T) = 1 if and only if S = O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T = O_E. 3. Computability: for any S in G_1 and T in G_2, the bilinear map is efficiently computable. 2.3. BarretoNaehrig Curve A BN curve [BN05] is one of the instantiations of pairingfriendly curves proposed in 2005. A pairing over BN curves constructs optimal Ate pairings. A BN curve is defined by elliptic curves E and E' parameterized by a wellchosen integer t. E is defined over F_p, where p is a prime more than or equal to 5, and E(F_p) has a subgroup of prime order r. The characteristic p and the order r are parameterized by p = 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1 r = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1 for an integer t. The elliptic curve E has an equation of the form E: y^2 = x^3 + b, where b is an element of multiplicative group of order p. BN curves always have order 6 twists. If m is an element that is neither a square nor a cube in an extension field F_p^2, the twisted curve E' of E is defined over an extension field F_p^2 by the equation E': y^2 = x^3 + b' with b' = b / m or b' = b * m. BN curves are called Dtype if b' = b / m, and Mtype if b' = b * m. The embedded degree k is 12. A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order r, G_2 as a subgroup of E'(F_p^2), and G_T as a subgroup of a multiplicative group (F_p^12)^* of order r. 2.4. BarretoLynnScott Curve A BLS curve [BLS02] is another instantiation of pairings proposed in 2002. Similar to BN curves, a pairing over BLS curves constructs optimal Ate pairings. Sakemi, et al. Expires 30 October 2020 [Page 7] InternetDraft PairingFriendly Curves April 2020 A BLS curve is defined by elliptic curves E and E' parameterized by a wellchosen integer t. E is defined over a finite field F_p by an equation of the form E: y^2 = x^3 + b, and its twisted curve, E': y^2 = x^3 + b', is defined in the same way as BN curves. In contrast to BN curves, E(F_p) does not have a prime order. Instead, its order is divisible by a large parameterized prime r and denoted by h * r with cofactor h. The pairing is defined on the rtorsions points. In the same way as BN curves, BLS curves can be categorized into Dtype and Mtype. BLS curves vary in accordance with different embedding degrees. In this memo, we deal with the BLS12 and BLS48 families with embedding degrees 12 and 48 with respect to r, respectively. In BLS curves, parameterized p and r are given by the following equations: BLS12: p = (t  1)^2 * (t^4  t^2 + 1) / 3 + t r = t^4  t^2 + 1 BLS48: p = (t  1)^2 * (t^16  t^8 + 1) / 3 + t r = t^16  t^8 + 1 for a well chosen integer t. A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order r, G_2 as an order r subgroup of E'(F_p^2) for BLS12 and of E'(F_p^8) for BLS48, and G_T as an order r subgroup of a multiplicative group (F_p^12)^* for BLS12 and of a multiplicative group (F_p^48)^* for BLS48. 2.5. Representation Convention for an Extension Field Pairingfriendly curves use a tower of some extension fields. In order to encode an element of an extension field, focusing on interoperability, we adopt the representation convention shown in Appendix J.4 of [ID.ietflwigcurverepresentations] as a standard and effective method. Let F_p be a finite field of characteristic p and F_p^d be an extension field of F_p of degree d and an indeterminate i. For an element s in F_p^d such that s = s_0 + s_1 * i + ... + s_{d  1} * i^{d  1} for s_0, s_1, ... , s_{d  1} in a basefield F_p, s is represented as octet string by oct(s) = s_0  s_1  ...  s_{d  1}. Sakemi, et al. Expires 30 October 2020 [Page 8] InternetDraft PairingFriendly Curves April 2020 Let F_p^d' be an extension field of F_p^d of degree d' / d and an indeterminate j. For an element s' in F_p^d' such that s' = s'_0 + s'_1 * j + ... + s'_{d' / d  1} * j^{d' / d  1} for s'_0, s'_1, ..., s'_{d' / d  1} in a basefield F_p^d, s' is represented as integer by oct(s') = oct(s'_0)  oct(s'_1)  ...  oct(s'_{d' / d  1}), where oct(s'_0), ... , oct(s'_{d' / d  1}) are octet strings encoded by above convention. In general, one can define encoding between integer and an element of any finite field tower by inductively applying the above convention. The parameters and test vectors of extension fields described in this memo are encoded by this convention and represented in octet stream. When applications communicate elements in an extension field, using the compression method [MP04] may be more effective. In that case, care for interoperability must be taken. 3. Security of PairingFriendly Curves 3.1. Evaluating the Security of PairingFriendly Curves The security of pairingfriendly curves is evaluated by the hardness of the following discrete logarithm problems. * The elliptic curve discrete logarithm problem (ECDLP) in G_1 and G_2 * The finite field discrete logarithm problem (FFDLP) in G_T There are other hard problems over pairingfriendly curves used for proving the security of pairingbased cryptography. Such problems include the computational bilinear DiffieHellman (CBDH) problem, bilinear DiffieHellman (BDH) problem, decision bilinear Diffie Hellman (DBDH) problem, gap DBDH problem, etc. [ECRYPT]. Almost all of these variants are reduced to the hardness of discrete logarithm problems described above and are believed to be easier than the discrete logarithm problems. Since such attacks where an attacker solves these reduced problems to break pairingbased cryptography have yet to be discovered, we discuss the hardness of the discrete logarithm problems in this memo. The security level of pairingfriendly curves is estimated by the computational cost of the most efficient algorithm to solve the above discrete logarithm problems. The wellknown algorithms for solving Sakemi, et al. Expires 30 October 2020 [Page 9] InternetDraft PairingFriendly Curves April 2020 the discrete logarithm problems include Pollard's rho algorithm [Pollard78], Index Calculus [HR83] and so on. To make index calculus algorithms more efficient, number field sieve (NFS) algorithms are utilized. 3.2. Impact of the Recent Attack In 2016, Kim and Barbulescu proposed a new variant of the NFS algorithms, the extended tower number field sieve (exTNFS), which drastically reduces the complexity of solving FFDLP [KB16]. Due to exTNFS, the security level of pairingfriendly curves asymptotically was reduced. For instance, Barbulescu and Duquesne estimated that the security of the BN curves, which had been believed to provide 128bit security (BN256, for example) was reducedto approximately 100 bits [BD18]. Some papers showed the minimum bit length of the parameters of pairingfriendly curves for each security level when applying exTNFS as an attacking method for FFDLP. For 128bit security, Barbulescu and Duquesne estimated the minimum bit length of p of BN curves and BLS12 curves after exTNFS as 461 bits [BD18]. For 256bit security, Kiyomura et al. estimated the minimum bit length of p^k of BLS48 curves as 27,410 bits, which indicated 572 bits of p [KIK17]. 4. Selection of PairingFriendly Curves In this section, we introduce secure pairingfriendly curves that consider the impact of exTNFS. First, we show the adoption status of pairingfriendly curves in standards, libraries and applications, and classify them in accordance with 128bit, 192bit, and 256bit security levels. Then, from the viewpoints of "security" and "widely used", pairingfriendly curves corresponding to each security level are selected and their parameters are indicated. In our selection policy, it is important that selected curves are shown in peerreviewed papers for security and that they are widely used in cryptographic libraries. In addition, "efficiency" is one of the important aspects but greatly depends on implementations, so we consider that the viewpoints of "security" and "widely used" are more important than "efficiency" when considering interconnections and interoperability on future Internet. 4.1. Adoption Status of Pairingfriendly Curves We show the pairingfriendly curves selected by existing standards, cryptographic libraries, and applications. Sakemi, et al. Expires 30 October 2020 [Page 10] InternetDraft PairingFriendly Curves April 2020 Table 1 summarizes the adoption status of pairingfriendly curves. The details are described in the following subsections. A BN curve with a XXXbit characteristic p is denoted as BNXXX and a BLS curve of embedding degree k with a XXXbit p is denoted as BLSk_XXX. Due to space limitations, Table 1 omits libraries that have not been maintained since 2016 in which exTNFS was proposed and curves with 128bit security or lower since before 2016 (ex. BN160). The full version of Table 1 is available at https://lepidum.co.jp/ blog/20200327/ietfdraftpfc/. In this table, the security level for each curve is evaluated in accordance with [BD18],[GME19], [MAF19] and [FK18]. Note that the curves marked as (*) indicate that the evaluation of the security level does not take into account the impact of the exTNFS because [BD18] does not show the security level of these curves. +++++  Category  Name  Curve Type  Sec      uri      ty      Lev      els      (bi      t)     +++++++     ~  Ard  ~  Ard  ~  Ard       128   192   256  +=============+==========+============+===+=====+===+=====+===+=====+  Standard  ISO/IEC  BN256I  X         ++++++++    BN384   X        ++++++++    BN512I    X       ++++++++    Freeman224   *        ++++++++    Freeman256   *        ++++++++    MNT256   *       +++++++++   TCG  BN256I  X         ++++++++    BN638    X      +++++++++   FIDO/W3C  BN256I  X         ++++++++    BN256D  X         ++++++++    BN512I    X     Sakemi, et al. Expires 30 October 2020 [Page 11] InternetDraft PairingFriendly Curves April 2020   ++++++++    BN638    X     ++++++++++  Library  mcl  BLS12_381   X        ++++++++    BN254N  X         ++++++++    BN_SNARK1  X         ++++++++    BN382M   X        ++++++++    BN462   X       +++++++++   TEPLA  BN254B  X         ++++++++    BN254N  X        +++++++++   RELIC  BLS12_381   X        ++++++++    BLS12_446   X        ++++++++    BLS12_455   X        ++++++++    BLS12_638    X       ++++++++    BLS24_477     X      ++++++++    BLS48_575       X    ++++++++    BN254N  X         ++++++++    BN256D  X         ++++++++    BN382R   X        ++++++++    BN446   X        ++++++++    BN638    X       ++++++++    CP8_544   X        ++++++++    K54_569       X    ++++++++    KSS18_508    X       ++++++++    OT8_511   X       +++++++++   AMCL  BLS12_381   X      Sakemi, et al. Expires 30 October 2020 [Page 12] InternetDraft PairingFriendly Curves April 2020   ++++++++    BLS12_383   X        ++++++++    BLS12_461   X        ++++++++    BLS24_479     X      ++++++++    BLS48_556       X    ++++++++    BN254N  X         ++++++++    BN254CX  X         ++++++++    BN256I  X         ++++++++    BN512I    X      +++++++++  Intel IPP  BN256I  X        +++++++++   Kyushu  BLS48_581       X    Univ.          +++++++++   MIRACL  BLS12_381   X        ++++++++    BLS12_383   X        ++++++++    BLS12_461   X        ++++++++    BLS24_479     X      ++++++++    BLS48_556       X    ++++++++    BLS48_581       X    ++++++++    BN254N  X         ++++++++    BN254CX  X         ++++++++    BN256I  X         ++++++++    BN462   X        ++++++++    BN512I    X      +++++++++   Adjoint  BLS12_381   X        ++++++++    BN_SNARK1  X         ++++++++ Sakemi, et al. Expires 30 October 2020 [Page 13] InternetDraft PairingFriendly Curves April 2020    BN254B  X         ++++++++    BN254N  X         ++++++++    BN254S1  X         ++++++++    BN254S2  X         ++++++++    BN462   X      ++++++++++  Application  Zcash  BLS12_381   X        ++++++++    BN_SNARK1  X        +++++++++   Ethereum  BLS12_381   X       +++++++++   Chia  BLS12_381   X        Network          +++++++++   DFINITY  BLS12_381   X        ++++++++    BN254N  X         ++++++++    BN_SNARK1  X         ++++++++    BN382M   X        ++++++++    BN462   X       +++++++++   Algorand  BLS12_381   X      ++++++++++ Table 1: Adoption Status of PairingFriendly Curves 4.1.1. International Standards ISO/IEC 15946 series specifies publickey cryptographic techniques based on elliptic curves. ISO/IEC 159465 [ISOIEC159465] shows numerical examples of MNT curves[MNT01] with 160bit p and 256bit p, Freeman curves [Freeman06] with 224bit p and 256bit p, and BN curves with 160bit p, 192bit p, 224bit p, 256bit p, 384bit p, and 512bit p. These parameters do not take into account the effects of the exTNFS. On the other hand, the parameters may be revised in future versions since ISO/IEC 159465 is currently under development. As described below, BN curves with 256bit p and 512bit p specified in ISO/IEC 159465 used by other standards and libraries, these curves are especially denoted as BN256I and BN512I. Sakemi, et al. Expires 30 October 2020 [Page 14] InternetDraft PairingFriendly Curves April 2020 TCG adopts the BN256I and a BN curve with 638bit p specified by their own[TPM]. FIDO Alliance [FIDO] and W3C [W3C] adopt BN256I, BN512I, the BN638 by TCG, and the BN curve with 256bit p proposed by Devegili et al.[DSD07] (named BN256D). 4.1.2. Cryptographic Libraries There are a lot of cryptographic libraries that support pairing calculations. PBC is a library for pairingbased cryptography published by Stanford University that supports BN curves, MNT curves, Freeman curves, and supersingular curves [PBC]. Users can generate pairing parameters by using PBC and use pairing operations with the generated parameters. mcl[mcl] is a library for pairingbased cryptography that supports four BN curves and BLS12_381. These BN curves include BN254 proposed by Nogami et al. [NASKM08] (named BN254N), BN_SNARK1 suitable for SNARK applications[libsnark], BN382M, and BN462. Kyushu University published a library that supports the BLS48_581 [BLS48]. The University of Tsukuba Elliptic Curve and Pairing Library (TEPLA) [TEPLA] supports two BN curves, BN254N and BN254 proposed by Beuchat et al. [BGMORT10] (named BN254B). Intel published a cryptographic library named Intel Integrated Performance Primitives (IntelIPP) [IntelIPP] and the library supports BN256I. RELIC [RELIC] uses various types of pairingfriendly curves that include six BN curves (BN158, BN254R, BN256R, BN382R, BN446, and BN638), where BN254R, BN256R, and BN382R are RELIC specific parameters that are different from BN254N, BN254B, BN256I, BN256D, and BN382M. In addition, RELIC supports six BLS curves (BLS12_381, BLS12_446, BLS12_445, BLS12_638, BLS24_477, and BLS48_575 [MAF19]), CocksPinch curves of embedding degree 8 with 544bit p[GME19], pairingfriendly curves constructed by Scott et al. [SG19] based on KachisaScottSchaefer curves with embedding degree 54 with 569bit p (named K54_569)[MAF19], a KSS curve [KSS08] of embedding degree 18 with 508bit p (named KSS18_508) [AFKMR12], Optimal TNFSsecure curve [FM19] of embedding degree 8 with 511bit p(OT8_511), and a supersingular curve [S86] with 1536bit p (SS_1536). Apache Milagro Crypto Library (AMCL)[AMCL] supports four BLS curves (BLS12_381, BLS12_461, BLS24_479 and BLS48_556) and four BN curves (BN254N, BN254CX proposed by CertiVox, BN256I, and BN512I). In addition to AMCL's supported curves, MIRACL[MIRACL] supports BN462 and BLS48_581. Sakemi, et al. Expires 30 October 2020 [Page 15] InternetDraft PairingFriendly Curves April 2020 Adjoint published a library that supports the BLS12_381 and six BN curves (BN_SNARK1, BN254B, BN254N, BN254S1, BN254S2, and BN462) [AdjointLib], where BN254S1 and BN254S2 are BN curves adopted by an old version of AMCL [AMCLv2]. 4.1.3. Applications Several applications adopt pairingfriendly curves such as BN curves and BLS curves. Zcash implements a BN curve (named BN128) in their library libsnark [libsnark]. After exTNFS, they proposed a new parameter of BLS12 as BLS12_381 [BLS12381] and published its experimental implementation [zkcrypto]. Ethereum 2.0 adopts the BLS12_381 and uses an implementation by Meyer[pureGobls]. Chia Network published their implementation [Chia] by integrating the RELIC toolkit [RELIC]. DFINITY uses mcl, and Algorand published their implementation that supports BLS12_381. 4.2. For 128bit Security Table 1 shows that a lot of pairingfriendly curves whose types are BN and BLS are adopted as 128bit security level curves. Among them, the one that best matches our selection policy is BN462, so we introduce the parameters of BN462 in this section. On the other hand, from the viewpoint of "widely used", BLS12_381 is an attractive curve because a lot of libraries and applications adopt it. However, because it is not published as a 128bit security level curve in peerreviewed papers, it does not match our selection policy. In addition, according to [BD18], the bit length of p for BLS12 to achieve 128bit security is calculated as 461 bits and more, which BLS12_381 does not satisfy. Since BLS12_381 has a large effect from the viewpoint of interoperability, we introduce parameters of BLS12_381 in Appendix C. 4.2.1. BN Curves A BN curve with 128bit security is shown in [BD18], which we call BN462. BN462 is defined by the following parameter t = 2^114 + 2^101  2^14  1 for the definition in Section 2.3. For the finite field F_p, the towers of extension field F_p^2, F_p^6 and F_p^12 are defined by indeterminates u, v, and w as follows: Sakemi, et al. Expires 30 October 2020 [Page 16] InternetDraft PairingFriendly Curves April 2020 F_p^2 = F_p[u] / (u^2 + 1) F_p^6 = F_p^2[v] / (v^3  u  2) F_p^12 = F_p^6[w] / (w^2  v). Defined by t, the elliptic curve E and its twisted curve E' are represented by E: y^2 = x^3 + 5 and E': y^2 = x^3  u + 2, respectively. The size of p becomes 462bit length. A pairing e is defined by taking G_1 as a cyclic group of order r generated by a base point BP = (x, y) in F_p, G_2 as a cyclic group of order r generated by a base point BP' = (x', y') in F_p^2, and G_T as a subgroup of a multiplicative group (F_p^12)^* of order r. BN462 is Dtype. We give the following parameters for BN462. * G_1 defined over E: y^2 = x^3 + b  p: a characteristic  r: an order  BP = (x, y): a base point  h: a cofactor  b: a coefficient of E * G_2 defined over E': y^2 = x^3 + b'  r': an order  BP' = (x', y') : a base point (encoded with [ID.ietflwigcurverepresentations]) o x' = x'_0 + x'_1 * u (x'_0, x'_1 in F_p) o y' = y'_0 + y'_1 * u (y'_0, y'_1 in F_p)  h': a cofactor  b': a coefficient of E' p: 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908f41c802 0ffffffffff6ff66fc6ff687f640000000002401b00840138013 Sakemi, et al. Expires 30 October 2020 [Page 17] InternetDraft PairingFriendly Curves April 2020 r: 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908ee1c201 f7fffffffff6ff66fc7bf717f7c0000000002401b007e010800d x: 0x21a6d67ef250191fadba34a0a30160b9ac9264b6f95f63b3edbec3cf4b2e689d b1bbb4e69a416a0b1e79239c0372e5cd70113c98d91f36b6980d y: 0x0118ea0460f7f7abb82b33676a7432a490eeda842cccfa7d788c659650426e6a f77df11b8ae40eb80f475432c66600622ecaa8a5734d36fb03de h: 1 b: 5 r': 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908ee1c201 f7fffffffff6ff66fc7bf717f7c0000000002401b007e010800d x'_0: 0x0257ccc85b58dda0dfb38e3a8cbdc5482e0337e7c1cd96ed61c913820408208f 9ad2699bad92e0032ae1f0aa6a8b48807695468e3d934ae1e4df x'_1: 0x1d2e4343e8599102af8edca849566ba3c98e2a354730cbed9176884058b18134 dd86bae555b783718f50af8b59bf7e850e9b73108ba6aa8cd283 y'_0: 0x0a0650439da22c1979517427a20809eca035634706e23c3fa7a6bb42fe810f13 99a1f41c9ddae32e03695a140e7b11d7c3376e5b68df0db7154e y'_1: 0x073ef0cbd438cbe0172c8ae37306324d44d5e6b0c69ac57b393f1ab370fd725c c647692444a04ef87387aa68d53743493b9eba14cc552ca2a93a h': 0x240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908fa1ce02 27fffffffff6ff66fc63f5f7f4c0000000002401b008a0168019 b': u + 2 Sakemi, et al. Expires 30 October 2020 [Page 18] InternetDraft PairingFriendly Curves April 2020 4.3. For 192bit Security As shown in Table 1, candidates of pairingfriendly curves for 192bit security are only two curves: BLS24_477 and BLS24_479. BLS24_477 has only one implementation and BLS24_479 is an experimental parameter that is not shown in peerreviewed papers. Therefore, because none match our selection policy, we could not show the parameters for 192bit security here. 4.4. For 256bits Security As shown in Table 1, there are three candidates of pairingfriendly curves for 256bit security. According to our selection policy, we select BLS48_581, which is the most adopted by cryptographic libraries. The selected BLS48 curve is shown in [KIK17] and it is defined by the following parameter t = 1 + 2^7  2^10  2^30  2^32. For the finite field F_p, the towers of extension field F_p^2, F_p^4, F_p^8, F_p^24 and F_p^48 are defined by indeterminates u, v, w, z, and s as follows: F_p^2 = F_p[u] / (u^2 + 1) F_p^4 = F_p^2[v] / (v^2 + u + 1) F_p^8 = F_p^4[w] / (w^2 + v) F_p^24 = F_p^8[z] / (z^3 + w) F_p^48 = F_p^24[s] / (s^2 + z). The elliptic curve E and its twisted curve E' are represented by E: y^2 = x^3 + 1 and E': y^2 = x^3  1 / w. A pairing e is defined by taking G_1 as a cyclic group of order r generated by a base point BP = (x, y) in F_p, G_2 as a cyclic group of order r generated by a base point BP' = (x', y') in F_p^8, and G_T as a subgroup of a multiplicative group (F_p^48)^* of order r. The size of p becomes 581bit length. BLS48581 is Dtype. We then give the parameters for BLS48581 as follows. * G_1 defined over E: y^2 = x^3 + b  p: a characteristic  r: a prime which divides an order of G_1  BP = (x, y): a base point Sakemi, et al. Expires 30 October 2020 [Page 19] InternetDraft PairingFriendly Curves April 2020  h: a cofactor  b: a coefficient of E * G_2 defined over E': y^2 = x^3 + b'  r': an order  BP'= (x', y') : a base point (encoded with [ID.ietflwigcurverepresentations]) o x' = x'_0 + x'_1 * u + x'_2 * v + x'_3 * u * v + x'_4 * w + x'_5 * u * w + x'_6 * v * w + x'_7 * u * v * w (x'_0, ..., x'_7 in F_p) o y' = y'_0 + y'_1 * u + y'_2 * v + y'_3 * u * v + y'_4 * w + y'_5 * u * w + y'_6 * v * w + y'_7 * u * v * w (y'_0, ..., y'_7 in F_p)  h': a cofactor  b': a coefficient of E' p: 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444 a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac 3edc154e6565912b r: 0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6 e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c01 x: 0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7 544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d8c 3bce8732315af640 y: 0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279dd41b720e f7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f37aef7b926b57 6dbb5de3e2587a70 x'_0: 0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156 c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154de c34fd0b4ace8bfab Sakemi, et al. Expires 30 October 2020 [Page 20] InternetDraft PairingFriendly Curves April 2020 x'_1: 0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e 1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa143f 1669b36676b47c57 x'_2: 0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccbab5ab 6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3f0b4 6488156ca55a3e6a x'_3: 0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f8be0 cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80bc3f 09a7033cbb7feafe x'_4: 0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386 699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb 739c3a1c53f8cce5 x'_5: 0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb03741 8181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce3370 f2004d914a3c093a x'_6: 0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0b7a4 49cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c3354 e41607e60750e057 x'_7: 0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7 f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3f8 4e19da00fbc6ae34 y'_0: 0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc435fa ab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c0ff3 23edd3fe4d2d7971 y'_1: 0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d72964732fcb f3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ffc7b1 11471db936cd5665 Sakemi, et al. Expires 30 October 2020 [Page 21] InternetDraft PairingFriendly Curves April 2020 y'_2: 0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d370514 475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b8fde 68332a526a2a8474 y'_3: 0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e122d2 742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e53373 16213da92841589d y'_4: 0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f112985 7ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf7a43 f47831f982e50137 y'_5: 0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055ab750 4fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226cf3a5 94eedc58cf90bee4 y'_6: 0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c819a6 df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9aa62b 3d41faeafeb23986 y'_7: 0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8eca9a 9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e84069c55 d667ffcb732718b6 h: 0x85555841aaaec4ac b: 1 r': 0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6 e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c01 h': 0x170e915cb0a6b7406b8d94042317f811d6bc3fc6e211ada42e58ccfcb3ac076a 7e4499d700a0c23dc4b0c078f92def8c87b7fe63e1eea270db353a4ef4d38b5998 ad8f0d042ea24c8f02be1c0c83992fe5d7725227bb27123a949e0876c0a8ce0a67 326db0e955dcb791b867f31d6bfa62fbdd5f44a00504df04e186fae033f1eb43c1 b1a08b6e086eff03c8fee9ebdd1e191a8a4b0466c90b389987de5637d5dd13dab3 3196bd2e5afa6cd19cf0fc3fc7db7ece1f3fac742626b1b02fcee04043b2ea9649 2f6afa51739597c54bb78aa6b0b99319fef9d09f768831018ee6564c68d054c62f 2e0b4549426fec24ab26957a669dba2a2b6945ce40c9aec6afdeda16c79e15546c d7771fa544d5364236690ea06832679562a68731420ae52d0d35a90b8d10b688e3 Sakemi, et al. Expires 30 October 2020 [Page 22] InternetDraft PairingFriendly Curves April 2020 1b6aee45f45b7a5083c71732105852decc888f64839a4de33b99521f0984a418d2 0fc7b0609530e454f0696fa2a8075ac01cc8ae3869e8d0fe1f3788ffac4c01aa27 20e431da333c83d9663bfb1fb7a1a7b90528482c6be7892299030bb51a51dc7e91 e9156874416bf4c26f1ea7ec578058563960ef92bbbb8632d3a1b695f954af10e9 a78e40acffc13b06540aae9da5287fc4429485d44e6289d8c0d6a3eb2ece350124 52751839fb48bc14b515478e2ff412d930ac20307561f3a5c998e6bcbfebd97eff c6433033a2361bfcdc4fc74ad379a16c6dea49c209b1 b': 1 / w 5. Security Considerations The recommended pairingfriendly curves are selected by considering the exTNFS proposed by Kim et al. in 2016 [KB16] and they are categorized in each security level in accordance with [BD18]. Implementers who will newly develop pairingbased cryptography applications SHOULD use the recommended parameters. As of 2020, as far as we know, there are no fatal attacks that significantly reduce the security of pairingfriendly curves after exTNFS. BLS curves of embedding degree 12 require a characteristic p of 461 bits or larger to achieve 128bit security level [BD18]. Note that the security level of BLS12381, which is adopted by a lot of libraries and applications, is slightly below 128 bits because a 381bit characteristic is used. BN254 is used in most of the existing implementations as shown in Table 1, however, BN curves that were estimated as a 128bit security level before exTNFS including BN254 ensure no more than a 100bit security level by the effect of exTNFS. Implementers MAY use pairingfriendly curves with 100bit security only if they need to keep interoperability with the existing applications. 6. IANA Considerations This document has no actions for IANA. 7. Acknowledgements The authors would like to thank Akihiro Kato and Shoko Yonezawa for their significant contribution to an early version of this memo. The authors would also like to acknowledge Sakae Chikara, Kim Taechan, Hoeteck Wee, Sergey Gorbunov, and Michael Scott for their valuable comments. 8. References 8.1. Normative References Sakemi, et al. Expires 30 October 2020 [Page 23] InternetDraft PairingFriendly Curves April 2020 [BD18] Barbulescu, R. and S. Duquesne, "Updating Key Size Estimations for Pairings", DOI 10.1007/s0014501892805, Journal of Cryptology, January 2018, <https://doi.org/10.1007/s0014501892805>. [BLS02] Barreto, P., Lynn, B., and M. Scott, "Constructing Elliptic Curves with Prescribed Embedding Degrees", DOI 10.1007/3540364137_19, Security in Communication Networks pp. 257267, 2003, <https://doi.org/10.1007/3540364137_19>. [BN05] Barreto, P. and M. Naehrig, "PairingFriendly Elliptic Curves of Prime Order", DOI 10.1007/11693383_22, Selected Areas in Cryptography pp. 319331, 2006, <https://doi.org/10.1007/11693383_22>. [KB16] Kim, T. and R. Barbulescu, "Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case", DOI 10.1007/9783662530184_20, Advances in Cryptology  CRYPTO 2016 pp. 543571, 2016, <https://doi.org/10.1007/9783662530184_20>. [KIK17] Kiyomura, Y., Inoue, A., Kawahara, Y., Yasuda, M., Takagi, T., and T. Kobayashi, "Secure and Efficient Pairing at 256Bit Security Level", DOI 10.1007/9783319612041_4, Applied Cryptography and Network Security pp. 5979, 2017, <https://doi.org/10.1007/9783319612041_4>. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfceditor.org/info/rfc2119>. [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfceditor.org/info/rfc8174>. [Ver09] Vercauteren, F., "Optimal Pairings", DOI 10.1109/tit.2009.2034881, IEEE Transactions on Information Theory Vol. 56, pp. 455461, January 2010, <https://doi.org/10.1109/tit.2009.2034881>. 8.2. Informative References [AdjointLib] Adjoint Inc., "Optimised bilinear pairings over elliptic curves", 2018, <https://github.com/adjointio/pairing>. Sakemi, et al. Expires 30 October 2020 [Page 24] InternetDraft PairingFriendly Curves April 2020 [AFKMR12] Aranha, D.F., FuentesCastaneda, L., Knapp, E., Menezes, A., and F. RodríguezHenríquez, "Implementing Pairings at the 192Bit Security Level", DOI /10.1007/9783642363344_11, Pairing 2012 pp. 177195, 2012, <https://doi.org//10.1007/9783642363344_11>. [Algorand] Gorbunov, S., "Efficient and Secure Digital Signatures for ProofofStake Blockchains", <https://medium.com/algorand/ digitalsignaturesforblockchains5820e15fbe95>. [AMCL] The Apache Software Foundation, "The Apache Milagro Cryptographic Library (AMCL)", 2016, <https://github.com/apache/incubatormilagrocrypto>. [AMCLv2] The Apache Software Foundation, "Old version of the Apache Milagro Cryptographic Library", 2016, <https://github.com/miracl/amcl/tree/master/version22>. [BGMORT10] Beuchat, J., GonzálezDíaz, J., Mitsunari, S., Okamoto, E., RodríguezHenríquez, F., and T. Teruya, "HighSpeed Software Implementation of the Optimal Ate Pairing over BarretoNaehrig Curves", DOI 10.1007/9783642174551_2, Pairing 2010 pp. 2139, 2010, <https://doi.org/10.1007/9783642174551_2>. [BL10] Brickell, E. and J. Li, "Enhanced Privacy ID from Bilinear Pairing for Hardware Authentication and Attestation", DOI 10.1109/socialcom.2010.118, 2010 IEEE Second International Conference on Social Computing, August 2010, <https://doi.org/10.1109/socialcom.2010.118>. [BLS12381] Bowe, S., "BLS12381: New zkSNARK Elliptic Curve Construction", <https://electriccoin.co/blog/newsnarkcurve/>. [BLS48] Kyushu University, "bls48  C++ library for Optimal Ate Pairing on BLS48", 2017, <https://github.com/mkmathkyushu/bls48>. [CCS07] Chen, L., Cheng, Z., and N. Smart, "Identitybased key agreement protocols from pairings", DOI 10.1007/s1020700600119, International Journal of Information Security Vol. 6, pp. 213241, January 2007, <https://doi.org/10.1007/s1020700600119>. Sakemi, et al. Expires 30 October 2020 [Page 25] InternetDraft PairingFriendly Curves April 2020 [Chia] Chia Network, "BLS signatures in C++, using the relic toolkit", <https://github.com/ChiaNetwork/blssignatures>. [CIRCL] Cloudflare, "CIRCL: Cloudflare Interoperable, Reusable Cryptographic Library", 2019, <https://github.com/cloudflare/circl>. [Cloudflare] Sullivan, N., "Geo Key Manager: How It Works", <https://blog.cloudflare.com/geokeymanagerhowit works/>. [DFINITY] Williams, D., "DFINITY Technology Overview Series Consensus System Rev. 1", n.d., <https://dfinity.org/pdf viewer/library/dfinityconsensus.pdf>. [DSD07] Devegili, A. J., Scott, M., and R. Dahab, "Implementing Cryptographic Pairings over BarretoNaehrig Curves", DOI 10.1007/9783540734895_10, Pairing 2007 pp. 197207, 2007, <https://doi.org/10.1007/9783540734895_10>. [ECRYPT] ECRYPT, "Final Report on Main Computational Assumptions in Cryptography". [EPID] Intel Corporation, "Intel (R) SGX: Intel (R) EPID Provisioning and Attestation Services", <https://software.intel.com/enus/download/intelsgx intelepidprovisioningandattestationservices>. [Ethereum] Jordan, R., "Ethereum 2.0 Development Update #17  Prysmatic Labs", <https://medium.com/prysmaticlabs/ ethereum20developmentupdate17prysmaticlabs ed5bcf82ec00>. [FIDO] Lindemann, R., "FIDO ECDAA Algorithm  FIDO Alliance Review Draft 02", <https://fidoalliance.org/specs/fido v2.0rd20180702/fidoecdaaalgorithmv2.0rd 20180702.html>. [FK18] Fotiadis, G. and E. Konstantinou, "TNFS Resistant Families of PairingFriendly Elliptic Curves", Cryptology ePrint Archive Report 2018/1017, 2018, <https://eprint.iacr.org/2018/1017.pdf>. Sakemi, et al. Expires 30 October 2020 [Page 26] InternetDraft PairingFriendly Curves April 2020 [FM19] Fotiadis, G. and C. Martindale, "Optimal TNFSsecure pairings on elliptic curves with composite embedding degree", Cryptology ePrint Archive Report 2019/555, 2019, <https://eprint.iacr.org/2019/555.pdf>. [Freeman06] Freeman, D., "Constructing pairingfriendly elliptic curves with embedding degree 10", DOI 10.1007/11792086_32, ANTS 2006 pp. 452465, 2006, <https://doi.org/10.1007/11792086_32>. [FSU10] Fujioka, A., Suzuki, K., and B. Ustaoglu, "Ephemeral Key Leakage Resilient and Efficient IDAKEs That Can Share Identities, Private and Master Keys", DOI 10.1007/9783642174551_12, Lecture Notes in Computer Science pp. 187205, 2010, <https://doi.org/10.1007/9783642174551_12>. [GME19] Guillevic, A., Masson, S., and E. Thome, "CocksPinch curves of embedding degrees five to eight and optimal ate pairing computation", Cryptology ePrint Archive Report 2019/431, 2019, <https://eprint.iacr.org/2019/431.pdf>. [HR83] Hellman, M. and J. Reyneri, "Fast Computation of Discrete Logarithms in GF (q)", DOI 10.1007/9781475706024_1, Advances in Cryptology pp. 313, 1983, <https://doi.org/10.1007/9781475706024_1>. [ID.bonehblssignature] Boneh, D., Gorbunov, S., Wee, H., and Z. Zhang, "BLS Signature Scheme", Work in Progress, InternetDraft, draftbonehblssignature00, 8 February 2019, <https://tools.ietf.org/html/draftbonehblssignature 00>. [ID.ietflwigcurverepresentations] Struik, R., "Alternative Elliptic Curve Representations", Work in Progress, InternetDraft, draftietflwigcurve representations08, 24 July 2019, <https://tools.ietf.org/html/draftietflwigcurve representations08>. [IntelIPP] Intel Corporation, "Developer Reference for Intel Integrated Performance Primitives Cryptography 2019", 2018, <https://software.intel.com/enus/ippcrypto referencearithmeticofthegroupofellipticcurve points>. Sakemi, et al. Expires 30 October 2020 [Page 27] InternetDraft PairingFriendly Curves April 2020 [ISOIEC117703] ISO/IEC, "ISO/IEC 117703:2015", ISO/IEC Information technology  Security techniques  Key management  Part 3: Mechanisms using asymmetric techniques, 2015. [ISOIEC159465] ISO/IEC, "ISO/IEC 159465:2017", ISO/IEC Information technology  Security techniques  Cryptographic techniques based on elliptic curves  Part 5: Elliptic curve generation, 2017. [Joux00] Joux, A., "A One Round Protocol for Tripartite Diffie Hellman", DOI 10.1007/10722028_23, Lecture Notes in Computer Science pp. 385393, 2000, <https://doi.org/10.1007/10722028_23>. [KSS08] Kachisa, E., Schaefer, E., and M. Scott, "Constructing BrezingWeng PairingFriendly Elliptic Curves Using Elements in the Cyclotomic Field", DOI 10.1007/9783540855385_9, Pairing 2008 pp. 126135, 2008, <https://doi.org/10.1007/9783540855385_9>. [libsnark] SCIPR Lab, "libsnark: a C++ library for zkSNARK proofs", 2012, <https://github.com/zcash/libsnark>. [MPin] Scott, M., "MPin: A MultiFactor Zero Knowledge Authentication Protocol", July 2019, <https://www.miracl.com/miracllabs/mpinamultifactor zeroknowledgeauthenticationprotocol>. [MAF19] Mbiang, N.B., Aranha, D.F., and E. Fouotsa, "Computing the Optimal Ate Pairing over Elliptic Curves with Embedding Degrees 54 and 48 at the 256bit security level", International Journal of Applied Cryptography to appear, 2019, <https://www.researchgate.net/publication/337011283_ Computing_the_Optimal_Ate_Pairing_over_Elliptic_Curves_wit h_Embedding_Degrees_54_and_48_at_the_256bit_security_leve l>. [mcl] Mitsunari, S., "mcl  A portable and fast pairingbased cryptography library", 2016, <https://github.com/herumi/mcl>. [MIRACL] MIRACL Ltd., "The MIRACL Core Cryptographic Library", 2019, <https://github.com/miracl/core>. Sakemi, et al. Expires 30 October 2020 [Page 28] InternetDraft PairingFriendly Curves April 2020 [MNT01] Miyaji, A., Nakabayashi, M., and S. Takano, "New explicit conditions of Elliptic Curve Traces under FR reduction", IEICE Trans. Fundamentals. E84A(5) pp. 12341243, 2001. [MP04] Guillevic, A., Masson, S., and E. Thome, "CocksPinch curves of embedding degrees five to eight and optimal ate pairing computation", Cryptology ePrint Archive Report 2019/431, 2019, <https://eprint.iacr.org/2004/032.pdf>. [NASKM08] Nogami, Y., Akane, M., Sakemi, Y., Kato, H., and Y. Morikawa, "Integer Variable XBased Ate Pairing", DOI 10.1007/9783540855385_13, Pairing 2008 pp. 178191, 2008, <https://doi.org/10.1007/9783540855385_13>. [PBC] Lynn, B., "PBC Library  The PairingBased Cryptography Library", 2006, <https://crypto.stanford.edu/pbc/>. [Pollard78] Pollard, J., "Monte Carlo methods for index computation $({\rm mod}\ p)$", DOI 10.1090/s00255718197804914319, Mathematics of Computation Vol. 32, pp. 918918, September 1978, <https://doi.org/10.1090/s00255718197804914319>. [pureGobls] Meyer, J., "Pure GO bls library", 2019, <https://github.com/phoreproject/bls>. [RELIC] Gouvea, C.P.L., "RELIC is an Efficient LIbrary for Cryptography", 2013, <https://github.com/relictoolkit/relic>. [RFC5091] Boyen, X. and L. Martin, "IdentityBased Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems", RFC 5091, DOI 10.17487/RFC5091, December 2007, <https://www.rfceditor.org/info/rfc5091>. [RFC6508] Groves, M., "SakaiKasahara Key Encryption (SAKKE)", RFC 6508, DOI 10.17487/RFC6508, February 2012, <https://www.rfceditor.org/info/rfc6508>. [RFC6509] Groves, M., "MIKEYSAKKE: SakaiKasahara Key Encryption in Multimedia Internet KEYing (MIKEY)", RFC 6509, DOI 10.17487/RFC6509, February 2012, <https://www.rfceditor.org/info/rfc6509>. Sakemi, et al. Expires 30 October 2020 [Page 29] InternetDraft PairingFriendly Curves April 2020 [RFC6539] Cakulev, V., Sundaram, G., and I. Broustis, "IBAKE: IdentityBased Authenticated Key Exchange", RFC 6539, DOI 10.17487/RFC6539, March 2012, <https://www.rfceditor.org/info/rfc6539>. [S86] Silverman, J. H., "The arithmetic of elliptic curves", Springer GTM 106, 1986. [SAKKE] 3GPP, "Security of the mission critical service (Release 15)", 3GPP TS 33.180 15.3.0, 2018. [SG19] Scott, M. and A. Guillevic, "A New Family of Pairing Friendly elliptic curves", Cryptology ePrint Archive Report 2019/193, 2019, <https://eprint.iacr.org/2018/193.pdf>. [TEPLA] University of Tsukuba, "TEPLA: University of Tsukuba Elliptic Curve and Pairing Library", 2013, <http://www.cipher.risk.tsukuba.ac.jp/tepla/index_e.html>. [TPM] Trusted Computing Group (TCG), "Trusted Platform Module Library Specification, Family \"2.0\", Level 00, Revision 01.38", <https://trustedcomputinggroup.org/resource/tpm libraryspecification/>. [W3C] Lundberg, E., "Web Authentication: An API for accessing Public Key Credentials Level 1  W3C Recommendation", <https://www.w3.org/TR/webauthn/>. [Zcash] Lindemann, R., "What are zkSNARKs?", <https://z.cash/technology/zksnarks.html>. [zkcrypto] zkcrypto, "zkcrypto  Pairingfriendly elliptic curve library", 2017, <https://github.com/zkcrypto/pairing>. Appendix A. Computing Optimal Ate Pairing Before presenting the computation of optimal Ate pairing e(P, Q) satisfying the properties shown in Section 2.2, we give subfunctions used for the pairing computation. The following algorithm, Line_Function shows the computation of the line function. It takes A = (A[1], A[2]), B = (B[1], B[2]) in G_2, and P = ((P[1], P[2])) in G_1 as input, and outputs an element of G_T. Sakemi, et al. Expires 30 October 2020 [Page 30] InternetDraft PairingFriendly Curves April 2020 if (A = B) then l := (3 * A[1]^2) / (2 * A[2]); else if (A = B) then return P[1]  A[1]; else l := (B[2]  A[2]) / (B[1]  A[1]); end if; return (l * (P[1] A[1]) + A[2] P[2]); When implementing the line function, implementers should consider the isomorphism of E and its twisted curve E' so that one can reduce the computational cost of operations in G_2. We note that Line_function does not consider such isomorphism. Computation of optimal Ate pairing for BN curves uses a Frobenius map. Let a Frobenius map pi for a point Q = (x, y) over E' be pi(p, Q) = (x^p, y^p). A.1. Optimal Ate Pairings over BarretoNaehrig Curves Let c = 6 * t + 2 for a parameter t and c_0, c_1, ... , c_L in {1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., L) equals c. The following algorithm shows the computation of optimal Ate pairing over BN curves. It takes P in G_1, Q in G_2, an integer c, c_0, ...,c_L in {1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., L) equals c, and an order r as input, and outputs e(P, Q). f := 1; T := Q; if (c_L = 1) T := T; end if for i = L1 to 0 f := f^2 * Line_function(T, T, P); T := 2 * T; if (c_i = 1  c_i = 1) f := f * Line_function(T, c_i * Q); T := T + c_i * Q; end if end for Q_1 := pi(p, Q); Q_2 := pi(p, Q_1); f := f * Line_function(T, Q_1, P); T := T + Q_1; f := f * Line_function(T, Q_2, P); f := f^{(p^k  1) / r} return f; Sakemi, et al. Expires 30 October 2020 [Page 31] InternetDraft PairingFriendly Curves April 2020 A.2. Optimal Ate Pairings over BarretoLynnScott Curves Let c = t for a parameter t and c_0, c_1, ... , c_L in {1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., L) equals c. The following algorithm shows the computation of optimal Ate pairing over Barreto LynnScott curves. It takes P in G_1, Q in G_2, a parameter c, c_0, c_1, ..., c_L in {1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., L), and an order r as input, and outputs e(P, Q). f := 1; T := Q; if (c_L = 1) T := T; end if for i = L1 to 0 f := f^2 * Line_function(T, T, P); T := 2 * T; if (c_i = 1  c_i = 1) f := f * Line_function(T, c_i * Q, P); T := T + c_i * Q; end if end for f := f^{(p^k  1) / r}; return f; Appendix B. Test Vectors of Optimal Ate Pairing We provide test vectors for Optimal Ate Pairing e(P, Q) given in Appendix A for the curves BN462 and BLS48581 given in Section 4. Here, the inputs P = (x, y) and Q = (x', y') are the corresponding base points BP and BP' given in Section 4. For BN462, Q = (x', y') is given by x' = x'_0 + x'_1 * u and y' = y'_0 + y'_1 * u, where u is an indeterminate and x'_0, x'_1, y'_0, y'_1 are elements of F_p. For BLS48581, Q = (x', y') is given by x' = x'_0 + x'_1 * u + x'_2 * v + x'_3 * u * v + x'_4 * w + x'_5 * u * w + x'_6 * v * w + x'_7 * u * v * w and y' = y'_0 + y'_1 * u + y'_2 * v + y'_3 * u * v + y'_4 * w + y'_5 * u * w + y'_6 * v * w + y'_7 * u * v * w, where u, v, and w are indeterminates, and x'_0, ..., x'_7 and y'_0, ..., y'_7 are elements of F_p. The representation of Q = (x', y') given below is followed by [ID.ietflwigcurverepresentations]. Sakemi, et al. Expires 30 October 2020 [Page 32] InternetDraft PairingFriendly Curves April 2020 BN462: Input x value: 0x21a6d67ef250191fadba34a0a30160b9ac9264b6f95f63b3edbec3cf4b2e689d b1bbb4e69a416a0b1e79239c0372e5cd70113c98d91f36b6980d Input y value: 0x0118ea0460f7f7abb82b33676a7432a490eeda842cccfa7d788c659650426e6a f77df11b8ae40eb80f475432c66600622ecaa8a5734d36fb03de Input x'_0 value: 0x0257ccc85b58dda0dfb38e3a8cbdc5482e0337e7c1cd96ed61c913820408208f 9ad2699bad92e0032ae1f0aa6a8b48807695468e3d934ae1e4df Input x'_1 value: 0x1d2e4343e8599102af8edca849566ba3c98e2a354730cbed9176884058b18134 dd86bae555b783718f50af8b59bf7e850e9b73108ba6aa8cd283 Input y'_0 value: 0x0a0650439da22c1979517427a20809eca035634706e23c3fa7a6bb42fe810f13 99a1f41c9ddae32e03695a140e7b11d7c3376e5b68df0db7154e Input y'_1 value: 0x073ef0cbd438cbe0172c8ae37306324d44d5e6b0c69ac57b393f1ab370fd725c c647692444a04ef87387aa68d53743493b9eba14cc552ca2a93a e_0: 0x0cf7f0f2e01610804272f4a7a24014ac085543d787c8f8bf07059f93f87ba7e2 a4ac77835d4ff10e78669be39cd23cc3a659c093dbe3b9647e8c e_1: 0x00ef2c737515694ee5b85051e39970f24e27ca278847c7cfa709b0df408b830b 3763b1b001f1194445b62d6c093fb6f77e43e369edefb1200389 e_2: 0x04d685b29fd2b8faedacd36873f24a06158742bb2328740f93827934592d6f17 23e0772bb9ccd3025f88dc457fc4f77dfef76104ff43cd430bf7 e_3: 0x090067ef2892de0c48ee49cbe4ff1f835286c700c8d191574cb424019de11142 b3c722cc5083a71912411c4a1f61c00d1e8f14f545348eb7462c e_4: 0x1437603b60dce235a090c43f5147d9c03bd63081c8bb1ffa7d8a2c31d6732308 60bb3dfe4ca85581f7459204ef755f63cba1fbd6a4436f10ba0e Sakemi, et al. Expires 30 October 2020 [Page 33] InternetDraft PairingFriendly Curves April 2020 e_5: 0x13191b1110d13650bf8e76b356fe776eb9d7a03fe33f82e3fe5732071f305d20 1843238cc96fd0e892bc61701e1844faa8e33446f87c6e29e75f e_6: 0x07b1ce375c0191c786bb184cc9c08a6ae5a569dd7586f75d6d2de2b2f075787e e5082d44ca4b8009b3285ecae5fa521e23be76e6a08f17fa5cc8 e_7: 0x05b64add5e49574b124a02d85f508c8d2d37993ae4c370a9cda89a100cdb5e1d 441b57768dbc68429ffae243c0c57fe5ab0a3ee4c6f2d9d34714 e_8: 0x0fd9a3271854a2b4542b42c55916e1faf7a8b87a7d10907179ac7073f6a1de04 4906ffaf4760d11c8f92df3e50251e39ce92c700a12e77d0adf3 e_9: 0x17fa0c7fa60c9a6d4d8bb9897991efd087899edc776f33743db921a689720c82 257ee3c788e8160c112f18e841a3dd9a79a6f8782f771d542ee5 e_10: 0x0c901397a62bb185a8f9cf336e28cfb0f354e2313f99c538cdceedf8b8aa22c2 3b896201170fc915690f79f6ba75581f1b76055cd89b7182041c e_11: 0x20f27fde93cee94ca4bf9ded1b1378c1b0d80439eeb1d0c8daef30db0037104a 5e32a2ccc94fa1860a95e39a93ba51187b45f4c2c50c16482322 BLS48581: Input x value: 0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7 544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d8c 3bce8732315af640 Input y value: 0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279dd41b720e f7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f37aef7b926b57 6dbb5de3e2587a70 x'_0: 0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156 c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154de c34fd0b4ace8bfab Sakemi, et al. Expires 30 October 2020 [Page 34] InternetDraft PairingFriendly Curves April 2020 x'_1: 0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e 1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa143f 1669b36676b47c57 x'_2: 0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccbab5ab 6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3f0b4 6488156ca55a3e6a x'_3: 0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f8be0 cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80bc3f 09a7033cbb7feafe x'_4: 0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386 699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb 739c3a1c53f8cce5 x'_5: 0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb03741 8181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce3370 f2004d914a3c093a x'_6: 0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0b7a4 49cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c3354 e41607e60750e057 x'_7: 0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7 f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3f8 4e19da00fbc6ae34 y'_0: 0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc435fa ab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c0ff3 23edd3fe4d2d7971 y'_1: 0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d72964732fcb f3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ffc7b1 11471db936cd5665 Sakemi, et al. Expires 30 October 2020 [Page 35] InternetDraft PairingFriendly Curves April 2020 y'_2: 0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d370514 475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b8fde 68332a526a2a8474 y'_3: 0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e122d2 742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e53373 16213da92841589d y'_4: 0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f112985 7ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf7a43 f47831f982e50137 y'_5: 0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055ab750 4fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226cf3a5 94eedc58cf90bee4 y'_6: 0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c819a6 df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9aa62b 3d41faeafeb23986 y'_7: 0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8eca9a 9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e84069c55 d667ffcb732718b6 e_0: 0x0e26c3fcb8ef67417814098de5111ffcccc1d003d15b367bad07cef2291a93d3 1db03e3f03376f3beae2bd877bcfc22a25dc51016eda1ab56ee3033bc4b4fec596 2f02dffb3af5e38e e_1: 0x069061b8047279aa5c2d25cdf676ddf34eddbc8ec2ec0f03614886fa828e1fc0 66b26d35744c0c38271843aa4fb617b57fa9eb4bd256d17367914159fc18b10a10 85cb626e5bedb145 e_2: 0x02b9bece645fbf9d8f97025a1545359f6fe3ffab3cd57094f862f7fb9ca01c88 705c26675bcc723878e943da6b56ce25d063381fcd2a292e0e7501fe572744184f b4ab4ca071a04281 Sakemi, et al. Expires 30 October 2020 [Page 36] InternetDraft PairingFriendly Curves April 2020 e_3: 0x0080d267bf036c1e61d7fc73905e8c630b97aa05ef3266c82e7a111072c0d205 6baa8137fba111c9650dfb18cb1f43363041e202e3192fced29d2b0501c882543f b370a56bfdc2435b e_4: 0x03c6b4c12f338f9401e6a493a405b33e64389338db8c5e592a8dd79eac7720dd 83dd6b0c189eeda20809160cd57cdf3e2edc82db15f553c1f6c953ea27114cb6bd 8a38e273f407dae0 e_5: 0x016e46224f28bfd8833f76ac29ee6e406a9da1bde55f5e82b3bd977897a9104f 18b9ee41ea9af7d4183d895102950a12ce9975669db07924e1b432d9680f5ce7e5 c67ed68f381eba45 e_6: 0x008ddce7a4a1b94be5df3ceea56bef0077dcdde86d579938a50933a47296d337 b7629934128e2457e24142b0eeaa978fd8e70986d7dd51fccbbeb8a1933434fec4 f5bc538de2646e90 e_7: 0x060ef6eae55728e40bd4628265218b24b38cdd434968c14bfefb87f0dcbfc76c c473ae2dc0cac6e69dfdf90951175178dc75b9cc08320fcde187aa58ea047a2ee0 0b1968650eec2791 e_8: 0x0c3943636876fd4f9393414099a746f84b2633dfb7c36ba6512a0b48e66dcb2e 409f1b9e150e36b0b4311165810a3c721525f0d43a021f090e6a27577b42c7a57b ed3327edb98ba8f8 e_9: 0x02d31eb8be0d923cac2a8eb6a07556c8951d849ec53c2848ee78c5eed40262eb 21822527a8555b071f1cd080e049e5e7ebfe2541d5b42c1e414341694d6f16d287 e4a8d28359c2d2f9 e_10: 0x07f19673c5580d6a10d09a032397c5d425c3a99ff1dd0abe5bec40a0d47a6b8d aabb22edb6b06dd8691950b8f23faefcdd80c45aa3817a840018965941f4247f9f 97233a84f58b262e e_11: 0x0d3fe01f0c114915c3bdf8089377780076c1685302279fd9ab12d07477aac03b 69291652e9f179baa0a99c38aa8851c1d25ffdb4ded2c8fe8b30338c14428607d6 d822610d41f51372 Sakemi, et al. Expires 30 October 2020 [Page 37] InternetDraft PairingFriendly Curves April 2020 e_12: 0x0662eefd5fab9509aed968866b68cff3bc5d48ecc8ac6867c212a2d82cee5a68 9a3c9c67f1d611adac7268dc8b06471c0598f7016ca3d1c01649dda4b43531cffc 4eb41e691e27f2eb e_13: 0x0aad8f4a8cfdca8de0985070304fe4f4d32f99b01d4ea50d9f7cd2abdc0aeea9 9311a36ec6ed18208642cef9e09b96795b27c42a5a744a7b01a617a91d9fb7623d 636640d61a6596ec e_14: 0x0ffcf21d641fd9c6a641a749d80cab1bcad4b34ee97567d905ed9d5cfb74e9ae f19674e2eb6ce3dfb706aa814d4a228db4fcd707e571259435393a27cac68b59a1 b690ae8cde7a94c3 e_15: 0x0cbe92a53151790cece4a86f91e9b31644a86fc4c954e5fa04e707beb69fc60a 858fed8ebd53e4cfd51546d5c0732331071c358d721ee601bfd3847e0e904101c6 2822dd2e4c7f8e5c e_16: 0x0202db83b1ff33016679b6cfc8931deea6df1485c894dcd113bacf564411519a 42026b5fda4e16262674dcb3f089cd7d552f8089a1fec93e3db6bca43788cdb06f c41baaa5c5098667 e_17: 0x070a617ed131b857f5b74b625c4ef70cc567f619defb5f2ab67534a1a8aa7297 5fc4248ac8551ce02b68801703971a2cf1cb934c9c354cadd5cfc4575cde8dbde6 122bd54826a9b3e9 e_18: 0x070e1ebce457c141417f88423127b7a7321424f64119d5089d883cb953283ee4 e1f2e01ffa7b903fe7a94af4bb1acb02ca6a36678e41506879069cee11c9dcf6a0 80b6a4a7c7f21dc9 e_19: 0x058a06be5a36c6148d8a1287ee7f0e725453fa1bb05cf77239f235b417127e37 0cfa4f88e61a23ea16df3c45d29c203d04d09782b39e9b4037c0c4ac8e8653e7c5 33ad752a640b233e e_20: 0x0dfdfaaeb9349cf18d21b92ad68f8a7ecc509c35fcd4b8abeb93be7a204ac871 f2195180206a2c340fccb69dbc30b9410ed0b122308a8fc75141f673ae5ec82b6a 45fc2d664409c6b6 Sakemi, et al. Expires 30 October 2020 [Page 38] InternetDraft PairingFriendly Curves April 2020 e_21: 0x0d06c8adfdd81275da2a0ce375b8df9199f3d359e8cf50064a3dc10a59241712 4a3b705b05a7ffe78e20f935a08868ecf3fc5aba0ace7ce4497bb59085ca277c16 b3d53dd7dae5c857 e_22: 0x0708effd28c4ae21b6969cb9bdd0c27f8a3e341798b6f6d4baf27be259b4a476 88b50cb68a69a917a4a1faf56cec93f69ac416512c32e9d5e69bd8836b6c2ba9c6 889d507ad571dbc4 e_23: 0x09da7c7aa48ce571f8ece74b98431b14ae6fb4a53ae979cd6b2e82320e8d25a0 ece1ca1563aa5aa6926e7d608358af8399534f6b00788e95e37ef1b549f43a58ad 250a71f0b2fdb2bf e_24: 0x0a7150a14471994833d89f41daeaa999dfc24a9968d4e33d88ed9e9f07aa2432 c53e486ba6e3b6e4f4b8d9c989010a375935c06e4b8d6c31239fad6a61e2647b84 a0e3f76e57005ff7 e_25: 0x084696f31ff27889d4dccdc4967964a5387a5ae071ad391c5723c9034f16c255 7915ada07ec68f18672b5b2107f785c15ddf9697046dc633b5a23cc0e442d28ef6 eea9915d0638d4d8 e_26: 0x0398e76e3d2202f999ac0f73e0099fe4e0fe2de9d223e78fc65c56e209cdf48f 0d1ad8f6093e924ce5f0c93437c11212b7841de26f9067065b1898f48006bcc6f2 ab8fa8e0b93f4ba4 e_27: 0x06d683f556022368e7a633dc6fe319fd1d4fc0e07acff7c4d4177e83a911e733 13e0ed980cd9197bd17ac45942a65d90e6cb9209ede7f36c10e009c9d337ee97c4 068db40e34d0e361 e_28: 0x0d764075344b70818f91b13ee445fd8c1587d1c0664002180bbac9a396ad4a8d c1e695b0c4267df4a09081c1e5c256c53fd49a73ffc817e65217a44fc0b20ef5ee 92b28d4bc3e38576 e_29: 0x0aa6a32fdc4423b1c6d43e5104159bcd8e03a676d055d4496f7b1bc8761164a2 908a3ff0e4c4d1f4362015c14824927011e2909531b8d87ee0acd676e7221a1ca1 c21a33e2cf87dc51 Sakemi, et al. Expires 30 October 2020 [Page 39] InternetDraft PairingFriendly Curves April 2020 e_30: 0x1147719959ac8eeab3fc913539784f1f947df47066b6c0c1beafecdb5fa784c3 be9de5ab282a678a2a0cbef8714141a6c8aaa76500819a896b46af20509953495e 2a85eff58348b38d e_31: 0x11a377bcebd3c12702bb34044f06f8870ca712fb5caa6d30c48ace96898fcbcd dbcf31f331c9e524684c02c90db7f30b9fc470d6e651a7e8b1f684383f3705d7a4 7a1b4fe463d623c8 e_32: 0x0b8b4511f451ba2cc58dc28e56d5e1d0a8f557ecb242f4d994a627e07cf3fa44 e6d83cb907deacf303d2f761810b5d943b46c4383e1435ec23fec196a70e339461 73c78be3c75dfc83 e_33: 0x090962d632ee2a57ce4208052ce47a9f76ea0fdad724b7256bb07f3944e9639a 981d3431087241e30ae9bf5e2ea32af323ce7ed195d383b749cb25bc09f678d385 a49a0c09f6d9efca e_34: 0x0931c7befc80acd185491c68af886fa8ee39c21ed3ebd743b9168ae3b298df48 5bfdc75b94f0b21aecd8dca941dfc6d1566cc70dc648e6ccc73e4cbf2a1ac83c82 94d447c66e74784d e_35: 0x020ac007bf6c76ec827d53647058aca48896916269c6a2016b8c06f0130901c8 975779f1672e581e2dfdbcf504e96ecf6801d0d39aad35cf79fbe7fe193c6c882c 15bce593223f0c7c e_36: 0x0c0aed0d890c3b0b673bf4981398dcbf0d15d36af6347a39599f3a2258418482 8f78f91bbbbd08124a97672963ec313ff142c456ec1a2fc3909fd4429fd699d827 d48777d3b0e0e699 e_37: 0x0ef7799241a1ba6baaa8740d5667a1ace50fb8e63accc3bc30dc07b11d78dc54 5b68910c027489a0d842d1ba3ac406197881361a18b9fe337ff22d730fa44afabb 9f801f759086c8e4 e_38: 0x016663c940d062f4057257c8f4fb9b35e82541717a34582dd7d55b41ebadf40d 486ed74570043b2a3c4de29859fdeae9b6b456cb33bb401ecf38f9685646692300 517e9b035d6665fc Sakemi, et al. Expires 30 October 2020 [Page 40] InternetDraft PairingFriendly Curves April 2020 e_39: 0x1184a79510edf25e3bd2dc793a5082fa0fed0d559fa14a5ce9ffca4c61f17196 e1ffbb84326272e0d079368e9a735be1d05ec80c20dc6198b50a22a765defdc151 d437335f1309aced e_40: 0x120e47a747d942a593d202707c936dafa6fed489967dd94e48f317fd3c881b10 41e3b6bbf9e8031d44e39c1ab5ae41e487eac9acd90e869129c38a8e6c97cf55d6 666d22299951f91a e_41: 0x026b6e374108ecb2fe8d557087f40ab7bac8c5af0644a655271765d57ad71742 aa331326d871610a8c4c30ccf5d8adbeec23cdff20d9502a5005fce2593caf0682 c82e4873b89d6d71 e_42: 0x041be63a2fa643e5a66faeb099a3440105c18dca58d51f74b3bf281da4e689b1 3f365273a2ed397e7b1c26bdd4daade710c30350318b0ae9a9b16882c29fe31ca3 b884c92916d6d07a e_43: 0x124018a12f0f0af881e6765e9e81071acc56ebcddadcd107750bd8697440cc16 f190a3595633bb8900e6829823866c5769f03a306f979a3e039e620d6d2f576793 d36d840b168eeedd e_44: 0x0d422de4a83449c535b4b9ece586754c941548f15d50ada6740865be9c0b0667 88b6078727c7dee299acc15cbdcc7d51cdc5b17757c07d9a9146b01d2fdc7b8c56 2002da0f9084bde5 e_45: 0x1119f6c5468bce2ec2b450858dc073fea4fb05b6e83dd20c55c9cf694cbcc57f c0effb1d33b9b5587852d0961c40ff114b7493361e4cfdff16e85fbce667869b6f 7e9eb804bcec46db e_46: 0x061eaa8e9b0085364a61ea4f69c3516b6bf9f79f8c79d053e646ea637215cf65 90203b275290872e3d7b258102dd0c0a4a310af3958165f2078ff9dc3ac9e995ce 5413268d80974784 e_47: 0x0add8d58e9ec0c9393eb8c4bc0b08174a6b421e15040ef558da58d241e5f906a d6ca2aa5de361421708a6b8ff6736efbac6b4688bf752259b4650595aa395c40d0 0f4417f180779985 Sakemi, et al. Expires 30 October 2020 [Page 41] InternetDraft PairingFriendly Curves April 2020 Appendix C. Parameters of the BarretoLynnScott Curve of Embedding Degree 12 In this part, we introduce parameters of the BarretoLynnScott curve of embedding degree 12 with 381bit p that is adopted by a lot of applications such as Zcash [Zcash], Ethereum [Ethereum], and so on. The BLS12_381 curve is shown in [BLS12381] and it is defined by the following parameter t = 2^63  2^62  2^60  2^57  2^48  2^16 where the size of p becomes 381bit length. For the finite field F_p, the towers of extension field F_p^2, F_p^6 and F_p^12 are defined by indeterminates u, v, and w as follows: F_p^2 = F_p[u] / (u^2 + 1) F_p^6 = F_p^2[v] / (v^3  u  1) F_p^12 = F_p^6[w] / (w^2  v). Defined by t, the elliptic curve E and its twisted curve E' are represented by E: y^2 = x^3 + 4 and E': y^2 = x^3 + 4(u + 1). A pairing e is defined by taking G_1 as a cyclic group of order r generated by a base point BP = (x, y) in F_p, G_2 as a cyclic group of order r generated by a base point BP' = (x', y') in F_p^2, and G_T as a subgroup of a multiplicative group (F_p^12)^* of order r. BLS12_381 is Mtype. We have to note that, according to [BD18], the bit length of p for BLS12 to achieve 128bit security is calculated as 461 bits and more, which BLS12_381 does not satisfy. Parameters of BLS12_381 are given as follows. * G_1 defined over E: y^2 = x^3 + b  p : a characteristic  r : an order  BP = (x, y) : a base point  h : a cofactor  b : a coefficient of E Sakemi, et al. Expires 30 October 2020 [Page 42] InternetDraft PairingFriendly Curves April 2020 * G_2 defined over E': y^2 = x^3 + b'  r' : an order  BP' = (x', y') : a base point (encoded with [ID.ietflwigcurverepresentations]) o x' = x'_0 + x'_1 * u (x'_0, x'_1 in F_p) o y' = y'_0 + y'_1 * u (y'_0, y'_1 in F_p)  h' : a cofactor  b' : a coefficient of E' p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f624 1eabfffeb153ffffb9feffffffffaaab r: 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 x: 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac58 6c55e83ff97a1aeffb3af00adb22c6bb y: 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3ed d03cc744a2888ae40caa232946c5e7e1 h: 0x396c8c005555e1568c00aaab0000aaab b: 4 r': 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f624 1eabfffeb153ffffb9feffffffffaaab x'_0: 0x024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3d177 0bac0326a805bbefd48056c8c121bdb8 x'_1: 0x13e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049 334cf11213945d57e5ac7d055d042b7e Sakemi, et al. Expires 30 October 2020 [Page 43] InternetDraft PairingFriendly Curves April 2020 y'_0: 0x0ce5d527727d6e118cc9cdc6da2e351aadfd9baa8cbdd3a76d429a695160d12c 923ac9cc3baca289e193548608b82801 y'_1: 0x0606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af267492ab572e99ab 3f370d275cec1da1aaa9075ff05f79be h': 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa 628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5 b': 4 * (u + 1) Authors' Addresses Yumi Sakemi (editor) Lepidum Email: yumi.sakemi@lepidum.co.jp Tetsutaro Kobayashi NTT Email: tetsutaro.kobayashi.dr@hco.ntt.co.jp Tsunekazu Saito NTT Email: tsunekazu.saito.hg@hco.ntt.co.jp Sakemi, et al. Expires 30 October 2020 [Page 44]