Pairing-Friendly Curves

1.1. Pairing-based Cryptography

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.¶

1.2. Applications of Pairing-based Cryptography

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.irtf-cfrg-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.¶

1.3. Motivation and Contribution

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 with gcd(i, j) = 1 and i, j > 1. The basic idea is based on the equality GF(p^k) = GF((p^i)^j) and one of the improvements for reducing the amount of cost for solving the discrete logarithm problem is using subfield 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. 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 consider them at 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.¶

This memo also specifies how the points and scalars that protocols exchange are serialized and deserialized. That format does not originate here: it comes from [ZcashRep] and is already relied upon by other specifications, which cite this document for it. It is restated normatively in Section 5, together with what makes a deserialized value valid and which decisions are left to the calling protocol. Point serialization is given for BLS12-381 and BLS48-581; scalar serialization applies to all three curves.¶

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.1. Elliptic Curves

Let p be a prime number at least 5, and let q be a power of p. 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 n, we define the set of (GF(q^n))-rational points of E, denoted by E(GF(q^n)), to be the set of all solutions (x,y) in GF(q^n), 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^n)) forms a group under a group law that can be defined geometrically as follows. For P and Q in E(GF(q^n)) 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.¶

2.2. Pairings

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), and let r be a large prime dividing the order of E(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 pi be the p-power Frobenius endomorphism, which maps a point (x, y) of E to (x^p, y^p), and let E(GF(p^k))[r] be the r-torsion subgroup of E(GF(p^k)). The pairing is defined on the two subgroups¶

G_1 = E(GF(p^k))[r] intersect ker(pi - [1]) = E(GF(p))[r],
G_2 = E(GF(p^k))[r] intersect ker(pi - [p]),

where ker(pi - [a]) denotes the set of points T with pi(T) = [a]T. For the curves considered in this document, both G_1 and G_2 have order r. G_2 is identified by the eigenvalue p, and not merely as an order r subgroup of E(GF(p^k)): that weaker description is satisfied by G_1 as well, and the pairing computed in Appendix A is degenerate when both of its arguments are taken from G_1.¶

Let d be a divisor of k and E' be an elliptic curve defined over GF(p^(k/d)). If there is an isomorphism psi from E'(GF(p^k)) to E(GF(p^k)), then E' is called the twist of E. It is more efficient to hold elements of G_2 as points of E'(GF(p^(k/d))), whose coordinates lie in a smaller field. Write G'_2 for the preimage of G_2 under psi, that is, the set of points Q of E'(GF(p^(k/d))) with psi(Q) in G_2. For the curves in this document, G_2 lies in the image of E'(GF(p^(k/d))) under psi, which is what makes that representation possible; since psi is injective, G'_2 is a subgroup of order r, and psi restricted to G'_2 is an isomorphism onto G_2. The formula for psi is given for each curve in Section 4. What is given there is the restriction of psi to E'(GF(p^(k/d))), which is an injective homomorphism into E(GF(p^k)) and not an isomorphism, since E'(GF(p^(k/d))) and E(GF(p^k)) differ in size. The formula is the same in either case. Where a point of G_2 is written with coordinates in this document, as in Section 4 and in Section 5, it is the corresponding point of G'_2 that is written; psi carries it back to G_2 when the pairing is evaluated. 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:¶

1. Bilinearity: for any S in G_1, T in G_2, and integers K and L, e([K]S, [L]T) = e(S, T)^{K * L}.¶

2. Non-degeneracy: for every T in G_2 other than O_E, e(S, T) = 1 if and only if S = O_E; and for every S in G_1 other than O_E, e(S, T) = 1 if and only if T = O_E. The identity element has to be excluded on both sides: by bilinearity, e(S, O_E) = 1 holds for every S in G_1, and e(O_E, T) = 1 for every T in G_2.¶

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:¶

GF(p):

a finite field with characteristic p.¶

GF(p^k):

an extension field of degree k.¶

(GF(p))^*:

the multiplicative group of GF(p).¶

(GF(p^k))^*:

the multiplicative group of GF(p^k).¶

b:

the coefficient of the curve equation E: y^2 = x^3 + b.¶

O_E:

the point at infinity over an elliptic curve E.¶

E(GF(p^k)):

the group of GF(p^k)-rational points of E.¶

#E(GF(p^k)):

the number of GF(p^k)-rational points of E.¶

r:

the order of G_1 and G_2.¶

E(GF(p^k))[r]:

the r-torsion subgroup of E(GF(p^k)), that is, the set of points T of E(GF(p^k)) with [r]T = O_E.¶

pi:

the p-power Frobenius endomorphism, which maps a point (x, y) of E to (x^p, y^p).¶

BP:

a point in G_1. (The 'base point' of a cyclic subgroup of G_1)¶

h:

the cofactor h = #E(GF(p)) / r, where gcd(h, r) = 1.¶

h':

the cofactor h' = #E'(GF(p^(k/d))) / r, where gcd(h', r) = 1.¶

BP':

a point in G'_2. (The 'base point' of a cyclic subgroup of G'_2)¶

2.3. Barreto-Naehrig Curves

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 nu 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 / nu or b' = b * nu. BN curves are called D-type if b' = b / nu, and M-type if b' = b * nu. 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 defined in Section 2.2 and represented by the subgroup G'_2 of E'(GF(p^2)), and G_T as an order r subgroup of the multiplicative group (GF(p^12))^*.¶

2.4. Barreto-Lynn-Scott Curves

A BLS curve [BLS02] is another family of pairing-friendly 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 defined in Section 2.2 and represented by the subgroup G'_2 of E'(GF(p^2)) for BLS12 and of E'(GF(p^8)) for BLS48, and G_T as an order r subgroup of the multiplicative group (GF(p^12))^* for BLS12 and of the multiplicative group (GF(p^48))^* for BLS48.¶

3.1. Evaluating the Security of Pairing-Friendly Curves

The security of pairing-friendly 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 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 cryptography, 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.¶

3.2. Impact of Recent Attacks

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 can be written as k = i * j with gcd(i, j) = 1 and i, j > 1. Any k divisible by 6 meets this condition, taking i to be the largest power of 2 dividing k and j to be k / i; [KB16] accordingly gives k = 6 as the first case it treats. BN curves and BLS curves, whose embedding degree is divisible by 6, are therefore 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 improvements for reducing the amount of cost for solving FFDLP is using subfield 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].¶

