Pairing-Friendly Curves

1.1. Pairing-Based Cryptography

Elliptic curve cryptography is one of the important areas in recent cryptography. The cryptographic algorithms based on elliptic curve cryptography, such as ECDSA (Elliptic Curve Digital Signature Algorithm), are widely used in many applications.¶

Pairing-based cryptography, a variant of elliptic curve cryptography, has attracted the attention for its flexible and applicable functionality. Pairing is a special map defined over elliptic curves. Thanks to the characteristics of pairing, it can be applied to construct several cryptographic algorithms and protocols such as identity-based encryption (IBE), attribute-based encryption (ABE), authenticated key exchange (AKE), short signatures and so on. Several applications of pairing-based cryptography are now in practical use.¶

As the importance of pairing grows, elliptic curves where pairing is efficiently computable are studied and the special curves called pairing-friendly curves are proposed.¶

1.2. Applications of Pairing-Based Cryptography

Several applications using pairing-based cryptography are standardized and implemented. We show example applications available in the real world.¶

IETF publishes 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 by Fujioka-Suzuki-Ustaoglu [FSU10] are specified.¶

MIRACL implements M-Pin, a multi-factor authentication protocol [M-Pin]. M-Pin protocol includes a kind of zero-knowledge proof, where pairing is used for its construction.¶

Trusted Computing Group (TCG) specifies ECDAA (Elliptic Curve Direct Anonymous Attestation) in the specification of Trusted Platform Module (TPM) [TPM]. ECDAA is a protocol for proving the attestation held by a TPM to a verifier without revealing the attestation held by that TPM. Pairing is used for constructing ECDAA. FIDO Alliance [FIDO] and W3C [W3C] also published ECDAA algorithm similar to TCG.¶

Intel introduces Intel Enhanced Privacy ID (EPID) which enables remote attestation of a hardware device while preserving the privacy of the device as a functionality of Intel Software Guard Extensions (SGX) [EPID]. They extend TPM ECDAA to realize such functionality. A pairing-based EPID has been proposed [BL10] and distributed along with Intel SGX applications.¶

Zcash implements their own zero-knowledge proof algorithm named zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) [Zcash]. zk-SNARKs is used for protecting privacy of transactions of Zcash. They use pairing for constructing zk-SNARKS.¶

Cloudflare introduces Geo Key Manager [Cloudflare] to restrict distribution of customers' private keys to the subset of their data centers. To achieve this functionality, attribute-based encryption is used and pairing takes a role as a building block. In addition, Cloudflare published a new cryptographic library CIRCL[CIRCL] (Cloudflare Interoperable, Reusable Cryptographic Library) in 2019. They plan for supporting secure pairing-friendly curves in CIRCL.¶

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

1.3. Goal

The goal of this memo is to consider the security of pairing-friendly curves used in pairing-based cryptography and introduce secure parameters of pairing-friendly curves. Specifically, we explain the recent attack against pairing-friendly curves and how much the security of the curves is reduced. We show how to evaluate the security of pairing-friendly curves and give the parameters for 100 bits of security, which is no longer secure, 128, 192 and 256 bits of security.¶

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 Curve

Let p > 3 be a prime and q = p^n for a natural number n. Let F_q be a finite field. The curve defined by the following equation E is called an elliptic curve.¶

   E : y^2 = x^3 + A * x + B,

where x and y are in F_q, and A and B in F_q satisfy the discriminant inequality 4 * A^3 + 27 * B^2 != 0 mod q. This is called Weierstrass normal form of an elliptic curve.¶

Solutions (x, y) for an elliptic curve E, as well as the point at infinity, O_E, are called F_q-rational points. If P and Q are two points on the curve E, we can define R = P + Q as the opposite point of the intersection between the curve E and the line that passes through P and Q. We can define P + O_E = P = O_E + P as well. Similarly, we can define 2P = P + P and a scalar multiplication S = [a]P for a positive integer a can be defined as an (a-1)-time addition of P.¶

The additive group, denoted by E(F_q), is constructed by the set of F_q-rational points and the addition law described above. We can define the cyclic additive group with a prime order r by taking a base point BP in E(F_q) as a generator. This group is used for the elliptic curve cryptography.¶

We define terminology used in this memo as follows.¶

O_E:

the point at infinity over an elliptic curve E.¶

E(F_q):

a group constructed by F_q-rational points of E.¶

#E(F_q):

the number of F_q-rational points of E.¶

h:

a cofactor such that h = #E(F_q) / r.¶

2.2. Pairing

