Internet-Draft | Pairing-Friendly Curves | September 2020 |
Sakemi, et al. | Expires 3 April 2021 | [Page] |
Pairing-based cryptography, a subfield of elliptic curve cryptography, has received attention due to its flexible and practical functionality. Pairings are special maps defined using elliptic curves and it can be applied to construct several cryptographic protocols such as identity-based encryption, attribute-based 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 pairing-friendly curves such as Barreto-Naehrig curves are affected by the attack. In particular, a Barreto-Naehrig curve with a 254-bit characteristic was adopted by a lot of cryptographic libraries as a parameter of 128-bit security, however, it ensures no more than the 100-bit security level due to the effect of the attack. In this memo, we list the security levels of certain pairing-friendly curves, and motivate our choices of curves. First, we summarize the adoption status of pairing-friendly curves in standards, libraries and applications, and classify them in the 128-bit, 192-bit, and 256-bit security levels. Then, from the viewpoints of "security" and "widely used", we select the recommended pairing-friendly curves considering exTNFS.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts 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 Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 3 April 2021.¶
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/license-info) 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.¶
Elliptic curve cryptography is an important area in currently deployed cryptography. The cryptographic algorithms based on elliptic curve cryptography, such as the Elliptic Curve Digital Signature Algorithm (ECDSA), are widely used in many applications.¶
Pairing-based cryptography, a subfield of elliptic curve cryptography, has attracted much attention due to its flexible and practical functionality. Pairings are special maps defined using elliptic curves. Pairings are fundamental in the construction of several cryptographic algorithms and protocols such as identity-based encryption (IBE), attribute-based encryption (ABE), authenticated key exchange (AKE), short signatures, and so on. Several applications of pairing-based cryptography are currently in practical use.¶
As the importance of pairings grows, elliptic curves where pairings are efficiently computable are studied and the special curves called pairing-friendly curves are proposed.¶
Several applications using pairing-based cryptography have already been standardized and deployed. We list here some examples of applications available in the real world.¶
IETF published RFCs for pairing-based cryptography such as Identity-Based Cryptography [RFC5091], Sakai-Kasahara Key Encryption (SAKKE) [RFC6508], and Identity-Based Authenticated Key Exchange (IBAKE) [RFC6539]. SAKKE is applied to Multimedia Internet KEYing (MIKEY) [RFC6509] and used in 3GPP [SAKKE].¶
Pairing-based key agreement protocols are standardized in ISO/IEC [ISOIEC11770-3]. In [ISOIEC11770-3], a key agreement scheme by Joux [Joux00], identity-based key agreement schemes by Smart-Chen-Cheng [CCS07] and Fujioka-Suzuki-Ustaoglu [FSU10] are specified.¶
MIRACL implements M-Pin, a multi-factor authentication protocol [M-Pin]. The M-Pin protocol includes a type of zero-knowledge proof, where pairings are used for its construction.¶
The Trusted Computing Group (TCG) specified the Elliptic Curve Direct Anonymous Attestation (ECDAA) in the specification of a 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. Pairings are used in the construction of 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 part of the functionality of Intel Software Guard Extensions (SGX) [EPID]. They extended TPM ECDAA to realize such functionality. A pairing-based EPID was proposed [BL10] and distributed along with Intel SGX applications.¶
Zcash implemented their own zero-knowledge proof algorithm named Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARKs) [Zcash]. zk-SNARKs are used for protecting the privacy of transactions of Zcash. They use pairings to construct zk-SNARKs.¶
Cloudflare introduced Geo Key Manager [Cloudflare] to restrict distribution of customers' private keys to a subset of their data centers. To achieve this functionality, ABE is used, and pairings take 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 include securely implemented subroutines for pairing computations on certain secure pairing-friendly curves in CIRCL.¶
Currently, Boneh-Lynn-Shacham (BLS) signature schemes are being standardized [I-D.boneh-bls-signature] 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.¶
At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field sieve (NFS) algorithm for the discrete logarithm problem in a finite field GF(p^k) [KB16]. The attack improves the polynomial selection that is the first step in the number field sieve algorithm for discrete logarithms in GF(p^k). The idea is applicable when the embedding degree k is a composite that satisfies k = i*j (gcd (i, j) = 1, i, j> 1). The basic idea is based on the equality GF(p^k) = (GF(p^i)^j) and one of the improvement for reducing the amount of cost for solving the discrete logarithm problem is using sub-field calculation. Several types of pairing-friendly curves such as Barreto-Naehrig curves (BN curves)[BN05] and Barreto-Lynn-Scott curves (BLS curves)[BLS02] are affected by the attack, since a pairing-friendly curve suitable for cryptographic applications requires that the discrete logarithm problem is sufficiently difficult. Please refer to [KB16] for detailed ideas and calculation algorithms of the attack by Kim. In particular, BN254, which is a BN curve with a 254-bit characteristic effective for pairing calculations, was adopted by a lot of cryptographic libraries as a parameter of the 128-bit security level, however, BN254 ensures no more than the 100-bit security level due to the effect of the attack, where the security levels described in this memo correspond to the security strength of NIST recommendation [NIST].¶
To resolve this effect immediately, several research groups and implementers re-evaluated the security of pairing-friendly curves and they respectively proposed various curves that are secure against the attack [BD18] [BLS12-381].¶
In this memo, we list the security levels of certain pairing-friendly curves, and motivate our choices of curves. First, we summarize the adoption status of pairing-friendly curves in international standards, libraries and applications, and classify them in the 128-bit, 192-bit, and 256-bit security levels. Then, from the viewpoints of "security" and "widely used", pairing-friendly curves corresponding to each security level are selected in accordance with the security evaluation by Barbulescu and Duquesne [BD18].¶
As a result, we recommend the BLS curve with 381-bit characteristic of embedding degree 12 and the BN curve with the 462-bit characteristic for the 128-bit security level, and the BLS curves of embedding degree 48 with the 581-bit characteristic for the 256-bit security level. This memo shows their specific test vectors.¶
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.¶
Let p be a prime number and q = p^n for a natural number n > 0, where p at least 5. Let GF(q) be a finite field. The curve defined by the following equation E is called an elliptic curve:¶
E : y^2 = x^3 + a * x + b,¶
and a and b in GF(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.¶
A solution (x,y) to the equation E can be thought of as a point on the corresponding curve. For a natural number k, we define the set of (GF(q^k))-rational points of E, denoted by E(GF(q^k)), to be the set of all solutions (x,y) in GF(q^k), together with a 'point at infinity' O_E, which is defined to lie on every vertical line passing through the curve E.¶
The set E(GF(q^k)) forms a group under a group law that can be defined geometrically as follows. For P and Q in E(GF(q^k)) define P + Q to be the reflection around the x-axis of the unique third point R of intersection of the straight line passing through P and Q with the curve E. If the straight line is tangent to E, we say that it passes through that point twice. The identity of this group is the point at infinity O_E. We also define scalar multiplication [K]P for a positive integer K as the point P added to itself (K-1) times. Here, [0]P becomes the point at infinity O_E and the relation [-K]P = -([K]P) is satisfied.¶
A pairing is a bilinear map defined on two subgroups of rational points of an elliptic curve. Examples include the Weil pairing, the Tate pairing, the optimal Ate pairing [Ver09], and so on. The optimal Ate pairing is considered to be the most efficient to compute and is the one that is most commonly used for practical implementation.¶
Let E be an elliptic curve defined over a prime field GF(p). Let k be the minimum integer for which r is a divisor of p^k - 1; this is called the embedding degree of E over GF(p). Let G_1 be a cyclic subgroup of E(GF(p)) of order r, there also exists a cyclic subgroup of E(GF(p^k)) of order r, define this to be G_2. Let d be a divisor of k and E' be an elliptic curve defined over GF(p^(k/d)). If an isomorphism from E' to E(GF(p^k)) exists, then E' is called the twist of E. It can sometimes be convenient for efficiency to do the computations of G_2 in the twist E', and so consider G_2 to instead be a subgroup of E'. Let G_T be an order r subgroup of the multiplicative group (GF(p^k))^*; this exists by definition of k.¶
A pairing is defined as a bilinear map e: (G_1, G_2) -> G_T satisfying the following properties:¶
In applications, it is also necessary that for any S in G_1 and T in G_2, this bilinear map is efficiently computable.¶
We define some of the terminology used in this memo as follows:¶
A BN curve [BN05] is a family of pairing-friendly 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 well-chosen integer t. E is defined over GF(p), where p is a prime number and at least 5, and E(GF(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 a primitive element of the multiplicative group (GF(p))^* of order (p - 1).¶
In the case of BN curves, we can use twists of the degree 6. If m is an element that is neither a square nor a cube in an extension field GF(p^2), the twist E' of E is defined over an extension field GF(p^2) by the equation E': y^2 = x^3 + b' with b' = b / m or b' = b * m. BN curves are called D-type if b' = b / m, and M-type if b' = b * m. The embedding degree k is 12.¶
A pairing e is defined by taking G_1 as a subgroup of E(GF(p)) of order r, G_2 as a subgroup of E'(GF(p^2)), and G_T as a subgroup of a multiplicative group (GF(p^12))^* of order r.¶
A BLS curve [BLS02] is a another family of pairing-frinedly curves proposed in 2002. Similar to BN curves, a pairing over BLS curves constructs optimal Ate pairings.¶
A BLS curve is defined by elliptic curves E and E' parameterized by a well-chosen integer t. E is defined over a finite field GF(p) by an equation of the form E: y^2 = x^3 + b, and its twist E': y^2 = x^3 + b', is defined in the same way as BN curves. In contrast to BN curves, E(GF(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 r-torsion points. In the same way as BN curves, BLS curves can be categorized as D-type and M-type.¶
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, parameters 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 where t must be 1 (mod 3).¶
A pairing e is defined by taking G_1 as a subgroup of E(GF(p)) of order r, G_2 as an order r subgroup of E'(GF(p^2)) for BLS12 and of E'(GF(p^8)) for BLS48, and G_T as an order r subgroup of a multiplicative group (GF(p^12))^* for BLS12 and of a multiplicative group (GF(p^48))^* for BLS48.¶
Pairing-friendly 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 [I-D.ietf-lwig-curve-representations] as a standard and effective method. Note that the big-endian encoding is used for an element in GF(p) which follows to mcl [mcl], ISO/IEC 15946-5 [ISOIEC15946-5] and etc.¶
Let GF(p) be a finite field of characteristic p and GF(p^d) = GF(p)(i) be an extension field of GF(p) of degree d.¶
For an element s in GF(p^d) such that s = s_0 + s_1 * i + ... + s_{d - 1} * i^{d - 1} where s_0, s_1, ... , s_{d - 1} in the basefield GF(p), s is represented as octet string by oct(s) = s_0 || s_1 || ... || s_{d - 1}.¶
Let GF(p^d') = GF(p^d)(j) be an extension field of GF(p^d) of degree d' / d.¶
For an element s' in GF(p^d') such that s' = s'_0 + s'_1 * j + ... + s'_{d' / d - 1} * j^{d' / d - 1} where s'_0, s'_1, ..., s'_{d' / d - 1} in the basefield GF(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 an 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.¶
The security of pairing-friendly curves is evaluated by the hardness of the following discrete logarithm problems:¶
There are other hard problems over pairing-friendly curves used for proving the security of pairing-based cryptography. Such problems include the computational bilinear Diffie-Hellman (CBDH) problem, the bilinear Diffie-Hellman (BDH) problem, the decision bilinear Diffie-Hellman (DBDH) problem, the 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.¶
Although it would be sufficient to attack any of these problems to attack pairing-based crytography, the only known attacks thus far attack the discrete logarithm problem directly, so we focus on the discrete logarithm in this memo.¶
The security levels of pairing-friendly curves are estimated by the computational cost of the most efficient algorithm for solving the above discrete logarithm problems. The best-known algorithms for solving the discrete logarithm problems are based on Pollard's rho algorithm [Pollard78] and Index Calculus [HR83]. To make index calculus algorithms more efficient, number field sieve (NFS) algorithms are utilized.¶
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]. The exTNFS improves the polynomial selection that is the first step in the number field sieve algorithm for discrete logarithms in GF(p^k). The idea is applicable when the embedding degree k is a composite that satisfies k = i * j (gcd (i, j) = 1, i, j> 1). Since the above condition is satisfied especially when k = 2^n*3^m (n, m> 1), BN curves and BLS curves whose embedding degree is divisible by 6 are affected by the exTNFS. The basic idea of the exTNFS is based on the equality GF(p^k) = (GF(p^i)^j) and one of the improvement for reducing the amount of cost for solving FFDLP is using sub-field calculation. Please refer to [KB16] for detailed ideas and calculation algorithms of exTNFS. Due to exTNFS, the security levels of certain pairing-friendly curves asymptotically dropped down. For instance, Barbulescu and Duquesne estimated that the security of the BN curves, which had been believed to provide 128-bit security (BN256, for example) was reduced to approximately 100 bits [BD18]. Here, the security levels described in this memo correspond to the security strength of NIST recommendation [NIST].¶
There has since been research into the minimum bit length of the parameters of pairing-friendly curves for each security level when applying exTNFS as an attacking method for FFDLP. For 128-bit security, Barbulescu and Duquesne estimated the minimum bit length of p of BN curves and BLS12 curves after exTNFS as 461 bits [BD18]. For 256-bit 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].¶
In this section, we introduce some of the known secure pairing-friendly curves that consider the impact of exTNFS.¶
First, we show the adoption status of pairing-friendly curves in standards, libraries and applications, and classify them in accordance with the 128-bit, 192-bit, and 256-bit security levels. Then, from the viewpoints of "security" and "widely used", pairing-friendly 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 peer-reviewed papers for security and that they are widely used in cryptographic libraries. In addition, "efficiency" is one of the important aspects but greatly dependant on implementations, so we choose to prioritize "security" and "widely used" over "efficiency" in consideration of future interconnections and interoperability over the internet.¶
We show the pairing-friendly curves that have been selected by existing standards, cryptographic libraries, and applications.¶
Table 1 summarizes the adoption status of pairing-friendly curves. In this table, "Arnd" is an abbreviation for "Around". The curves categorized as 'Arnd 128-bit', 'Arnd 192-bit' and 'Arnd 256-bit' for each label show that their security levels are within the range of plus/minus 5 bits for each security level. Other labels shown with '~' mean that the security level of the categorized curve is outside the range of each security level. Specifically, the security level of the categorized curves is more than the previous column and is less than the next column. The details are described as the following subsections. A BN curve with a XXX-bit characteristic p is denoted as BNXXX and a BLS curve of embedding degree k with a XXX-bit p is denoted as BLSk_XXX.¶
Table 1 omits parameters with security levels below the "Arnd 128-bit" range due to space limitations and viewpoints of secure usage of parameters. On the other hand, indicating which standards, libraries, and applications use these lower security level parameters would be useful information for implementers, therefore Appendix D shows these parameters. In addition, the full version of Table 1 is available at https://lepidum.co.jp/blog/2020-03-27/ietf-draft-pfc/.¶
In Table 1, the security level for each curve is evaluated in accordance with [BD18],[GMT19], [MAF19] and [FK18]. Note that the Freeman curves and MNT curves are not included in this table because [BD18] does not show the security levels of these curves.¶
Category | Name | Curve Type | Security Levels (bit) | ||||
---|---|---|---|---|---|---|---|
Arnd 128 | ~ | Arnd 192 | ~ | Arnd 256 | |||
Standard | ISO/IEC | BN384 | X | ||||
BN512I | X | ||||||
TCG | BN638 | X | |||||
FIDO/W3C | BN512I | X | |||||
BN638 | X | ||||||
Library | mcl | BLS12_381 | X | ||||
BN382M | X | ||||||
BN462 | X | ||||||
RELIC | BLS12_381 | X | |||||
BLS12_446 | X | ||||||
BLS12_455 | X | ||||||
BLS12_638 | X | ||||||
BLS24_477 | X | ||||||
BLS48_575 | X | ||||||
BN382R | X | ||||||
BN446 | X | ||||||
BN638 | X | ||||||
CP8_544 | X | ||||||
K54_569 | X | ||||||
KSS18_508 | X | ||||||
OT8_511 | X | ||||||
AMCL | BLS12_381 | X | |||||
BLS12_383 | X | ||||||
BLS12_461 | X | ||||||
BLS24_479 | X | ||||||
BLS48_556 | X | ||||||
BN512I | X | ||||||
Kyushu Univ. | BLS48_581 | X | |||||
MIRACL | BLS12_381 | X | |||||
BLS12_383 | X | ||||||
BLS12_461 | X | ||||||
BLS24_479 | X | ||||||
BLS48_556 | X | ||||||
BLS48_581 | X | ||||||
BN462 | X | ||||||
BN512I | X | ||||||
Adjoint | BLS12_381 | X | |||||
BN462 | X | ||||||
bls12377js | BLS12_377 | X | |||||
Application | Zcash | BLS12_381 | X | ||||
Ethereum | BLS12_381 | X | |||||
Chia Network | BLS12_381 | X | |||||
DFINITY | BLS12_381 | X | |||||
BN382M | X | ||||||
BN462 | X | ||||||
Algorand | BLS12_381 | X |
ISO/IEC 15946 series specifies public-key cryptographic techniques based on elliptic curves. ISO/IEC 15946-5 [ISOIEC15946-5] shows numerical examples of MNT curves[MNT01] with 160-bit p and 256-bit p, Freeman curves [Freeman06] with 224-bit p and 256-bit p, and BN curves with 160-bit p, 192-bit p, 224-bit p, 256-bit p, 384-bit p, and 512-bit 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 15946-5 is currently under development. As described below, BN curves with 256-bit p and 512-bit p specified in ISO/IEC 15946-5 used by other standards and libraries, these curves are especially denoted as BN256I and BN512I. The suffix 'I' of BN256I and BN512I are given from the initials of the standard name ISO.¶
TCG adopts the BN256I and a BN curve with 638-bit p specified by their own[TPM]. FIDO Alliance [FIDO] and W3C [W3C] adopt BN256I, BN512I, the BN638 by TCG, and the BN curve with 256-bit p proposed by Devegili et al.[DSD07] (named BN256D). The suffix 'D' of BN256D is given from the initials of the first author's name of the paper which proposed the parameter.¶
There are a lot of cryptographic libraries that support pairing calculations.¶
PBC is a library for pairing-based 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 pairing-based cryptography that supports four BN curves and BLS12_381 [GMT19]. These BN curves include BN254 proposed by Nogami et al. [NASKM08] (named BN254N), BN_SNARK1 suitable for SNARK applications[libsnark], BN382M, and BN462. The suffix 'N' of BN256N and the suffix 'M' of BN382M are respectively given from the initials of the first author's name of the proposed paper and the library's name mcl. 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). The suffix 'B' of BN254B is given from the initials of the first author's name of the proposed paper. Intel published a cryptographic library named Intel Integrated Performance Primitives (Intel-IPP) [Intel-IPP] and the library supports BN256I.¶
RELIC [RELIC] uses various types of pairing-friendly curves including 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. The suffix 'R' of BN382R is given from the initials of the library's name RELIC. In addition, RELIC supports six BLS curves (BLS12_381, BLS12_446, BLS12_445, BLS12_638, BLS24_477, and BLS48_575 [MAF19]), Cocks-Pinch curves of embedding degree 8 with 544-bit p[GMT19], pairing-friendly curves constructed by Scott et al. [SG19] based on Kachisa-Scott-Schaefer curves with embedding degree 54 with 569-bit p (named K54_569)[MAF19], a KSS curve [KSS08] of embedding degree 18 with 508-bit p (named KSS18_508) [AFKMR12], Optimal TNFS-secure curve [FM19] of embedding degree 8 with 511-bit p(OT8_511), and a supersingular curve [S86] with 1536-bit 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.¶
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]. The suffix 'S' of BN254S1 and BN254S2 are given from the initials of developper's name because he proposed these parameters.¶
The Celo foundation published the bls12377js library [bls12377js]. The supported curve is the BLS12_377 curve which is shown in [BCGMMW20].¶
Zcash uses a BN curve (named BN128) in their library libsnark [libsnark]. In response to the exTNFS attacks, they proposed new parameters using BLS12_381 [BLS12-381] [GMT19]and published its experimental implementation [zkcrypto].¶
Ethereum 2.0 adopted BLS12_381 and uses the implementation by Meyer [pureGo-bls]. Chia Network published their implementation [Chia] by integrating the RELIC toolkit [RELIC]. DFINITY uses mcl, and Algorand published an implementation which supports BLS12_381.¶
Table 1 shows a lot of cases of adopting BN and BLS curves. Among them, BLS12_381 and BN462 match our selection policy. Especially, the one that best matches the policy is BLS12_381 from the viewpoint of "widely used" and "efficiency", so we introduce the parameters of BLS12_381 in this memo.¶
On the other hand, from the viewpoint of the future use, the parameter of BN462 is also introduced. As shown in recent security evaluations for BLS12_381[BD18] [GMT19], its security level close to 128-bit but it is less than 128-bit. If the attack is improved even a little, BLS12_381 will not be suitable for the curve of the 128-bit security level. As curves of 128-bit security level are currently the most widely used, we recommend both BLS12-381 and BN462 in this memo in order to have a more efficient and a more prudent option respectively.¶
In this part, we introduce the parameters of the Barreto-Lynn-Scott curve of embedding degree 12 with 381-bit 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 [BLS12-381] and it is defined by the parameter¶
t = -2^63 - 2^62 - 2^60 - 2^57 - 2^48 - 2^16¶
where the size of p becomes 381-bit length.¶
For the finite field GF(p), the towers of extension field GF(p^2), GF(p^6) and GF(p^12) are defined by indeterminates u, v, and w as follows:¶
GF(p^2) = GF(p)[u] / (u^2 + 1) GF(p^6) = GF(p^2)[v] / (v^3 - u - 1) GF(p^12) = GF(p^6)[w] / (w^2 - v).¶
Defined by t, the elliptic curve E and its twist E' are represented by E: y^2 = x^3 + 4 and E': y^2 = x^3 + 4(u + 1). BLS12_381 is categorized as M-type.¶
We have to note that the security level of this pairing is expected to be 126 rather than 128 bits [GMT19].¶
Parameters of BLS12_381 are given as follows.¶
G_1 is the largest prime-order subgroup of E(GF(p))¶
G_2 is an r-order subgroup of E'(GF(p^2))¶
BP' = (x',y') : a 'base point', i.e., a generator of G_2 (encoded with [I-D.ietf-lwig-curve-representations])¶
As mentioned above, BLS12_381 is adopted in a lot of applications. Since it is expected that BLS12_381 will continue to be widely used more and more in the future, Appendix C shows the serialization format of points on an elliptic curve as useful information. This serialization format is also adopted in [I-D.boneh-bls-signature] [zkcrypto].¶
In addition, many pairing-based cryptographic applications use a hashing to an elliptic curve procedure that outputs a rational point on an elliptic curve from an arbitrary input. A standard specification of ciphersuites for a hashing to an elliptic curve, including BLS12-381, is under discussion in the IETF [I-D.irtf-cfrg-hash-to-curve] and it will be valuable information for implementers.¶
A BN curve with the 128-bit security level is shown in [BD18], which we call BN462. BN462 is defined by the parameter¶
t = 2^114 + 2^101 - 2^14 - 1¶
for the definition in Section 2.3.¶
For the finite field GF(p), the towers of extension field GF(p^2), GF(p^6) and GF(p^12) are defined by indeterminates u, v, and w as follows:¶
GF(p^2) = GF(p)[u] / (u^2 + 1) GF(p^6) = GF(p^2)[v] / (v^3 - u - 2) GF(p^12) = GF(p^6)[w] / (w^2 - v).¶
Defined by t, the elliptic curve E and its twist E' are represented by E: y^2 = x^3 + 5 and E': y^2 = x^3 - u + 2, respectively. The size of p becomes 462-bit length. BN462 is categorized as D-type.¶
We have to note that BN462 is significantly slower than BLS12_381, but has 134-bit security level [GMT19], so may be more resistant to future small improvements to the exTNFS attack.¶
We note also that CP8_544 is about 20% faster that BN462 [GMT19], has 131-bit security level, and that due to its construction will not be affected by future small improvements to the exTNFS attack. However, as this curve is not widely used (it is only implemented in one library), we instead chose BN462 for our 'safe' option.¶
We give the following parameters for BN462.¶
G_1 is the largest prime-order subgroup of E(GF(p))¶
G_2 is an r-order subgroup of E'(GF(p^2))¶
BP' = (x',y') : a 'base point', i.e., a generator of G_2 (encoded with [I-D.ietf-lwig-curve-representations])¶
As shown in Table 1, there are only two candidates of pairing-friendly curves for the 192-bit security level, BLS24_477 and BLS24_479. BLS24_477 has only one implementation and BLS24_479 is an experimental parameter that is not shown in any peer-reviewed paper. Therefore, because neither match our selection policy, we do not show the parameters for 192-bit security here.¶
As shown in Table 1, there are three candidates of pairing-friendly curves for 256-bit security. According to our selection policy, we select BLS48_581, as it is the most widely adopted by cryptographic libraries.¶
The selected BLS48 curve is shown in [KIK17] and it is defined by the parameter¶
t = -1 + 2^7 - 2^10 - 2^30 - 2^32.¶
In this case, the size of p becomes 581-bit.¶
For the finite field GF(p), the towers of extension field GF(p^2), GF(p^4), GF(p^8), GF(p^24) and GF(p^48) are defined by indeterminates u, v, w, z, and s as follows:¶
GF(p^2) = GF(p)[u] / (u^2 + 1) GF(p^4) = GF(p^2)[v] / (v^2 + u + 1) GF(p^8) = GF(p^4)[w] / (w^2 + v) GF(p^24) = GF(p^8)[z] / (z^3 + w) GF(p^48)= GF(p^24)[s] / (s^2 + z).¶
The elliptic curve E and its twist E' are represented by E: y^2 = x^3 + 1 and E': y^2 = x^3 - 1 / w. BLS48-581 is categorized as D-type.¶
We then give the parameters for BLS48-581 as follows.¶
G_1 is the largest prime-order subgroup of E(GF(p))¶
G_2 is an r-order subgroup of E'(GF(p^8))¶
BP' = (x',y') : a 'base point', i.e., a generator of G_2 (encoded with [I-D.ietf-lwig-curve-representations])¶
The recommended pairing-friendly 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 pairing-based cryptography applications SHOULD use the recommended parameters. As of 2020, as far as we've investigated the top cryptographic conferences in the past, there are no fatal attacks that significantly reduce the security of pairing-friendly curves after exTNFS.¶
BLS curves of embedding degree 12 typically require a characteristic p of 461 bits or larger to achieve the 128-bit security level [BD18]. Note that the security level of BLS12-381, which is adopted by a lot of libraries and applications, is slightly below 128 bits because a 381-bit characteristic is used [BD18] [GMT19].¶
BN254 is used in most of the existing implementations as shown in Section 4.1 ( and Appendix D), however, BN curves that were estimated as the 128-bit security level before exTNFS including BN254 ensure no more than the 100-bit security level by the effect of exTNFS.¶
In addition, implementors should be aware of the following points when they implement pairing-based cryptographic applications using recommended curves. Regarding the use case and applications of pairing-based cryptographic applications, please refer Section 1.2.¶
In applications such as key agreement protocols, users exchange the elements in G_1 and G_2 as public keys. To check these elements are so-called sub-group secure [BCM15], implementors should validate if the elements have the correct order r. Specifically, for public keys P in G_1 and Q in G_2, a receiver should calculate scalar multiplications [r]P and [r]Q, and check the results become points at infinity.¶
The pairing-based protocols, such as the BLS signatures, use a scalar multiplication in G_1, G_2 and an exponentiation in G_3 with the secret key. In order to prevent the leakage of secret key due to side channel attacks, implementors should apply countermeasure techniques such as montgomery ladder [Montgomery] [CF06] when they implement modules of a scalar multiplication and an exponentiation. Please refer [Montgomery] and [CF06] for the detailed algorithms of montgomery ladder.¶
When converting between an element in extension field and an octet string, implementors should check that the coefficient is within an appropriate range [IEEE1363]. If the coefficient is out of range, there is a possible that security vulnerabilities such as the signature forgery may occur.¶
Recommended parameters are affected by the Cheon's attack which is a solving algorithm for the strong DH problem [Cheon06]. The mathematical problem that provides the security of the strong DH problem is called ECDLP with Auxiliary Inputs (ECDLPwAI). In ECDLPwAI, given rational points P, [K]P, [K^i]P, for i=1,...,n, then we find a secret K. Since the complexity of ECDLPwAI is given as O(sqrt((r-1)/n + sqrt(n)) where n|r-1 by using Cheon's algorithm whereas the complexity of ECDLP is given as O(sqrt(r)), the complexity of ECDLPwAI with the ideal value n becomes dramatically smaller than that of ECDLP. Please refer [Cheon06] for the details of Cheon's algorithm. Therefore, implementers should be careful when they design cryptographic protocols based on the strong DH problem. For example, in the case of Short Signatures, they can prevent the Cheon's attack by carefully setting the maximum number of queries which corresponds to the parameter n.¶
This document has no actions for IANA.¶
The authors would like to appreciate a lot of authors including Akihiro Kato for their significant contribution to early versions of this memo. The authors would also like to acknowledge Kim Taechan, Hoeteck Wee, Sergey Gorbunov, Michael Scott, Chloe Martindale as an Expert Reviewer, Watson Ladd, Armando Faz, Rene Struik, and Satoru Kanno for their valuable comments.¶
Before presenting the computation of the optimal Ate pairing e(P, Q) satisfying the properties shown in Section 2.2, we give the 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.¶
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 twist curve E' so that one can reduce the computational cost of operations in G_2 [CLN09][KIK17]. We note that Line_function does not consider such an isomorphism.¶
The computation of the optimal Ate pairing for BN curves uses the Frobenius map. The p-power Frobenius map pi for a point Q = (x, y) over E' is pi(p, Q) = (x^p, y^p).¶
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 the optimal Ate pairing on 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 the order r of G_1 as input, and outputs e(P, Q).¶
f := 1; T := Q; if (c_L = -1) T := -T; end if for i = L-1 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;¶
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-Lynn-Scott 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 = L-1 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;¶
We provide test vectors for Optimal Ate Pairing e(P, Q) given in Appendix A for the curves BLS12-381, BN462 and BLS48-581 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 BLS12-381 and BN462, Q = (x', y') is given by¶
x' = x'_0 + x'_1 * u and y' = y'_0 + y'_1 * u,¶
where u is a indeterminate and x'_0, x'_1, y'_0, y'_1 are elements of GF(p).¶
For BLS48-581, 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 GF(p). The representation of Q = (x', y') given below is followed by [I-D.ietf-lwig-curve-representations].¶
BLS12-381:¶
BN462:¶
BLS48-581:¶
This section describes the serialization format defined by [ZCashRep]. This format applies to points on the BLS12-381 elliptic curves E and E', whose parameters are given in Section 4.2.1. Note that this serialization method is based on the representation shown in [SEC1] and it is a tiny tweak so as to apply to GF(p^m). It is not officially standardized by the standards organization, however we show it in this appendix as a useful reference for implementers.¶
At a high level, the serialization format is defined as follows:¶
Below, we give detailed serialization and de-serialization procedures. The following notation is used in the rest of this section:¶
sign_GF_p(y) := { 1 if y > (p - 1) / 2, else { 0 otherwise.¶
sign_GF_p^2(y') := { sign_GF_p(y'_0) if y'_1 equals 0, else { 1 if y'_1 > (p - 1) / 2, else { 0 otherwise.¶
The serialization procedure is defined as follows for a point P = (x, y). This procedure uses the I2OSP function defined in [RFC8017].¶
Compute the metadata bits C_bit, I_bit, and S_bit, as follows:¶
Let m_byte = (C_bit * 2^7) + (I_bit * 2^6) + (S_bit * 2^5).¶
Let x_string be the serialization of x, which is defined as follows:¶
Notice that in all of the above cases, the 3 most significant bits of x_string[0] are guaranteed to be 0.¶
If point compression is used, let y_string be the empty string. Otherwise (i.e., when point compression is not used), let y_string be the serialization of y, which is defined in Step 3.¶
Let s_string = x_string || y_string.¶
Set s_string[0] = x_string[0] OR m_byte, where OR is computed bitwise. After this operation, the most significant bit of s_string[0] equals C_bit, the next bit equals I_bit, and the next equals S_bit. (This is true because the three most significant bits of x_string[0] are guaranteed to be zero, as discussed above.)¶
Output s_string.¶
The deserialization procedure is defined as follows for a string s_string. This procedure uses the OS2IP function defined in [RFC8017].¶
Let m_byte = s_string[0] AND 0xE0, where AND is computed bitwise. In other words, the three most significant bits of m_byte equal the three most significant bits of s_string[0], and the remaining bits are 0.¶
If m_byte equals any of 0x20, 0x60, or 0xE0, output INVALID and stop decoding.¶
Otherwise:¶
If C_bit is 1:¶
If C_bit is 0:¶
If I_bit is 1:¶
Otherwise, I_bit must be 0. Continue decoding.¶
If C_bit is 0:¶
Otherwise, C_bit must be 1. Continue decoding.¶
If the curve that was determined in step 2 is E:¶
Otherwise, (i.e., when the curve that was determined in step 2 is E'):¶
BN curves including BN254 that were estimated as the 128-bit security level before exTNFS ensure no more than the 100-bit security level by the effect of exTNFS. Table 2 summarizes the adoption status of the parameters with a security level lower than the "Arnd 128-bit" range. Please refer the Section 4 for the naming conventions for each curve listed in Table 2.¶
Category | Name | Supported 100-bit Curves |
---|---|---|
Standard | ISO/IEC | BN256I |
TCG | BN256I | |
FIDO/W3C | BN256I | |
BN256D | ||
Library | mcl | BN254N |
BN_SNARK1 | ||
TEPLA | BN254B | |
BN254N | ||
RELIC | BN254N | |
BN256D | ||
AMCL | BN254N | |
BN254CX | ||
BN256I | ||
Intel IPP | BN256I | |
MIRACL | BN254N | |
BN254CX | ||
BN256I | ||
Adjoint | BN_SNARK1 | |
BN254B | ||
BN254N | ||
BN254S1 | ||
BN254S2 | ||
Application | Zcash | BN_SNARK1 |
DFINITY | BN254N | |
BN_SNARK1 |