Internet-Draft | Pairing-Friendly Curves | June 2020 |
Sakemi, et al. | Expires 20 December 2020 | [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 20 December 2020.¶
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 [KB16]. 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. 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 level described in this memo corresponds 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 > 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:¶
E : y^2 = x^3 + A * x + B,¶
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.¶
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 (F_q^k)-rational points of E, denoted by E(F_q^k), to be the set of all solutions (x,y) in F_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(F_q^k) forms a group under a group law which can be defined geometrically as follows. For P and Q in E(F_q^k) define P + Q to be the reflection about the x-axis of the unique third point 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 [a]P for a positive integer a as the point P added to itself (a-1) times.¶
We define some of the terminology used in this memo as follows:¶
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 F_p. Let k be the minimum integer for which r is a divisor of p^k - 1; this is called the embedding degree. Let G_1 be a cyclic subgroup of E(F_p) of order r, there also exists a cyclic subgroup of E(F_p^k) of order r, define this to be G_2. 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 (F_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.¶
A BN curve [BN05] is one of the instantiations 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 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 a multiplicative group (F_p)^* of order (p - 1).¶
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 twist 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 D-type if b' = b / m, and M-type if b' = b * m. The embeddiing 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.¶
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.¶
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 F_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(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 r-torsion points. In the same way as BN curves, BLS curves can be categorized into 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, 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.¶
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.¶
Let F_p be a finite field of characteristic p and F_p^d = F_p(i) be an extension field of F_p of degree d.¶
For an element s in F_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 F_p, s is represented as octet string by oct(s) = s_0 || s_1 || ... || s_{d - 1}.¶
Let F_p^d' = F_p^d(j) be an extension field of F_p^d of degree d' / d.¶
For an element s' in F_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 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 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 paiting-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 level of pairing-friendly curves is estimated by the computational cost of the most efficient algorithm to solve 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]. Due to exTNFS, the security level 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 level described in this memo corresponds 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 into '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. Due to space limitations, Table 1 omits libraries that have not been maintained since the 2016 exTNFS attacks and curves that have had the security levels below 128 bits since before 2016 (ex. BN160). The full version of Table 1 is available at https://lepidum.co.jp/blog/2020-03-27/ietf-draft-pfc/. In this table, 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 level of these curves.¶
Category | Name | Curve Type | Security Levels (bit) | |||||
---|---|---|---|---|---|---|---|---|
~ | Arnd 128 | ~ | Arnd 192 | ~ | Arnd 256 | |||
Standard | ISO/IEC | BN256I | X | |||||
BN384 | X | |||||||
BN512I | X | |||||||
TCG | BN256I | X | ||||||
BN638 | X | |||||||
FIDO/W3C | BN256I | X | ||||||
BN256D | X | |||||||
BN512I | X | |||||||
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 | ||||||
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 Univ. | BLS48_581 | X | ||||||
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 | |||||||
BN254B | X | |||||||
BN254N | X | |||||||
BN254S1 | X | |||||||
BN254S2 | X | |||||||
BN462 | X | |||||||
Application | Zcash | BLS12_381 | X | |||||
BN_SNARK1 | X | |||||||
Ethereum | BLS12_381 | X | ||||||
Chia Network | BLS12_381 | X | ||||||
DFINITY | BLS12_381 | X | ||||||
BN254N | X | |||||||
BN_SNARK1 | 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.¶
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 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 twist E' are represented by E: y^2 = x^3 + 4 and E': y^2 = x^3 + 4(u + 1). BLS12_381 is categorized into 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(F_p)¶
G_2 is an r-order subgroup of E'(F_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].¶
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 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 - 2) F_p^12 = F_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 into 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 more efficient than BN462, 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(F_p)¶
G_2 is an r-order subgroup of E'(F_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 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 twist E' are represented by E: y^2 = x^3 + 1 and E': y^2 = x^3 - 1 / w. BLS48-581 is categorized into D-type.¶
We then give the parameters for BLS48-581 as follows.¶
G_1 is the largest prime-order subgroup of E(F_p)¶
G_2 is an r-order subgroup of E'(F_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 know, 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 Table 1, 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. Implementers MAY use pairing-friendly curves with 100-bit security only if they need to keep interoperability with the existing applications.¶
In addition, implementors should be aware of the following points when they implement pairing-based cryptographic applications using recommended curves.¶
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, calculate a scalar multiplication 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 when they implement a module of scalar multiplication[Montgomery] [RFC7748].¶
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]. 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.¶
This document has no actions for IANA.¶
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, Michael Scott, Chloe Martindale as an Expert Reviewer, Watson Ladd, Armand Faz, 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. 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 F_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 F_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.¶
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_F_p(y) := { 1 if y > (p - 1) / 2, else { 0 otherwise.¶
sign_F_p^2(y') := { sign_F_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'):¶