Pairing is a kind of the bilinear map defined over two elliptic curves E and E'. Examples include Weil pairing, Tate pairing, optimal Ate pairing [Ver09] and so on. Especially, optimal Ate pairing is considered to be efficient to compute and mainly used for practical implementation.¶

Let E be an elliptic curve defined over a prime field F_p and E' be an elliptic curve defined over an extension field of F_p. Let k be a minimum integer such that r is a divisor of p^k - 1, which is called an embedding degree. Let G_1 be a cyclic subgroup on the elliptic curve E with order r, and G_2 be a cyclic subgroup on the elliptic curve E' with order r. Let G_T be an order r subgroup of a multiplicative group (F_p^k)^*.¶

Pairing is defined as a bilinear map e: (G_1, G_2) -> G_T satisfying the following properties:¶

1. Bilinearity: for any S in G_1, T in G_2, and integers a and b, e([a]S, [b]T) = e(S, T)^{a * b}.¶
2. Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S = O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T = O_E.¶
3. Computability: for any S in G_1 and T in G_2, the bilinear map is efficiently computable.¶

2.3. Barreto-Naehrig Curve

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 multiplicative group of order p.¶

BN curves always have order 6 twists. If m is an element which is neither a square nor a cube in an extension field F_p^2, the twisted curve E' of E is defined over an extension field F_p^2 by the equation E': y^2 = x^3 + b' with b' = b / m or b' = b * m. BN curves are called D-type if b' = b / m, and M-type if b' = b * m. The embedded degree k is 12.¶

A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order r, G_2 as a subgroup of E'(F_p^2), and G_T as a subgroup of a multiplicative group (F_p^12)^* of order r.¶

2.4. Barreto-Lynn-Scott Curve

A BLS curve [BLS02] is another instantiations of pairings proposed in 2002. Similar to BN curves, a pairing over BLS curves constructs optimal Ate pairings.¶

A BLS curve is 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 twisted curve, E': y^2 = x^3 + b', is defined in the same way as BN curves. In contrast to BN curves, E(F_p) does not have a prime order. Instead, its order is divisible by a large parameterized prime r and denoted by h * r with cofactor h. The pairing will be defined on the r-torsions points. In the same way as BN curves, BLS curves can be categorized into D-type and M-type.¶

BLS curves vary according to different embedding degrees. In this memo, we deal with BLS12 and BLS48 families with embedding degrees 12 and 48 with respect to r, respectively.¶

In BLS curves, parameterized p and r are given by the following equations:¶

   BLS12:
       p = (t - 1)^2 * (t^4 - t^2 + 1) / 3 + t
       r = t^4 - t^2 + 1
   BLS48:
       p = (t - 1)^2 * (t^16 - t^8 + 1) / 3 + t
       r = t^16 - t^8 + 1

for a well chosen integer t.¶

A pairing e is defined by taking G_1 as a subgroup of E(F_p) of order r, G_2 as an order r subgroup of E'(F_p^2) for BLS12 and of E'(F_p^8) for BLS48, and G_T as an order r subgroup of a multiplicative group (F_p^12)^* for BLS12 and of a multiplicative group (F_p^48)^* for BLS48.¶

2.5. Representation Convention for an Extension Field

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 be an extension field of F_p of degree d and an indeterminate i.¶

For an element s in F_p^d such that s = s_0 + s_1 * i + ... + s_{d - 1} *  i^{d - 1} for s_0, s_1, ... , s_{d - 1} in a basefield F_p, s is represented as octet string by oct(s) = s_0 || s_1 || ... || s_{d - 1}.¶

Let F_p^d' be an extension field of F_p^d of degree d' / d and an indeterminate j.¶