4.1. Adoption Status of Pairing-friendly Curves

We show the pairing-friendly curves that have been selected by existing standards, cryptographic libraries, and applications. A comprehensive curve-by-curve comparison, including proposed alternatives that were not selected, is maintained at https://cfrg.github.io/draft-irtf-cfrg-pairing-friendly-curves/adoption-status.html.¶

The adoption status of pairing-friendly curves is surveyed in standards, libraries and applications. 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.¶

Parameters whose security level is more than 5 bits below the 128-bit level are not candidates for selection here, because this document recommends against using parameters that fall that far below the 128-bit level. They are still named in the subsections below wherever a standard or a library supports them, and Appendix F tabulates that adoption, which is useful information for implementers.¶

The security level for each curve is evaluated in accordance with [BD18], [GMT19], [MAF19] and [FK18]. For the 128-bit level, [G20] revisits the Special variant of the tower number field sieve, which applies to pairing-friendly curves because their characteristic is a polynomial of moderate degree with tiny coefficients evaluated at a seed. It revises the estimates of earlier work downward for the families it examines, with BLS12 and BN as the exceptions that it leaves unchanged. Note that the Freeman curves [Freeman06] and MNT curves [MNT01] are not included in this survey because [BD18] does not show the security levels of these curves.¶

4.2. For 128-bit Security

The survey in Section 4.1 shows a lot of cases of adopting BN and BLS curves. Among them, BLS12-381 and BN462 match our selection policy. In particular, the one that best matches the policy is BLS12-381 from the viewpoint of "widely used": as Section 4 states, its adoption in production deployments is what makes it the one exception to the preference for margin. We therefore 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 is close to 128 bits but less than 128 bits. 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.¶

t = -2^63 - 2^62 - 2^60 - 2^57 - 2^48 - 2^16

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).

psi(x', y') = (x' / w^2, y' / w^3)

t = 2^114 + 2^101 - 2^14 - 1

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).

psi(x', y') = (x' * w^2, y' * w^3)

4.3. For 256-bit Security

As shown in the survey in Section 4.1, there are three candidate pairing-friendly curves for 256-bit security: BLS48-556, BLS48-575 and BLS48-581. None of them is widely used in the sense of the policy given in Section 4, so the preference for margin governs. As noted in Section 3.2, [KIK17] puts the minimum size of p^k for BLS48 curves at 27,410 bits, which is 572 bits of p. BLS48-556 does not reach that size; BLS48-575 and BLS48-581 both exceed it, and BLS48-581 leaves the larger margin. We therefore select BLS48-581.¶

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 bits.¶

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. Concretely, in the tower above: w^2 = -v gives -1 / w = w / v, and v^2 = -(u + 1) gives w / v = w * v / v^2 = -w * v / (u + 1); since u^2 = -1, 1 / (u + 1) = (1 - u) / 2, so -1 / w = ((u - 1) / 2) * v * w.¶

The untwist isomorphism psi of Section 2.2, restricted to E'(GF(p^8)), maps into E(GF(p^48)) and is given by¶

psi(x', y') = (x' * xi^2, y' * xi^3)

where xi = u * s in GF(p^48) satisfies xi^6 = -w, the reciprocal of the twist coefficient b' = -1 / w, per the tower given above. Concretely: u in GF(p^2) satisfies u^2 = -1, so u^6 = -1; s in GF(p^48) satisfies s^2 = -z and z^3 = -w, so s^6 = w; hence xi^6 = u^6 * s^6 = (-1) * w = -w.¶

We then give the parameters for BLS48-581 as follows.¶

• G_1 is the largest prime-order subgroup of E(GF(p))¶

  • BP = (x,y) : a 'base point', i.e., a generator of G_1¶

• G'_2 is the r-order subgroup of E'(GF(p^8)) corresponding to G_2 under psi¶

  • BP' = (x',y') : a 'base point', i.e., a generator of G'_2¶

    • 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 GF(p))¶

    • 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 GF(p))¶

  • h' : the cofactor #E'(GF(p^8))/r¶

p:

0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444
  a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48
  ac3edc154e6565912b

¶

r:

0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6
  e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c
  01

¶

x:

0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7
  544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d
  8c3bce8732315af640

¶

y:

0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279dd41b720e
  f7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f37aef7b926b
  576dbb5de3e2587a70

¶

x'_0:

0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156
  c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154
  dec34fd0b4ace8bfab

¶

x'_1:

0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e
  1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa14
  3f1669b36676b47c57

¶

x'_2:

0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccbab5ab
  6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3f0
  b46488156ca55a3e6a

¶

x'_3:

0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f8be0
  cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80bc
  3f09a7033cbb7feafe

¶

x'_4:

0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386
  699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4c
  bb739c3a1c53f8cce5

¶

x'_5:

0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb03741
  8181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce33
  70f2004d914a3c093a

¶

x'_6:

0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0b7a4
  49cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c33
  54e41607e60750e057

¶

x'_7:

0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7
  f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3
  f84e19da00fbc6ae34

¶

y'_0:

0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc435fa
  ab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c0f
  f323edd3fe4d2d7971

¶

y'_1:

0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d72964732fcb
  f3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ffc7
  b111471db936cd5665

¶

y'_2:

0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d370514
  475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b8f
  de68332a526a2a8474

¶

y'_3:

0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e122d2
  742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e533
  7316213da92841589d

¶

y'_4:

0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f112985
  7ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf7a
  43f47831f982e50137

¶

y'_5:

0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055ab750
  4fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226cf3
  a594eedc58cf90bee4

¶

y'_6:

0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c819a6
  df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9aa6
  2b3d41faeafeb23986

¶

y'_7:

0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8eca9a
  9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e84069c
  55d667ffcb732718b6

¶

h:

0x85555841aaaec4ac¶

b:

1¶

h':

0x170e915cb0a6b7406b8d94042317f811d6bc3fc6e211ada42e58ccfcb3ac076a
  7e4499d700a0c23dc4b0c078f92def8c87b7fe63e1eea270db353a4ef4d38b59
  98ad8f0d042ea24c8f02be1c0c83992fe5d7725227bb27123a949e0876c0a8ce
  0a67326db0e955dcb791b867f31d6bfa62fbdd5f44a00504df04e186fae033f1
  eb43c1b1a08b6e086eff03c8fee9ebdd1e191a8a4b0466c90b389987de5637d5
  dd13dab33196bd2e5afa6cd19cf0fc3fc7db7ece1f3fac742626b1b02fcee040
  43b2ea96492f6afa51739597c54bb78aa6b0b99319fef9d09f768831018ee656
  4c68d054c62f2e0b4549426fec24ab26957a669dba2a2b6945ce40c9aec6afde
  da16c79e15546cd7771fa544d5364236690ea06832679562a68731420ae52d0d
  35a90b8d10b688e31b6aee45f45b7a5083c71732105852decc888f64839a4de3
  3b99521f0984a418d20fc7b0609530e454f0696fa2a8075ac01cc8ae3869e8d0
  fe1f3788ffac4c01aa2720e431da333c83d9663bfb1fb7a1a7b90528482c6be7
  892299030bb51a51dc7e91e9156874416bf4c26f1ea7ec578058563960ef92bb
  bb8632d3a1b695f954af10e9a78e40acffc13b06540aae9da5287fc4429485d4
  4e6289d8c0d6a3eb2ece35012452751839fb48bc14b515478e2ff412d930ac20
  307561f3a5c998e6bcbfebd97effc6433033a2361bfcdc4fc74ad379a16c6dea
  49c209b1

¶

b':

-1 / w¶

Section 5 defines a normative point serialization format for BLS48-581 (with test vectors in Appendix D), extending the format defined by [ZcashRep] for BLS12-381 as specified in [I-D.ietf-cose-bls-key-representations].¶

5.1. Parameters and Notation

Below, we give detailed serialization and deserialization procedures, applicable to both curves using the parameters above. The following notation is used in the rest of this section:¶

• Elements of GF(p^m) are represented as a vector of m coefficients in GF(p), (y_0, ..., y_{m-1}), using the basis and coefficient ordering already defined for each curve in Section 4.¶

• The identity element of G_1 is the point at infinity O_E of Section 2.1, and the identity element of G'_2 is the point at infinity on E'. Below, 'the point at infinity' refers to whichever of the two curves is in question.¶

• For a byte string str, str[0] is defined as the first byte of str.¶

• The function sign_GF_p(y) returns one bit representing the sign of an element of GF(p). This function is defined as follows:¶