For an element s' in F_p^d' such that s' = s'_0 + s'_1 * j + ... + s'_{d' / d - 1} * j^{d' / d - 1} for s'_0, s'_1, ..., s'_{d' / d - 1} in a basefield F_p^d, s' is represented as integer by oct(s') = oct(s'_0) || oct(s'_1) || ... || oct(s'_{d' / d - 1}), where oct(s'_0), ... , oct(s'_{d' / d - 1}) are octet strings encoded by above convention.¶

In general, one can define encoding between integer and an element of any finite field tower by inductively applying the above convention.¶

The parameters and test vectors of extension fields described in this memo are encoded by this convention and represented in octet stream.¶

When applications communicate elements in an extension field, using the compression method [MP04] may be more effective. In that case, you need to use it with care for interoperability.¶

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 computational bilinear Diffie-Hellman (CBDH) problem and bilinear Diffie-Hellman (BDH) Problem, decision bilinear Diffie-Hellman (DBDH) problem, gap DBDH problem, etc [ECRYPT]. Almost all of these variants are reduced to the hardness of discrete logarithm problems described above and believed to be easier than the discrete logarithm problems.¶

There would be the case where the attacker solves these reduced problems to break pairing-based cryptography. Since such attacks have not been discovered yet, we discuss the hardness of the discrete logarithm problems 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 well-known algorithms for solving the discrete logarithm problems include Pollard's rho algorithm [Pollard78], Index Calculus [HR83] and so on. In order to make index calculus algorithms more efficient, number field sieve (NFS) algorithms are utilized.¶

3.2. Impact of the Recent Attack

In 2016, Kim and Barbulescu proposed a new variant of the NFS algorithms, the extended tower number field sieve (exTNFS), which drastically reduces the complexity of solving FFDLP [KB16]. Due to exTNFS, the security level of 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 bits of security (BN256, for example) dropped down to approximately 100 bits [BD18].¶

Some papers showed 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 bits of security, Barbulescu and Duquesne estimated the minimum bit length of p of BN curves after exTNFS as 461 bits, and that of BLS12 curves as 461 bits [BD18]. For 256 bits of security, Kiyomura et al. estimated the minimum bit length of p^k of BLS48 curves as 27,410 bits, which implied 572 bits of p [KIK17].¶

4.1. Adoption Status of Pairing-friendly Curves

We show the pairing-friendly curves selected by existing standards, cryptographic libraries and applications.¶

Table 1 summarizes the adoption status of pairing-friendly curves. The details are described as 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 denoted as BLSk_XXX. Due to space limitations, Table 1 omits libraries that have not been maintained since 2016 in which exTNFS was proposed and curves that had security levels below 128 bits since before 2016 (ex. BN160). The full version of Table1 is available at https://lepidum.co.jp/blog/2020-03-27/ietf-draft-pfc/. In this table, security level for each curve is evaluated according to [BD18],[GME19], [MAF19] and [FK18]. Note that the curves marked as (*) indicate that the evaluation of security level does not take into account the impact of the exTNFS because [BD18] does not show the security level of these curves.¶

4.2. For 100 Bits of Security

Before exTNFS, BN curves with 256-bit size of underlying finite field (so-called BN256) were considered to achieve 128 bits of security. After exTNFS, however, the security level of BN curves with 256-bit size of underlying finite field fell into 100 bits.¶

Implementers who will newly develop the applications of pairing-based cryptography SHOULD NOT use pairing-friendly curves with 100 bits of security (i.e. BN256).¶

There exists applications which already implemented pairing-based cryptography with 100-bit secure pairing-friendly curves. In such a case, implementers MAY use 100 bits of security only if they need to keep interoperability with the existing applications.¶

4.3. For 128 Bits of Security

Table 1 shows that a lot of pairing-friendly curves whose curve types are BN curves and BLS curves are adopted as curves of 128 bits security level. Among them, the one that best matches our selection policy is BN462, so we introduce the parameters of BN462 in this section.¶

On the other hand, from the viewpoint of "widely use", BLS12_381 is an attractive curve because a lot of libraries and applications adopt it. However, because it is not published as a curve of 128-bit security level in peer-reviewed papers, it does not match our selection policy. In addition, according to [BD18], the bit length of p for BLS12 to achieve 128 bits of security is calculated as 461 bits and more, which BLS12_381 does not satisfy. Since BLS12_381 has a large influence from the viewpoint of interoperability, we introduce parameters of BLS12_381 in Appendix C.¶

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

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

4.4. For 192 Bits of Security

As shown in Table 1, candidates of pairing-friendly curves for the security level 192 bits are only two curves BLS24_477 and BLS24_479. BLS24_477 has only one implementation and BLS24_479 is an experimental parameter which is not shown in peer-reviewed paper. Therefore, because none match our selection policy, we couldn't show parameters for security level 192 bits here.¶

4.5. For 256 Bits of Security

As shown in Table 1, there are three candidats of pairing-friendly curves for security level 256 bit. According to our selection policy, we select BLS48_581 which is the most adopted by cryptographic libraries.¶

The selected BLS48 curve is shown in [KIK17] and it is defined by a parameter¶

    t = -1 + 2^7 - 2^10 - 2^30 - 2^32.

For the finite field F_p, the towers of extension field F_p^2, F_p^4, F_p^8, F_p^24 and F_p^48 are defined by indeterminates u, v, w, z, s as follows:¶

    F_p^2 = F_p[u] / (u^2 + 1)
    F_p^4 = F_p^2[v] / (v^2 + u + 1)
    F_p^8 = F_p^4[w] / (w^2 + v)
    F_p^24 = F_p^8[z] / (z^3 + w)
    F_p^48 = F_p^24[s] / (s^2 + z).

The elliptic curve E and its twisted curve E' are represented by E: y^2 = x^3 + 1 and E': y^2 = x^3 - 1 / w. A pairing e is defined by taking G_1 as a cyclic group of order r generated by a base point BP = (x, y) in F_p, G_2 as a cyclic group of order r generated by a based point BP' = (x', y') in F_p^8, and G_T as a subgroup of a multiplicative group (F_p^48)^* of order r. The size of p becomes 581-bit length. BLS48-581 is D-type.¶

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

• G_1 defined over E: y^2 = x^3 + b¶

  • p : a characteristic¶
  • r : a prime which divides an order of G_1¶
  • BP = (x, y) : a base point¶
  • h : a cofactor¶
  • b : a coefficient of E¶

• G_2 defined over E': y^2 = x^3 + b'¶

  • r' : an order¶

  • BP' = (x', y') : a base point (encoded with [I-D.ietf-lwig-curve-representations])¶

    • x' = x'_0 + x'_1 * u + x'_2 * v + x'_3 * u * v + x'_4 * w + x'_5 * u * w + x'_6 * v * w + x'_7 * u * v * w (x'_0, ..., x'_7 in F_p)¶
    • y' = y'_0 + y'_1 * u + y'_2 * v + y'_3 * u * v + y'_4 * w + y'_5 * u * w + y'_6 * v * w + y'_7 * u * v * w (y'_0, ..., y'_7 in F_p)¶
  • h' : a cofactor¶
  • b' : a coefficient of E'¶

p:

0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac3edc154e6565912b¶

r:

0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c01¶

x:

0x02af59b7ac340f2baf2b73df1e93f860de3f257e0e86868cf61abdbaedffb9f7544550546a9df6f9645847665d859236ebdbc57db368b11786cb74da5d3a1e6d8c3bce8732315af640¶

y:

0x0cefda44f6531f91f86b3a2d1fb398a488a553c9efeb8a52e991279dd41b720ef7bb7beffb98aee53e80f678584c3ef22f487f77c2876d1b2e35f37aef7b926b576dbb5de3e2587a70¶

x'_0:

0x05d615d9a7871e4a38237fa45a2775debabbefc70344dbccb7de64db3a2ef156c46ff79baad1a8c42281a63ca0612f400503004d80491f510317b79766322154dec34fd0b4ace8bfab¶

x'_1:

0x07c4973ece2258512069b0e86abc07e8b22bb6d980e1623e9526f6da12307f4e1c3943a00abfedf16214a76affa62504f0c3c7630d979630ffd75556a01afa143f1669b36676b47c57¶

x'_2:

0x01fccc70198f1334e1b2ea1853ad83bc73a8a6ca9ae237ca7a6d6957ccbab5ab6860161c1dbd19242ffae766f0d2a6d55f028cbdfbb879d5fea8ef4cded6b3f0b46488156ca55a3e6a¶

x'_3:

0x0be2218c25ceb6185c78d8012954d4bfe8f5985ac62f3e5821b7b92a393f8be0cc218a95f63e1c776e6ec143b1b279b9468c31c5257c200ca52310b8cb4e80bc3f09a7033cbb7feafe¶

x'_4:

0x038b91c600b35913a3c598e4caa9dd63007c675d0b1642b5675ff0e7c5805386699981f9e48199d5ac10b2ef492ae589274fad55fc1889aa80c65b5f746c9d4cbb739c3a1c53f8cce5¶

x'_5:

0x0c96c7797eb0738603f1311e4ecda088f7b8f35dcef0977a3d1a58677bb037418181df63835d28997eb57b40b9c0b15dd7595a9f177612f097fc7960910fce3370f2004d914a3c093a¶

x'_6:

0x0b9b7951c6061ee3f0197a498908aee660dea41b39d13852b6db908ba2c0b7a449cef11f293b13ced0fd0caa5efcf3432aad1cbe4324c22d63334b5b0e205c3354e41607e60750e057¶

x'_7:

0x0827d5c22fb2bdec5282624c4f4aaa2b1e5d7a9defaf47b5211cf741719728a7f9f8cfca93f29cff364a7190b7e2b0d4585479bd6aebf9fc44e56af2fc9e97c3f84e19da00fbc6ae34¶

y'_0:

0x00eb53356c375b5dfa497216452f3024b918b4238059a577e6f3b39ebfc435faab0906235afa27748d90f7336d8ae5163c1599abf77eea6d659045012ab12c0ff323edd3fe4d2d7971¶

y'_1:

0x0284dc75979e0ff144da6531815fcadc2b75a422ba325e6fba01d72964732fcbf3afb096b243b1f192c5c3d1892ab24e1dd212fa097d760e2e588b423525ffc7b111471db936cd5665¶

y'_2:

0x0b36a201dd008523e421efb70367669ef2c2fc5030216d5b119d3a480d370514475f7d5c99d0e90411515536ca3295e5e2f0c1d35d51a652269cbc7c46fc3b8fde68332a526a2a8474¶

y'_3:

0x0aec25a4621edc0688223fbbd478762b1c2cded3360dcee23dd8b0e710e122d2742c89b224333fa40dced2817742770ba10d67bda503ee5e578fb3d8b8a1e5337316213da92841589d¶

y'_4:

0x0d209d5a223a9c46916503fa5a88325a2554dc541b43dd93b5a959805f1129857ed85c77fa238cdce8a1e2ca4e512b64f59f430135945d137b08857fdddfcf7a43f47831f982e50137¶

y'_5:

0x07d0d03745736b7a513d339d5ad537b90421ad66eb16722b589d82e2055ab7504fa83420e8c270841f6824f47c180d139e3aafc198caa72b679da59ed8226cf3a594eedc58cf90bee4¶

y'_6:

0x0896767811be65ea25c2d05dfdd17af8a006f364fc0841b064155f14e4c819a6df98f425ae3a2864f22c1fab8c74b2618b5bb40fa639f53dccc9e884017d9aa62b3d41faeafeb23986¶

y'_7:

0x035e2524ff89029d393a5c07e84f981b5e068f1406be8e50c87549b6ef8eca9a9533a3f8e69c31e97e1ad0333ec719205417300d8c4ab33f748e5ac66e84069c55d667ffcb732718b6¶

h:

0x85555841aaaec4ac¶

b:

1¶

r':

0x2386f8a925e2885e233a9ccc1615c0d6c635387a3f0b3cbe003fad6bc972c2e6e741969d34c4c92016a85c7cd0562303c4ccbe599467c24da118a5fe6fcd671c01¶

h':

0x170e915cb0a6b7406b8d94042317f811d6bc3fc6e211ada42e58ccfcb3ac076a7e4499d700a0c23dc4b0c078f92def8c87b7fe63e1eea270db353a4ef4d38b5998ad8f0d042ea24c8f02be1c0c83992fe5d7725227bb27123a949e0876c0a8ce0a67326db0e955dcb791b867f31d6bfa62fbdd5f44a00504df04e186fae033f1eb43c1b1a08b6e086eff03c8fee9ebdd1e191a8a4b0466c90b389987de5637d5dd13dab33196bd2e5afa6cd19cf0fc3fc7db7ece1f3fac742626b1b02fcee04043b2ea96492f6afa51739597c54bb78aa6b0b99319fef9d09f768831018ee6564c68d054c62f2e0b4549426fec24ab26957a669dba2a2b6945ce40c9aec6afdeda16c79e15546cd7771fa544d5364236690ea06832679562a68731420ae52d0d35a90b8d10b688e31b6aee45f45b7a5083c71732105852decc888f64839a4de33b99521f0984a418d20fc7b0609530e454f0696fa2a8075ac01cc8ae3869e8d0fe1f3788ffac4c01aa2720e431da333c83d9663bfb1fb7a1a7b90528482c6be7892299030bb51a51dc7e91e9156874416bf4c26f1ea7ec578058563960ef92bbbb8632d3a1b695f954af10e9a78e40acffc13b06540aae9da5287fc4429485d44e6289d8c0d6a3eb2ece35012452751839fb48bc14b515478e2ff412d930ac20307561f3a5c998e6bcbfebd97effc6433033a2361bfcdc4fc74ad379a16c6dea49c209b1¶

b':

-1 / w¶

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

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

The following algorithm shows the computation of optimal Ate pairing over Barreto-Naehrig 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 to c, and an order r as input, and outputs e(P, Q).¶

    f := 1; T := Q;
    if (c_L = -1)
        T := -T;
    end if
    for i = 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;

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

Let c = t for a parameter t and c_0, c_1, ... , c_L in {-1,0,1} such that the sum of c_i * 2^i (i = 0, 1, ..., L) equals to 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;