sign_GF_p(y) := { 1 if y > (p - 1) / 2, else
                { 0 otherwise.

• The function sign_GF_p^m(y), for an element y = (y_0, ..., y_{m-1}) of GF(p^m), returns one bit computed as follows: let i be the largest index in {0, ..., m-1} such that y_i is nonzero, or i = 0 if all coefficients are zero; return sign_GF_p(y_i). For BLS12-381 (m=2), this specializes to: sign_GF_p^2(y') = sign_GF_p(y'_0) if y'_1 equals 0, else sign_GF_p(y'_1). For BLS48-581 (m=8), this is the same function specified as sign_GF_p^8 in [I-D.ietf-cose-bls-key-representations], evaluated over the coefficient ordering (y'_0, ..., y'_7) given in Section 4.¶

• The function OS2FE(str, n), for a byte string str of m*n bytes, returns an element of GF(p^m) or INVALID. It inverts the coordinate serialization of step 3 of Section 5.3: divide str into m consecutive blocks of n bytes each, and for each i in {0, ..., m-1} let y_i = OS2IP(str_i), where str_i is the block starting at offset (m - 1 - i) * n, so that the blocks give the coefficients in decreasing index order. If any y_i is greater than or equal to p, OS2FE returns INVALID; otherwise it returns y = (y_0, ..., y_{m-1}).¶

Section 5.4 requires deciding whether a field element y2 is a square and, where it is, computing a square root. This document does not specify how. The following pointers are provided for implementers and are not requirements.¶

For y2 in GF(p), all curves in this document have p = 3 (mod 4). Appendix I.1 of [RFC9380] therefore applies directly: y2 is a square exactly when y2^((p-1)/2) is 0 or 1, and a square root is given by y2^((p+1)/4).¶

For y2 in GF(p^m), that shortcut does not apply, since p^2 and p^8 are both 1 (mod 4). Appendix I.4 of [RFC9380] gives a constant-time Tonelli-Shanks procedure for a general field, and Appendix I.5 gives an is_square test for GF(p^2).¶

5.2. Scalar Serialization

This section defines a serialization format for elements of the scalar field GF(r), where r is the order of G_1 and G_2 as given for each curve in Section 4. Unlike point serialization, this format applies to all three curves in this document (BLS12-381, BN462, and BLS48-581), since no metadata bits are required.¶

For a curve with scalar field order r represented in n_s = ceil(L_r / 8) bytes, where L_r is the bit length of r:¶

Serialization: a scalar kappa in the range [0, r - 1] is serialized as I2OSP(kappa, n_s).¶

Deserialization: given a byte string s_string of length n_s, let kappa = OS2IP(s_string). If kappa >= r, return INVALID. Otherwise, return kappa.¶

Rejecting values greater than or equal to r gives every scalar exactly one encoding, which matters wherever an encoded scalar is hashed or compared as bytes. The byte order is the big-endian order of I2OSP and OS2IP [RFC8017], which is the order used by [I-D.irtf-cfrg-bbs-signatures] and [I-D.ietf-cose-bls-key-representations]. Other specifications for prime-order groups encode scalars in little-endian order, [RFC8032] among them, so an implementation working with both needs to convert.¶

This document does not define a distinct encoding for the zero scalar. Whether a protocol accepts it is a protocol-level decision, discussed in Section 5.6.3.¶

5.3. Point Serialization

This section defines point_to_octets_G1 and point_to_octets_G2. point_to_octets_G1 takes an element of G_1, which is a point on E, and point_to_octets_G2 takes an element of G'_2, which is a point on E'; each returns a byte string. Both are given by the single procedure below, stated for a point P = (x, y) and the parameters n and m of Section 5.1. This procedure uses the I2OSP function defined in [RFC8017].¶

1. Compute the metadata bits C_bit, I_bit, and S_bit, as follows:¶

   • C_bit is 1 if point compression should be used, otherwise it is 0.¶

   • I_bit is 1 if P is the point at infinity, otherwise it is 0.¶

   • S_bit is 0 if P is the point at infinity or if point compression is not used. Otherwise (i.e., when point compression is used and P is not the point at infinity), if P is a point on E, S_bit = sign_GF_p(y), else if P is a point on E', S_bit = sign_GF_p^m(y).¶

2. Let m_byte = (C_bit * 2^7) + (I_bit * 2^6) + (S_bit * 2^5).¶

3. Let x_string be the serialization of x, which is defined as follows:¶

   • If P is the point at infinity on E, let x_string = I2OSP(0, n).¶

   • If P is a point on E other than the point at infinity, then x is an element of GF(p), i.e., an integer in the inclusive range [0, p - 1]. In this case, let x_string = I2OSP(x, n).¶

   • If P is the point at infinity on E', let x_string = I2OSP(0, m*n).¶

   • If P is a point on E' other than the point at infinity, then x can be represented as (x_0, ..., x_{m-1}) where each x_i is an element of GF(p). In this case, let x_string = I2OSP(x_{m-1}, n) concatenated with I2OSP(x_{m-2}, n), ..., concatenated with I2OSP(x_0, n) (i.e., coefficients in decreasing index order). Notice that in all of the above cases, the 3 most significant bits of x_string[0] are guaranteed to be 0.¶

4. 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.¶

5. Let s_string be the concatenation of x_string and y_string.¶

6. 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.)¶

7. Return s_string.¶

5.4. Point Deserialization

This section defines octets_to_point_G1 and octets_to_point_G2. Each takes a byte string and returns an element of G_1 or of G'_2 respectively, or INVALID. A string that deserializes to a point of E or E' that is not in the group is INVALID, so a value returned by these procedures is a group element and a caller does not have to obtain one by a further step.¶

This document does not define a deserialization procedure that stops at E or E'. G_1 and G_2 are the groups on which the pairing of Section 2.2 is defined, and elements of G_1 and of G'_2 are what the specifications citing this document exchange; psi carries an element of G'_2 to the corresponding element of G_2, on which the pairing operates, as described in Section 2.2. Section 5.3 of [I-D.irtf-cfrg-bls-signature] requires conforming implementations to perform the subgroup check for the same reason, and Section 6.2 of [I-D.irtf-cfrg-bbs-signatures] notes that a library may combine the two operations.¶

The procedure below is stated once, for a string s_string and the parameters n and m of Section 5.1. It uses the OS2IP function defined in [RFC8017] and the OS2FE function defined in Section 5.1.¶

Each of the two functions fixes the group it returns, and the curve that step 2 determines is what selects between them. octets_to_point_G1 MUST return INVALID if step 2 determines E', and octets_to_point_G2 MUST return INVALID if step 2 determines E. This check is not redundant: the encodings of the two groups can have the same length. For BLS12-381, for instance, a 96-byte string is a compressed point on E' when C_bit is 1 and an uncompressed point on E when C_bit is 0, so without this rule a compressed element of G'_2 passed to octets_to_point_G1 would be decoded and returned rather than rejected.¶

Every GF(p) coefficient recovered by this procedure MUST be an integer in the inclusive range [0, p - 1]. A byte string that encodes a coordinate, or a coefficient of a coordinate, as a value greater than or equal to p is not a canonical encoding of a field element; implementations MUST return INVALID in that case. This applies to coordinates on E, recovered with OS2IP, as well as to the coefficients of coordinates on E', recovered with OS2FE.¶

1. If s_string is empty, return INVALID. Otherwise, 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, return INVALID. Otherwise:¶

   • Let C_bit equal the most significant bit of m_byte,¶

   • Let I_bit equal the second most significant bit of m_byte, and¶

   • Let S_bit equal the third most significant bit of m_byte.¶

2. If C_bit is 1:¶

   • If s_string has length n bytes, the output point is on the curve E.¶

   • If s_string has length m*n bytes, the output point is on the curve E'.¶

   • If s_string has any other length, return INVALID.¶

   If C_bit is 0:¶

   • If s_string has length 2n bytes, the output point is on E.¶

   • If s_string has length 2*m*n bytes, the output point is on E'.¶

   • If s_string has any other length, return INVALID.¶

3. Let s_string[0] = s_string[0] AND 0x1F, where AND is computed bitwise. In other words, set the three most significant bits of s_string[0] to 0.¶

4. If I_bit is 1:¶

   • If s_string is not the all zeros string, return INVALID.¶

   • Otherwise (i.e., if s_string is the all zeros string), return the identity element of the group determined in step 2.¶

   Otherwise, I_bit is 0. Continue.¶

5. If C_bit is 0:¶

   • Let x_string be the first half of s_string.¶

   • Let y_string be the last half of s_string.¶

   • If the curve that was determined in step 2 is E:¶

     • Let x = OS2IP(x_string). If x is greater than or equal to p, return INVALID.¶

     • Let y = OS2IP(y_string). If y is greater than or equal to p, return INVALID.¶

     • If the point P = (x, y) is not a valid point on E, return INVALID.¶

   • Otherwise (i.e., when the curve that was determined in step 2 is E'):¶

     • Let x = OS2FE(x_string, n). If x is INVALID, return INVALID.¶

     • Let y = OS2FE(y_string, n). If y is INVALID, return INVALID.¶

     • If the point P = (x, y) is not a valid point on E', return INVALID.¶

   Let P = (x, y) and continue at step 8.¶

   Otherwise, C_bit is 1. Continue.¶

6. Let x_string be s_string.¶

   • If the curve that was determined in step 2 is E:¶

     • Let x = OS2IP(x_string). If x is greater than or equal to p, return INVALID.¶

     • Let y2 = the right-hand side of the curve equation for E (given in Section 4 for the curve in question), evaluated at x, in GF(p).¶

     • If y2 is not square in GF(p), return INVALID.¶

     • Otherwise, let y = sqrt(y2) in GF(p) and let Y_bit = sign_GF_p(y).¶

   • Otherwise (i.e., when the curve that was determined in step 2 is E'):¶

     • Let x = OS2FE(x_string, n). If x is INVALID, return INVALID.¶

     • Let y2 = the right-hand side of the curve equation for E' (given in Section 4 for the curve in question), evaluated at x, in GF(p^m).¶

     • If y2 is not square in GF(p^m), return INVALID.¶

     • Otherwise, let y = sqrt(y2) in GF(p^m) and let Y_bit = sign_GF_p^m(y).¶

7. If S_bit equals Y_bit, let P = (x, y). Otherwise, let P = (x, -y).¶

8. If the curve determined in step 2 is E and subgroup_check_G1(P) returns FALSE, return INVALID. If the curve determined in step 2 is E' and subgroup_check_G2(P) returns FALSE, return INVALID. Otherwise, return P.¶

Note that OS2FE outputs field elements in the towered representation of the curve in question:¶

• For BLS12-381, OS2FE(x_string, n) = (x'_0, x'_1) = x'_0 + x'_1 * u¶

• For BLS48-581, OS2FE(x_string, n) = (x'_0, ..., x'_7) = 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¶

5.5. Applicability to BN462

This document does not specify a point encoding for BN462. Scalar serialization, defined in Section 5.2, and the subgroup checks of Section 5.4.1 are unaffected and apply to BN462 as well.¶

The coordinate encoding of Section 5.3 (coordinates as fixed-length big-endian integers, with the coefficients of an element of GF(p^m) in decreasing index order) carries over to BN462 unchanged. What does not fit is the placement of the metadata bits. BN462 has a 462-bit characteristic p, so its canonical GF(p) representation occupies n = ceil(462 / 8) = 58 bytes, that is 464 bits. This leaves 2 unused bits in the leading byte of a serialized coordinate, one short of the three (C_bit, I_bit, S_bit) that the scheme above places there. Appendix E describes two ways of accommodating that: carrying the metadata in a byte of its own, following the general pattern of [SEC1], which leaves the rest of the format unchanged; or restricting the format to uncompressed points, which need only C_bit and I_bit and therefore fit in the two bits available.¶

This document specifies neither. The format above is specified here because it is already widely used in applications, and because specifications depend on it: it originates with [ZcashRep] and is relied upon by [I-D.irtf-cfrg-bbs-signatures] and [I-D.ietf-cose-bls-key-representations]. For BN462 neither consideration holds: no specification examined requires a BN462 point encoding, and the implementations that do emit BN462 points have not converged on one of the variants above. Choosing among them would therefore be encoding design rather than the recording of established practice, and this document restates an encoding only where practice has already settled on one.¶

Implementations that nevertheless need to exchange BN462 points may find Appendix E useful. It records, informatively, the encodings that existing implementations use and the alternatives that have been considered. It defines no format.¶

5.6. Requirements on Calling Protocols

The procedures above leave three decisions to the protocol that uses them. This document does not decide them, because the right answer depends on what the protocol does rather than on the curve or the wire format. A specification that adopts this format SHOULD state its answer to each.¶

A.1. Optimal Ate Pairings over Barreto-Naehrig Curves

Let c = 6 * t + 2 for a parameter t and c_0, c_1, ... , c_N in {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., N) 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_N in {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., N) equals c, and the order r of G_1 as input, and outputs e(P, Q).¶

f := 1; T := Q;
if (c_N = -1) then
    T := -T;
end if
for i = N-1 downto 0
    f := f^2 * Line_function(T, T, P); T := T + T;
    if (c_i = 1) then
        f := f * Line_function(T, Q, P); T := T + Q;
    else if (c_i = -1) then
        f := f * Line_function(T, -Q, P); T := T - 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;

A.2. Optimal Ate Pairings over Barreto-Lynn-Scott Curves

Let c = t for a parameter t and c_0, c_1, ... , c_N in {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., N) equals c.¶

The following algorithm shows the computation of the optimal ate pairing on Barreto-Lynn-Scott curves. It takes P in G_1, Q in G_2, an integer c, c_0, ...,c_N in {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., N) equals c, and the order r of G_1 as input, and outputs e(P, Q).¶

f := 1; T := Q;
if (c_N = -1) then
    T := -T;
end if
for i = N-1 downto 0
    f := f^2 * Line_function(T, T, P); T := T + T;
    if (c_i = 1) then
        f := f * Line_function(T, Q, P); T := T + Q;
    else if (c_i = -1) then
        f := f * Line_function(T, -Q, P); T := T - Q;
    end if
end for
f := f^{(p^k - 1) / r}
return f;

B.1. Cofactors in Existing Libraries

Some implementations evaluate a fixed multiple of the final exponent. Their output differs from the literal output of the pseudocode in Appendix A by a curve-specific exponent in G_T:¶

e_lib(P, Q) = e_pseudocode(P, Q)^alpha

where alpha is:¶

• BLS12-381: alpha = 3 [HHT20]¶

• BN462: alpha = 2t(6t^2 + 3t + 1) mod r [FCKR11]¶

• BLS48-581: alpha = 3 [HHT20]¶

Because gcd(alpha, r) = 1 for all three curves, the following properties hold:¶

• Bilinearity is preserved: e_lib([K]P, [L]Q) = e_lib(P, Q)^{K * L}.¶

• Verification equations of the form e(A, B) = e(C, D) hold using e_lib if and only if they hold using e_pseudocode.¶

• Direct byte-comparison between e_lib output and the test vectors in Appendix C will not match. Implementations seeking byte-level reproducibility of those test vectors should evaluate the pseudocode in Appendix A literally, without applying the cofactor optimization.¶

B.2. Final Exponentiation Decomposition

The pseudocode in Appendix A writes the final exponentiation as a single step, f := f^((p^k - 1) / r). In practice, implementations compute this via an easy/hard split: an easy part computed cheaply via the Frobenius endomorphism, and a hard part computed via an addition chain over the curve parameter t.¶

Standard references for the hard-part addition chain include [SBCK09] (the original approach for BLS curves) and [AKLGL11] (for BN curves). [FCKR11] and [HHT20] are cited in Appendix B.1 for a different reason: each evaluates a fixed multiple of the hard part rather than the hard part itself, which is where the exponent alpha given there comes from.¶

D.1. BLS12-381 Points

G_1 (BP), compressed (48 bytes):¶

97f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac58
6c55e83ff97a1aeffb3af00adb22c6bb

G_1 (BP), uncompressed (96 bytes):¶

17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac58
6c55e83ff97a1aeffb3af00adb22c6bb08b3f481e3aaa0f1a09e30ed741d8ae4
fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1

G'_2 (BP'), compressed (96 bytes):¶

93e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049
334cf11213945d57e5ac7d055d042b7e024aa2b2f08f0a91260805272dc51051
c6e47ad4fa403b02b4510b647ae3d1770bac0326a805bbefd48056c8c121bdb8

G'_2 (BP'), uncompressed (192 bytes):¶

13e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049
334cf11213945d57e5ac7d055d042b7e024aa2b2f08f0a91260805272dc51051
c6e47ad4fa403b02b4510b647ae3d1770bac0326a805bbefd48056c8c121bdb8
0606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af267492ab572e99ab
3f370d275cec1da1aaa9075ff05f79be0ce5d527727d6e118cc9cdc6da2e351a
adfd9baa8cbdd3a76d429a695160d12c923ac9cc3baca289e193548608b82801

Identity on E: 48 zero bytes with the leading byte set to 0xc0 (C_bit = 1, I_bit = 1) when compressed, and 96 zero bytes with the leading byte set to 0x40 (I_bit = 1) when uncompressed.¶

Identity on E': 96 zero bytes with the leading byte set to 0xc0 when compressed, and 192 zero bytes with the leading byte set to 0x40 when uncompressed.¶

• Note: the point values above are the second entry of each of the valid test vector files distributed with [zkcrypto-bls12-381], whose first entry is the identity; they have been compared byte for byte. The uncompressed values are derived from the same coordinates by the procedure of Section 5.3, and have been checked to deserialize back to those coordinates. The same strings have also been checked against [blst] and [gnark-crypto]: each deserializes to the coordinates given in Section 4.2.1 and serializes back to the same bytes. The BLS12-381 scalars of Appendix D.3 were checked against the same two implementations.¶

D.2. BLS48-581 Points

G_1 (BP), compressed (73 bytes):¶

a2af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7
544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d
8c3bce8732315af640

G_1 (BP), uncompressed (146 bytes):¶

02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7
544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d
8c3bce8732315af6400cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a
52e991279dd41b720ef7bb7beffb98aee53e80f678584c3ef22f487f77c2876d
1b2e35f37aef7b926b576dbb5de3e2587a70

G'_2 (BP'), compressed (584 bytes):¶

8827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7
f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3
f84e19da00fbc6ae340b9b7951c6061ee3f0197a498908aee660dea41b39d138
52b6db908ba2c0b7a449cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c2
2d63334b5b0e205c3354e41607e60750e0570c96c7797eb0738603f1311e4ecd
a088f7b8f35dcef0977a3d1a58677bb037418181df63835d28997eb57b40b9c0
b15dd7595a9f177612f097fc7960910fce3370f2004d914a3c093a038b91c600
b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386699981f9e4
8199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb739c3a1c
53f8cce50be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a
393f8be0cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8
cb4e80bc3f09a7033cbb7feafe01fccc70198f1334e1b2ea1853ad83bc73a8a6
ca9ae237ca7a6d6957ccbab5ab6860161c1dbd19242ffae766f0d2a6d55f028c
bdfbb879d5fea8ef4cded6b3f0b46488156ca55a3e6a07c4973ece2258512069
b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e1c3943a00abfedf16214
a76affa62504f0c3c7630d979630ffd75556a01afa143f1669b36676b47c5705
d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156c4
6ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154de
c34fd0b4ace8bfab

G'_2 (BP'), uncompressed (1168 bytes):¶

0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7
f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3
f84e19da00fbc6ae340b9b7951c6061ee3f0197a498908aee660dea41b39d138
52b6db908ba2c0b7a449cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c2
2d63334b5b0e205c3354e41607e60750e0570c96c7797eb0738603f1311e4ecd
a088f7b8f35dcef0977a3d1a58677bb037418181df63835d28997eb57b40b9c0
b15dd7595a9f177612f097fc7960910fce3370f2004d914a3c093a038b91c600
b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386699981f9e4
8199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb739c3a1c
53f8cce50be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a
393f8be0cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8
cb4e80bc3f09a7033cbb7feafe01fccc70198f1334e1b2ea1853ad83bc73a8a6
ca9ae237ca7a6d6957ccbab5ab6860161c1dbd19242ffae766f0d2a6d55f028c
bdfbb879d5fea8ef4cded6b3f0b46488156ca55a3e6a07c4973ece2258512069
b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e1c3943a00abfedf16214
a76affa62504f0c3c7630d979630ffd75556a01afa143f1669b36676b47c5705
d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156c4
6ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154de
c34fd0b4ace8bfab035e2524ff89029d393a5c07e84f981b5e068f1406be8e50
c87549b6ef8eca9a9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f
748e5ac66e84069c55d667ffcb732718b60896767811be65ea25c2d05dfdd17a
f8a006f364fc0841b064155f14e4c819a6df98f425ae3a2864f22c1fab8c74b2
618b5bb40fa639f53dccc9e884017d9aa62b3d41faeafeb2398607d0d0374573
6b7a513d339d5ad537b90421ad66eb16722b589d82e2055ab7504fa83420e8c2
70841f6824f47c180d139e3aafc198caa72b679da59ed8226cf3a594eedc58cf
90bee40d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f
1129857ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdd
dfcf7a43f47831f982e501370aec25a4621edc0688223fbbd478762b1c2cded3
360dcee23dd8b0e710e122d2742c89b224333fa40dced2817742770ba10d67bd
a503ee5e578fb3d8b8a1e5337316213da92841589d0b36a201dd008523e421ef
b70367669ef2c2fc5030216d5b119d3a480d370514475f7d5c99d0e904115155
36ca3295e5e2f0c1d35d51a652269cbc7c46fc3b8fde68332a526a2a84740284
dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d72964732fcbf3af
b096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ffc7b111
471db936cd566500eb53356c375b5dfa497216452f3024b918b4238059a577e6
f3b39ebfc435faab0906235afa27748d90f7336d8ae5163c1599abf77eea6d65
9045012ab12c0ff323edd3fe4d2d7971

Identity on E: 73 zero bytes with the leading byte set to 0xc0 (C_bit = 1, I_bit = 1) when compressed, and 146 zero bytes with the leading byte set to 0x40 (I_bit = 1) when uncompressed.¶

Identity on E': 584 zero bytes with the leading byte set to 0xc0 when compressed, and 1168 zero bytes with the leading byte set to 0x40 when uncompressed.¶

• Note: the point values above are newly computed for this document by applying the sign_GF_p^8 function of [I-D.ietf-cose-bls-key-representations] to the BP' coordinates in Section 4.¶

D.3. Scalars

The values below are the boundary cases of Section 5.2: the zero scalar, the smallest nonzero scalar, the largest scalar the procedure accepts, and the smallest value it rejects. The value kappa = 1 distinguishes the byte order, and kappa = r exercises the rejection of values that are not less than r.¶

BLS12-381 (n_s = 32):¶

kappa = 0
0000000000000000000000000000000000000000000000000000000000000000
kappa = 1
0000000000000000000000000000000000000000000000000000000000000001
kappa = r - 1
73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000000
kappa = r  (deserialization returns INVALID)
73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

BN462 (n_s = 58):¶

kappa = 0
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000
kappa = 1
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000001
kappa = r - 1
240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908e
e1c201f7fffffffff6ff66fc7bf717f7c0000000002401b007e010800c
kappa = r  (deserialization returns INVALID)
240480360120023ffffffffff6ff0cf6b7d9bfca0000000000d812908e
e1c201f7fffffffff6ff66fc7bf717f7c0000000002401b007e010800d

BLS48-581 (n_s = 65):¶

kappa = 0
000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
kappa = 1
000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000001
kappa = r - 1
2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6e7
41969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c00
kappa = r  (deserialization returns INVALID)
2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6e7
41969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c01

E.1. The Constraint

The format of Section 5 carries three metadata bits (C_bit, I_bit, S_bit) in the three most significant bits of the first byte of a serialized coordinate. This requires the canonical representation of an element of GF(p) to leave at least three unused bits in its leading byte.¶

BN462 has a 462-bit characteristic p, so n = ceil(462 / 8) = 58 bytes, i.e. 464 bits, and only 464 - 462 = 2 bits are unused: one bit short, as stated in Section 5.5.¶

The same criterion appears in implementations. [MIRACL] selects between two point encodings at compile time using the condition (MBITS - 1) mod 8 <= 4, where MBITS is the bit length of p; this condition holds exactly when the leading byte of a coordinate has three or more unused bits. When it holds, the library packs a compression flag (0x80) and a sign flag (0x20) into that byte, reserving 0x40; when it does not, it falls back to the [SEC1] encoding described in Appendix E.4. For BN462, (462 - 1) mod 8 = 5, so the fallback is used. The diagnosis above is therefore not particular to this document: an implementation supporting BN462 reaches the same conclusion by the same test. (The bit-packing path is additionally gated on a build-time option that the shipped configuration does not enable, so the default build uses the fallback encoding for every curve it supports.)¶

E.2. Encodings Used by Existing Implementations

Few libraries implement BN462 at all. Among those surveyed for this document, it is absent from [RELIC], [blst], [gnark-crypto], [noble-curves] and [arkworks], each of which does implement BLS12-381. The following do provide it:¶

Sizes are given as uncompressed / compressed, for G_1. For [MIRACL] and [zig-pairings], the corresponding G'_2 sizes are 233 bytes uncompressed and 117 bytes compressed. The [SEC1] type byte is 0x04 for an uncompressed point and 0x02 or 0x03 for a compressed one; the dedicated flag byte is described in Appendix E.4. The byte order given for [mcl] is its default.¶

Both leading-byte forms leave the coordinate encoding of Section 5.3 untouched: [MIRACL] writes the coefficients of a GF(p^2) coordinate in decreasing index order, as that section does, and so does [zig-pairings]. The two differ only in what the leading byte means. Note that [SEC1] itself defines point encoding over GF(p) and GF(2^m) only, so its type byte applied to E'(GF(p^2)) is an extension of it by the coefficient rule of Section 5.3 rather than [SEC1] as written.¶

In [mcl], BN462 is marked deprecated. Its affine serialization writes x followed by y with no metadata at all, its compressed form stores the parity of y in the most significant bit of the most significant byte of the coordinate, and the identity element is represented by an all-zero string. [MIRACL] likewise has no distinct representation for the identity element: its coordinates are zero and the ordinary type byte is emitted, so the identity element is recognized by inspecting the coordinate values rather than by a metadata bit. This differs from the approach of Section 5, which represents the identity element explicitly through I_bit and leaves the decision of whether to accept it to the calling protocol (Section 5.6.2).¶

Two observations follow. First, the implementations that support BN462 and do not mark it deprecated have converged on a dedicated leading byte rather than on packing metadata into the coordinate; [mcl], which does mark it deprecated, is the exception and packs the sign of y into the coordinate. Second, none of the implementations examined carries the pair C_bit and I_bit in the two spare bits of the coordinate, which is the arrangement Appendix E.3 considers.¶

E.3. Alternative Considered: Two Metadata Bits

S_bit is meaningful only for compressed points (see step 1 of Section 5.3). An encoding restricted to uncompressed points therefore needs only C_bit and I_bit, which fit in the two spare bits that BN462 does have. The appeal of such an encoding is that BN462 would remain within the same bit-packing family as the other two curves: a decoder written for BLS12-381 could be extended to BN462 by masking two metadata bits instead of three, rather than by acquiring a second, leading-byte parser used only for BN462.¶

It carries a pitfall. Step 2 of Section 5.4 determines the curve jointly from C_bit and the length of the string. For BN462 (n = 58, and E' represented over GF(p^2)), an uncompressed point on E and a compressed point on E' both occupy 116 bytes. Under a two-bit variant, compressed forms cannot be represented and C_bit is always 0, so the two cases never both arise; but a decoder that reuses step 2 unmodified would accept a 116-byte string with C_bit set and interpret it as a compressed point on E'. An implementation of such a variant would have to reject a nonzero C_bit before the length-based determination in step 2. An encoding with a dedicated leading byte (Appendix E.4) does not have this hazard, because the type byte separates the two cases structurally.¶

The variant would also forgo point compression, which is the form most protocols transmit. No implementation of it was found.¶

E.4. Alternative Considered: A Dedicated Leading Byte

Moving the metadata out of the coordinate and into a byte of its own removes the constraint of Appendix E.1 entirely and keeps point compression available, at a cost of one byte. Two mutually incompatible variants are in use:¶

• The [SEC1] type byte: 0x04 for an uncompressed point, 0x02 or 0x03 for a compressed point with the value itself carrying the sign of y, followed by the coordinates in big-endian order. This is what [MIRACL] and [pfcurve-js] emit.¶

• A flag byte carrying the same three metadata bits as Section 5.3 in the same positions (C_bit at 0x80, I_bit at 0x40, S_bit at 0x20, with the remaining five bits zero and checked on input), followed by the coordinates in big-endian order. This is what [zig-pairings] emits. These are the same bit positions that [MIRACL] uses in its bit-packing path, so this variant amounts to relocating the bit assignment of Section 5 into a leading byte, leaving the rest of the format unchanged.¶

Both variants yield the same encoded lengths (117 and 59 bytes for G_1, 233 and 117 bytes for G'_2), so length alone does not distinguish them. The leading byte does: an uncompressed point other than the identity element begins with 0x04 in the first variant and 0x00 in the second. A decoder that validates the leading byte rather than skipping over it will therefore reject a string in the other format instead of misparsing it.¶

E.5. Why This Document Does Not Define a Format

Section 5.5 gives the reasons this document does not specify a BN462 point format. Two of them bear on what is recorded above. No specification examined defines or requires a BN462 point encoding, so the encodings listed here are library conventions rather than a format that a consumer of this document needs; and choosing among them would be encoding design rather than the recording of established practice.¶

Should BN462 point encodings converge, or should a protocol specification come to require one, a separate specification can define one. Of the encodings recorded above, the [SEC1] type byte is the most widely implemented among the libraries examined, and is the form an implementer is most likely to encounter when interoperating with existing BN462 code.¶