# A short-list of pairing-friendly curves resistant to the Special TNFS algorithm at the 192-bit security level

Diego F. Aranha, Georgios Fotiadis, Aurore Guillevic

► To cite this version:

Diego F. Aranha, Georgios Fotiadis, Aurore Guillevic. A short-list of pairing-friendly curves resistant to the Special TNFS algorithm at the 192-bit security level. IACR Communications in Cryptology, 2024, 1 (3), pp.44. 10.62056/angyl86bm . hal-04666521v2

HAL Id: hal-04666521

https://inria.hal.science/hal-04666521v2

Submitted on 3 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A short-list of pairing-friendly curves resistant to the Special TNFS algorithm at the 192-bit security level

Diego F. Aranha¹ Ⓔ, Georgios Fotiadis² Ⓔ and Aurore Guillevic¹,³,⁴ Ⓔ

¹ Aarhus University, Aarhus, Denmark

² Université du Luxembourg, Esch-sur-Alzette, Luxembourg

³ Université de Lorraine, CNRS, Inria, LORIA, Nancy, France

⁴ Univ Rennes, Inria, CNRS, IRISA, Rennes, France

**Abstract.** For more than two decades, pairings have been a fundamental tool for designing elegant cryptosystems, varying from digital signature schemes to more complex privacy-preserving constructions. However, the advancement of quantum computing threatens to undermine public-key cryptography. Concretely, it is widely accepted that a future large-scale quantum computer would be capable to break any public-key cryptosystem used today, rendering today's public-key cryptography obsolete and mandating the transition to quantum-safe cryptographic solutions. This necessity is enforced by numerous recognized government bodies around the world, including NIST which initiated the first open competition in standardizing post-quantum (PQ) cryptographic schemes, focusing primarily on digital signatures and key encapsulation/public-key encryption schemes. Despite the current efforts in standardizing PQ primitives, the landscape of complex, privacy-preserving cryptographic protocols, e.g., zkSNARKs/zkSTARKs, is at an early stage. Existing solutions suffer from various disadvantages in terms of efficiency and compactness and in addition, they need to undergo the required scrutiny to gain the necessary trust in the academic and industrial domains. Therefore, it is believed that the migration to purely quantum-safe cryptography would require an intermediate step where current classically secure protocols and quantum-safe solutions will co-exist. This is enforced by the report of the Commercial National Security Algorithm Suite version 2.0, mandating transition to quantum-safe cryptographic algorithms by 2033 and suggesting to incorporate ECC at 192-bit security in the meantime. To this end, the present paper aims at providing a comprehensive study on pairings at 192-bit security level. We start with an exhaustive review in the literature to search for all possible recommendations of such pairing constructions, from which we extract the most promising candidates in terms of efficiency and security, with respect to the advanced Special TNFS attacks. Our analysis is focused, not only on the pairing computation itself, but on additional operations that are relevant in pairing-based applications, such as hashing to pairing groups, cofactor clearing and subgroup membership testing. We implement all functionalities of the most promising candidates within the RELIC cryptographic toolkit in order to identify the most efficient pairing implementation at 192-bit security and provide extensive experimental results.

**Keywords:** pairing-friendly curves · SNARK · TNFS

<figure><img src="image_2.png" /></figure>

<footnote>E-mail: dfaranha@cs.au.dk (Diego F. Aranha), georgios.fotiadis@uni.lu (Georgios Fotiadis), aurore.guillevic@inria.fr (Aurore Guillevic)</footnote>
# 1 Introduction

Pairings have been used as a black-box tool in the cryptographic landscape since the first constructive applications have been proposed in 2000 and 2001. Some of the early applications were identity-based encryption [BF01], short signatures [BLS01], and tri-partite Diffie-Hellman key exchange [Jou04]. In the following decades, pairings increased in popularity following the explosion in research within the broad area of cryptographic computing, consisting in essential building blocks to modern digital signatures [PS16, TZ23], commitment schemes [KZG10], anonymous credentials [CL04], and zero-knowledge proof systems such as zkSNARKs [Gro16].

Since the practical constructions of cryptographic pairings over elliptic curves are not secure against quantum-computers, an active research area is developing quantum-safe alternatives for pairing-based cryptography. However, migrating to quantum-safe cryptography has disadvantages in terms of efficiency and compactness, and potentially loss of some functionality. Taking for example zkSNARKs, there are promising quantum-safe constructions, such as zkSTARKs [BBHR18] and LaBRADOR [BS23], but they may offer larger proof sizes and/or prover/verification times that are still linear in the size of the witness or statement. Despite the exciting work in progress to develop alternatives, such performance penalties can be prohibitive for many applications.

In this paper, we follow a nuanced approach and argue that practical applications of pairing-based cryptography will need more conservative parameter choices while quantum-safe alternatives are further developed. In order to offer security in the next decade, we envision that parameters at the 192- and 256-bit security level will be needed. For reference, the Commercial National Security Algorithm Suite version 2.0 mandates transition to quantum-safe algorithms by 2033, and establishes that elliptic curve cryptography (ECC) at the 192-bit security level should be used before transition, effectively deprecating ECC at 128-bit security. The rationale behind the latter decision is rather unclear and unlikely to be ever properly substantiated, but there are speculations around computing elliptic curve discrete logs in cube-root time [KM16], without as much storage cost as publicly-known algorithms [BL13].

## 1.1 Motivation

Concretely, pairings are bilinear maps that are instantiated on algebraic curves. Contrary to other domains of cryptography where the choice of parameters is limited, straightforward, and standardized, the picture is more elaborated with pairings. Genus two pairings do not offer any advantage compared to elliptic curve (genus one) pairings in terms of security, while at the same time the Jacobian arithmetic is by far more costly compared to elliptic curve point addition. Instances of efficient and secure pairings on genus two curves have been recently reported in [AFK24], however they are still less efficient than the well-known elliptic curve pairings. For genus one, Barreto-Naehrig (BN) curves over large characteristic fields [BN06] became the dominant choice at 128-bit security for many years, followed by Barreto-Lynn-Scott (BLS) curves with embedding degree 12 at the 192-bit level [AFK+13]. Supersingular curves over small-characteristic fields were also considered for smaller devices, but efficient algorithms and record computations for discrete logarithms over extension fields completely eliminated their viability.<fnref n="1" /> These attacks do not apply in large characteristic, but the Kim-Barbulescu variant of the TNFS attack [KB16] still forced larger parameters, and the widely deployed BN-254/256 curves became outdated. Current deployments of pairing-based schemes are tailored to the updated 128-bit security level, and practical deployments have employed the BLS12-381 elliptic curve designed by the ZCash project [Bow17].

<footnote n="1">¹In 2012 happened the first large record computation of discrete logarithm computation https://dldb.loria.fr in GF(3<sup>6·97</sup>) (923 bits), and a final milestone in 2019 with GF(2<sup>30750</sup>) [HSST12, GKL+21].</footnote>
Scaling the security of pairing-friendly curves under the new constraints is challenging. Some previously obvious choices became undefined: alternative curves are not of prime order, contrary to BN curves, or might not have $j$-invariant 0 like BN curves. While the choice of parameters at the 256-bit security level seems to be clearer [KIK$^+$17, BMDFAF19], the story is more complicated for the 192-bit security level due to a broader range of candidate parameters. Hence, we focus our efforts exactly on finding and benchmarking parameter choices at 192-bit security, providing a detailed overview in terms of security and efficiency. We discuss which curves to choose, together with precise security estimates; and performance in terms of the cost of pairing computation and group operations including hashing, membership testing, scalar multiplication and exponentiation. There has been a long and dense bibliography on pairing implementation, from designing new curves (see the survey article [FST10]) to dedicated hardware optimizations, which we extend with a study dedicated to the 192-bit security level. As a motivating concrete example, we point out to the Polymath zkSNARK [Lip24], which considers 192-bit security as important for future applications and raises the need for zkSNARK-friendly curves.

## 1.2 Our Contributions

We review pairing-friendly curves at the 192-bit security level and provide TNFS-secure short-listed curves according to popular criteria. Some pre-selected curves were sketched in [Gui20, §5]. We also consider Scott–Guillevic (SG), Fotiadis–Martindale (FM), and Gasnier–Guillevic (GG) curves [SG18, FM19, GG23]. Because the *search space* of pairing-friendly curve families is too large for a complete survey, we restrict the evaluated curves w.r.t. the following a-priori criteria:

* Embedding degrees from 15 to 28. We justify this choice in Section 2.5.

* Curves with high degree twists: **quartic twist**: $4 | k$ and $j(E) = 1728$ ($k = 16, 20, 28$), **sextic twist**: $6 | k$ and $j(E) = 0$ ($k = 18, 24$), and also **cubic twist**: $3 | k$ odd and $j(E) = 0$ ($k = 15, 21, 27$).

* Variable $\rho$-value from the lowest possible according to [FST10], to $\rho = 2$ thanks to [FK19, FM19]. We observe that at fixed $k$, a larger $\rho$ can provide better performance.

We provide a full comparison of curves in terms of pairing efficiency, and $G_1, G_2$, and $G_T$ group operations:

* Formulas for optimal ate pairing, fast $G_1, G_2, G_T$ cofactor clearing and subgroup membership testing.

* Formulas for hashing into $G_1, G_2$ with SwiftEC [CSRT22] and Koshelev's generalization [Kos24]. A side-contribution is an implementation-friendly description of hashing, potentially impacting other parameters for 128-bit security (e.g. embedding degree 8 curves [GMT20]).

* SageMath and Magma prototype code. Automated estimated cost in terms of multiplications in the base field GF($p$).

* An optimized implementation within the RELIC library, and benchmarks of pairings and group operations for the most promising curves according to the SageMath estimates.

In summary, our evaluation supports the choice of BLS24-509 as the most efficient curve in general at the 192-bit security level. Our parameter search further unveiled the new family AFG16 of pairing-friendly curves with embedding degree 16, and two new curves within the BLS24 family which are especially suitable for SNARK applications.
# 2 Preliminaries

**Notations.** Denote $E$ an ordinary elliptic curve defined over a prime field $\mathbb{F}_p$. Denote $k$ the embedding degree such that the pairing embeds a pair of points of $E(\mathbb{F}_p)$ and $E(\mathbb{F}_{p^k})$ onto $\mathbb{F}_{p^k}^*$. The three pairing groups of prime order $r$ are denoted as usual $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$.

## 2.1 Pairings

The state-of-the-art implementations of pairings at 128-bit security are for the optimal ate pairing on different types of curves. Below we recall the definition of the optimal ate pairing and the formula to compute the Miller loop. For more information on this pairing type we refer to Vercauteren's paper [Ver10]. Furthermore, we give a brief description of the final exponentiation. For a complete introduction on pairings we refer to Costello's guide Pairings for beginners [Cos12].

**Optimal ate pairing Miller loop.** This is defined as the bilinear, non-degenerate and efficiently computable map $e: \mathbb{G}_2 \times \mathbb{G}_1 \to \mathbb{G}_T$, with $\mathbb{G}_1 = E[r] \cap \ker(\pi_p - [1])$ and $\mathbb{G}_2 = E[r] \cap \ker(\pi_p - [p])$, where $\pi_p: E \to E$ is the $p^{th}$-power Frobenius endomorphism.

Let $L$ be the following $\varphi(k)$-dimensional lattice, spanned by the rows:

$$L = \begin{pmatrix}
r & 0 & 0 & \dots & 0 \\
-p & 1 & 0 & \dots & 0 \\
-p^2 & 0 & 1 & \dots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
-p^{\varphi(k)-1} & 0 & 0 & \dots & 1
\end{pmatrix}$$

and let $v = (c_0, c_1, \dots, c_{\varphi(k)-1})$ be the shortest vector of the lattice $L$. Then the coordinates of the shortest vector $v$ satisfy the following relation:

$$\sum_{i=0}^{\varphi(k)-1} c_i p^i \equiv 0 \mod r, \qquad (1)$$

where the coordinates $c_i$ are functions of the seed $u$, used to instantiate the polynomials $(p(x), t(x), r(x))$. Based on this setup, the formula for computing the optimal ate pairing is [Ver10]:

$$(Q, P) \to \left[ \prod_{i=0}^{\varphi(k)-1} f_{c_i, Q}^{p^i}(P) \cdot \prod_{i=0}^{\varphi(k)-2} \frac{\ell_{R_i, S_i}(P)}{v_{R_i+S_i}(P)} \right],$$

where $R_i = [s_{i+1}]Q, S_i = [c_i p^i]Q$ and the scalars $s_i$ are defined as:

$$s_i = \sum_{j=i}^{\varphi(k)-1} c_j p^j,$$

for every $i = 0, \dots, \varphi(k) - 2$. In addition, $\ell_{R_i, S_i}(P)$ denotes the line passing through the points $R_i$ and $S_i$, which is evaluated at $P$, and $v_{R_i+S_i}(P)$ is the vertical line through the point $R_i + S_i$, evaluated at $P$.

The optimal ate pairing formula can be simplified using certain properties of the Miller loop. In particular:

* For every $c_i < 0$, we have:

$$f_{c_i, Q}(P) = \frac{1}{f_{-c_i, Q}(P) \cdot v_{[c_i]Q}(P)}.$$
* By [BKLS02, Theorem 2] the following holds:

$$f_{a+b,Q}(P) = f_{a,Q}(P) \cdot f_{b,Q}(P) \cdot \frac{\ell_{[a]Q, [b]Q}(P)}{v_{[a+b]Q}(P)}$$

* By [ALH10, Lemma 1] the following relation holds:

$$f_{ab,Q}(P) = f_{b,Q}(P)^a \cdot f_{a,[b]Q}(P) = f_{a,Q}(P)^b \cdot f_{b,[a]Q}(P).$$

* We have: $f_{0,Q}(P) = f_{1,Q}(P) = f_{-1,Q}(P) = 1$.

* Every scalar multiplication $[p^i]Q$ can be efficiently computed by applying the $p^i$-power Frobenius endomorphism $\pi_i: E \to E$. Therefore we write $[p^i]Q = \pi_i(Q)$, for every $i = 1, \dots, \varphi(k) - 1$.

**Final exponentiation.** The final exponentiation is the process of raising an element in $\mathbb{F}_{p^k}^*$ to the exponent $e = (p^k - 1)/r$. When working with pairing groups, this is accomplished by factoring $e$ as follows:

$$e = \frac{p^k - 1}{\Phi_k(p)} \cdot \frac{\Phi_k(p)}{r},$$

where we refer to $e_{\text{easy}} = (p^k - 1)/\Phi_k(p)$ as the *easy part* and $e_{\text{hard}} = \Phi_k(p)/r$ as the *hard part*. Both parts can be significantly simplified, depending on whether the embedding degree $k$ is even, composite odd, or prime. The formulas for computing the easy part of the final exponentiation is the same for all pairing-friendly elliptic curves with the same embedding degree. On the contrary, the formulas for computing the hard part of the final exponentiation is different for each family of curves. There are different methods for simplifying the hard part, which we explore in Section 3.

## 2.2 Constructing pairing-friendly curves and families

Plain ordinary elliptic curves are not pairing-friendly, in particular, their embedding degree $k$ has the magnitude of $r$ so the pairing is impracticable. Pairing-friendly curves should be designed specifically and there have been a long series of papers revealing new curves. The first ordinary curves were MNT ($k = 3, 4, 6$), followed by BLS, Brezing-Weng, the popular BN curves, and the KSS curves [MNT01, BLS03, BW05, BN06, KSS08]. Freeman, Scott and Teske delivered a useful taxonomy [FST10]. The recent works are a generalization of the BN construction [SG18] and the KSS construction [GG23] though without finding new prime-order curves. With the deployment of SNARKs and the need of cycles of prime-order pairing-friendly curves, impossibility results are also investigated [BMUS23, CCW19]. We also mention a very recent work on higher genus cycle constructions for SNARK [CRSCN24]. In this work we concentrate on complete families, parameterized by polynomials and of fixed small discriminant.

## 2.3 Pairings at 128-bit security

### 2.3.1 Assessing the TNFS-security level of pairing-friendly curves.

In 2016 the Kim-Barbulescu attack downgraded the security level of many pairing-friendly curves [KB16, KJ17], in particular the curves with composite embedding degree such as 12, 16, 18, 24. Because choosing $k = 2^i3^j$ allows an implementation-friendly towering and efficient field arithmetic, such choices are very common. Menezes, Sarkar, and Singh [MSS16] were the first to generate TNFS-secure parameters, recommending BLS12 curves of about 384 bits. Since then, the curve BLS12-381 has replaced BN curves almost everywhere. We
can mention the standardization effort about pairing-friendly curves [SKSW22], [BGW+22] on BLS signatures, [TL23] on BLS-curve-based key representation. Apart from BLS12, there are other specific proposals in other contexts [GMT20, FK19, FM19, Fot21, CDS20].

Analyzing TNFS is a challenging task. Barbulescu and Duquesne made recommendations in a worst-case scenario with a powerful attacker [BD19] (with conjectured hypotheses in the polynomial selection step of the TNFS algorithm). Guillevic and Singh [GS21] refined the TNFS analysis with the computation of the estimator *alpha*, and released an implementation of the simulator. There are very few record computations with TNFS. To the best of our knowledge, we are aware of Robinson's work in GF(*p*⁴) [Rob22] and De Micheli, Gaudry and Pierrot in GF(*p*⁶) [DGP21].

In parallel of a better understanding of the TNFS algorithm, new parameter sets are proposed [Gui20, CDS20]. A short-list at the 128-bit security level [Gui20] was published in 2020, it gave hints on possible curves at the 192-bit security level but missed the shortest $G_1$ constraint [CDS20] and lacked BLS24 at the 128-bit security level. More recently there is Guillevic's blog post [Gui21].

Better pairing implementations continue to be an active area of research, with the long-term software development in RELIC [AGM+] (see for example [APR21] for recent benchmarks) but also newer projects in Golang or Rust for SNARKs (see the survey [AHG23]). Latest improvements about pairing computations include a faster final exponentiation for all BLS curves [HHT20] thanks to a decomposition pattern, and for KSS18 curves [CHZ22]; implementation of pairings and group operations on prime-embedding-degree pairing-friendly curves BW13-310 and BW19-286 (with endomorphisms but without twists) [DZZ23a, DZZ23b, FAGA23, DZZZ21] (Yu Dai's repository at [Dai23]); cofactor clearing and subgroup membership testing on pairing-friendly curves [HGP22, DLZZ23]; pairings in arithmetic circuits in the context of SNARKs [Hou23].

The recommendations at the 128-bit security level are the following [Gui21]. For a **prime-order curve** e.g. for a hybrid cycle in the SNARK context, pick a BN curve of 384-448 bits (Freeman and MNT curves are also possible but less efficient). For the **fastest pairing**, choose a BLS12 curve of 384-448 bits. For **smallest $G_1$**, set a BLS24 curve of ≈320 bits, for even smaller $G_1$, BW13-P310, BW19-P286 or BLS48-286, SG54-283. Finally for **small embedding degree $k$**, there are curves with $k=1$, supersingular curves with $k=2$, and modified Cocks-Pinch curves with $5 \le k \le 8$.

The papers [KIK+17, BMDFAF19] consider the 256-bit security level with embedding degrees up to 48 (BLS48-581) and 54 (SG54-569). While [BD19] recommends a KSS18-1484 or a BLS24-1032 curve, [BEG19] expects a BLS27-559 curve (however this looks undersized). We collected the data in Appendix C, Table 23.

## 2.4 Previous work on 192-bit security

The situation at the 192-bit security level is unclear, for at least two reasons. First there are more parameters to tune in TNFS for higher extension degrees. Second, there are more curve families to investigate (the embedding degree range to consider is larger for example). A nice short-list of best curves at the 192-bit security level is missing. Not only pairing computation but operations in $G_1, G_2, G_T$ are important and need to be assessed. The size of $G_1$ and $G_2$ is an important criterion in certain use cases. Barbulescu and Duquesne focused on KSS18 and BLS24 (see Table 1). In 2019, Barbulescu, El Mrabet and Ghammam posted a preliminary report on many curves [BEG19]. Guillevic and Singh [GS21] and Guillevic [Gui20] proposed seeds and keysizes at the 192-bit security level for some families of curves (Tables 2 and 3). We aim at consolidating the knowledge for pairing-friendly curves at the 192-bit security level.
<table><caption>**Table 1:** Curves at the 192-bit security level from [BD19, Table 9, §7.6].</caption><thead><tr><th>k</th><th>Curve</th><th>NFS variant</th><th>seed</th><th>p<br>(bits)</th><th>p<sup>k</sup><br>(bits)</th><th>security<br>F<sub>p<sup>k</sup></sub><br>(bits)</th></tr></thead><tbody><tr><td>18</td><td>KSS</td><td>STNFS</td><td>85 bits</td><td>678</td><td>12200</td><td>192</td></tr><tr><td>24</td><td>BLS</td><td>STNFS</td><td>56 bits</td><td>555</td><td>13300</td><td>192</td></tr><tr><td>18</td><td>KSS</td><td>STNFS κ = 1</td><td>u = -2<sup>85</sup> - 2<sup>31</sup> - 2<sup>26</sup> + 2<sup>6</sup></td><td>676</td><td>12168</td><td>204</td></tr><tr><td>24</td><td>BLS</td><td>STNFS κ = 1</td><td>u = -2<sup>56</sup> - 2<sup>43</sup> + 2<sup>9</sup> - 2<sup>6</sup></td><td>559</td><td>13416</td><td>204</td></tr></tbody></table>

<table><caption>**Table 2:** Curves at the 192-bit security level from [Gui20, Table 10, §5].</caption><thead><tr><th>k</th><th>Curve</th><th>seed<br>(bits)</th><th>r<br>(bits)</th><th>p<br>(bits)</th><th>p<sup>k</sup><br>(bits)</th><th>security<br>F<sub>p<sup>k</sup></sub><br>(bits)</th></tr></thead><tbody><tr><td>14</td><td>FST 6.3</td><td>52</td><td>620</td><td>928</td><td>12979-12992</td><td>194</td></tr><tr><td>15</td><td>BLS</td><td>78</td><td>620</td><td>928</td><td>13906-13920</td><td>193</td></tr><tr><td>20</td><td>FST 6.4</td><td>56</td><td>448</td><td>670</td><td>13371-13400</td><td>192</td></tr><tr><td>21</td><td>BLS</td><td>32</td><td>384</td><td>511</td><td>10691-10719</td><td>195</td></tr><tr><td>27</td><td>BLS</td><td>22</td><td>384</td><td>427</td><td>11496-11524</td><td>212</td></tr><tr><td>28</td><td>FST 6.4</td><td>32</td><td>384</td><td>510</td><td>14243-14280</td><td>208</td></tr></tbody></table>

## 2.5 Justification of our a priori criteria

We listed in Section 1.2 our a priori criteria to restrict the considered curves. First we set boundaries on the embedding degree: $15 \le k \le 28$. The earlier work stated large bounds [Gui20, Eq. (8)]: $7168 \le 384\rho k \le 14336$. Because we target high degree twist curves, the embedding degree $k$ is always composite. Kim-Barbulescu extended TNFS applies well and we rather set

$$10000 \le 384\rho k \le 14336.$$

we scan the curve families of the taxonomy paper plus the newer ones listed in 1.2 (Fotiadis-Martindale, Scott-Guillevic) and obtain these bounds. We provide a SageMath script to reproduce this result. For RSA keysizes at the 192-bit security level, a modulus of 7680 bits is required according to NIST, while Lenstra Updated corresponds to 12548 bits<fnref n="2" />. For $k = 15$, the work [Gui20] already considered BLS15 and stated that $p$ of 928 bits offers 192 bits of security. Such $p$ is very large and we do not include it in our analysis. However we can take $k = 15$ and $\rho = 2$ as in [FK19]. The parameters are $p$ of 768 bits, $r$ of 384 bits and the security level is about 192 bits, for $p^k$ of about 11520 bits. the paper [Gui20] already established that there is no curve family whose embedding degree is larger than 28 but whose $\rho$-value is small enough to satisfy $384\rho k \le 14336$, hence $k \le 28$.

<table><caption>**Table 3:** Seeds at the 192-bit security level from [GS21, Tables 3, 4, 7].</caption><thead><tr><th>k</th><th>Curve</th><th>r<br>(bits)</th><th>p<br>(bits)</th><th>p<sup>k</sup><br>(bits)</th><th>seed</th><th>security<br>F<sub>p<sup>k</sup></sub><br>(bits)</th></tr></thead><tbody><tr><td>12</td><td>BN</td><td>1022</td><td>1022</td><td>12255</td><td>-2<sup>254</sup> + 2<sup>33</sup> + 2<sup>6</sup></td><td>191</td></tr><tr><td>12</td><td>BLS12</td><td>768</td><td>1150</td><td>13799</td><td>-2<sup>192</sup> + 2<sup>188</sup> - 2<sup>115</sup> - 2<sup>110</sup> - 2<sup>44</sup> - 1</td><td>193</td></tr><tr><td>16</td><td>KSS16</td><td>605</td><td>766</td><td>12255</td><td>2<sup>78</sup> - 2<sup>76</sup> - 2<sup>28</sup> + 2<sup>14</sup> + 2<sup>7</sup> + 1</td><td>194</td></tr><tr><td>18</td><td>KSS18</td><td>474</td><td>638</td><td>11477</td><td>2<sup>80</sup> + 2<sup>77</sup> + 2<sup>76</sup> - 2<sup>61</sup> - 2<sup>53</sup> - 2<sup>14</sup></td><td>193</td></tr><tr><td>24</td><td>BLS24</td><td>409</td><td>509</td><td>12202</td><td>-2<sup>51</sup> - 2<sup>28</sup> + 2<sup>11</sup> - 1 [CLN11]</td><td>193</td></tr></tbody></table>

<footnote n="2">²https://www.keylength.com/en/compare/</footnote>
## 2.6 Security Analysis: TNFS and its variants

In [BD19], Barbulescu and Duquesne further investigated the consequences of the extended Tower NFS algorithm of Kim and Barbulescu [KB16], after a first analysis in [MSS16]. In particular, they simulated worst-case scenarii from a cryptographer perspective to obtain key-size recommendations. We recall their formula [BD19, Eq. (2)]:

$$ 
\begin{aligned}
\text{cost} &= c_{\text{sieve}} \frac{1}{A} \frac{\text{\# required relations}}{\text{smoothness probability}} + c_{\text{lin. algebra}} c_{\text{density}} \frac{\text{\# required relations}}{A \cdot \text{filtering ratio}} \\
&= \frac{2B}{A \log B} \rho_D \left( \frac{\text{avg log}_2 N_f}{\log_2 B} \right)^{-1} \rho_D \left( \frac{\text{avg log}_2 N_g}{\log_2 B} \right)^{-1} + \frac{1}{4} 2^7 \left( \frac{2B}{A \log B \log_2 B} \right)^2
\end{aligned}
$$

where $\rho_D$ is Dickman's $\rho$ function. Inside the relation collection model of cost, [BD19] assumes that the duplicates due to the roots of unity can be avoided for free in the relation collection, hence a number of obtained relations in a sieving space of dimension $2 \deg h$ and samples whose coefficients are bounded by $A$ of

$$ \frac{(2A + 1)^{2 \deg h}}{2w} \rho_D \left( \frac{\text{avg log}_2 N_f}{\log_2 B} \right) \rho_D \left( \frac{\text{avg log}_2 N_g}{\log_2 B} \right) \geq \frac{2B}{\log B}. $$

Guillevic and Singh propose a slightly different model of cost in [GS21] where they evaluate the smoothness bias of the norms in TNFS. For that they need practical curve parameters and polynomials. Their experiments are given as a SageMath implementation. One requires

$$ \frac{(2A + 1)^{2 \deg h}}{2w} \frac{1}{\zeta_{K_h}(2)} \text{avg} \rho_D \left( \frac{\log N_f + \alpha(f, h)}{\log B} \right) \rho_D \left( \frac{\log N_g + \alpha(g, h)}{\log B} \right) \geq 2 \text{LogIntegral}(B) $$

and

$$ \text{cost} = \frac{(2A + 1)^{2 \deg h}}{2A} c_{\text{sieve}} + c_{\text{linalg}} c_{\text{density}} \left( \frac{2 \text{LogIntegral}(B)}{c_{\text{filter}}} \right)^2 $$

We summarize in Table 2.6 the different choices. In [GS21], the cost of linear algebra is modeled as the number of 64-bit machine words of $\ell$: $\lceil \log_2 \ell/64 \rceil$ times the weight per row, times the matrix size squared.

<table><caption>**Table 4:** Choices of parameters in [BD19, GS21].</caption><thead><tr><th></th><th>parameter</th><th>Barbulescu-Duquesne</th><th>Guillevic-Singh</th></tr></thead><tbody><tr><td>c<sub>sieve</sub></td><td>cost of sieving, per relation</td><td>1</td><td>log log B</td></tr><tr><td>c<sub>linalg</sub></td><td>factor of lin. algebra</td><td>1/4</td><td>[log<sub>2</sub> ℓ/64]</td></tr><tr><td>c<sub>filter</sub></td><td>filtering factor</td><td>log<sub>2</sub> B</td><td>20</td></tr><tr><td>c<sub>density</sub></td><td>matrix' weight per row</td><td>128</td><td>200</td></tr><tr><td>A</td><td>automorphisms</td><td>k / gcd(deg h, k / deg h)</td><td>aut(h) aut(f, g)</td></tr></tbody></table>

We incorporated the assumptions of [BD19] in the SageMath simulator of [GS21] so that we can give the two estimates with the same simulation tool.

# 3 Pairings at 192-bit security

## 3.1 Selection of pairing-friendly curves

Our selection of pairing-friendly curves for 192-bit security follows the same strategy as the case of 128-bit security (e.g., see the recent study in [Gui20]). More concretely, the choice of elliptic curves that will be included in our analysis is based on the following criteria:
C1. Use elliptic curves that admit high degree twists $d \in \{3, 4, 6\}$.

C2. Focus on pairing-friendly elliptic curves with embedding degree $15 \le k \le 28$.

C3. The selected curves should be TNFS-resistant.

C4. Consider pairing-friendly curves with $\rho = \log p / \log r$ up to 2.

C5. Apply and implement the optimal ate pairing.

C6. Identify efficient candidate curves, based on additional pairing-related operations, beyond the pairing computation itself.

We choose to implement the optimal ate pairing for our selected curves, since the state-of-the-art for 128-bit security suggests that this is the most efficient pairing type. The curves that we consider admit high degree twists i.e., they have $j$-invariant $1728$ ($4 | k$) or $j$-invariant $0$ ($3$ or $6 | k$). The use of high-degree twists is crucial for ensuring fast optimal ate pairing instances [CLN10]. We note that extending the fastest curve options in 128-bit security (e.g., BLS12 and BN curves) to the 192-bit setting is not the optimal choice, since this would require the size of the base field prime $p$ to be larger than 1000 bits [Gui21]. The security of the selected curves should be evaluated taking into consideration the progress on the TNFS attacks targeting the DLP in extension fields of composite degree [KB16]. In particular, the security of our selected curves is evaluated using the STNFS software simulator<fnref n="3" /> of Guillevic and Singh [GS21].

Furthermore, although the initial requirement for pairing-friendly curves was to look for $\rho \approx 1$ [FST10], sometimes curves with larger $\rho$ can be beneficial. In particular, given a pairing-friendly family of curves with fixed and composite embedding degree $k$, increasing the size of the base field prime $p$ to counter the TNFS attacks results in the increase of the size of the prime $r$ defining the prime order subgroup of $E(\mathbb{F}_p)$ and hence an increase of the length of the Miller loop. Alternatively, one can choose a pairing-friendly family of curves for the same $k$ with larger $\rho$, so that the size of $p$ is increased without affecting the size of $r$. Therefore, in our study we include curves with $\rho$-value up to 2. Such curve instances at 192-bit security with $\rho = 2$ are studied in [FK19]. In addition, we point out that our results on optimal pairing-friendly curves for 192-bit security depend not only on the fast pairing implementation, but also on efficient exponentiation in the three pairing-groups $G_1, G_2, G_T$, hashing to $G_1, G_2$, cofactor clearing and subgroup membership testing in $G_1, G_2, G_T$. Hence, in our quest for the most efficient pairing candidates at 192-bit security, we include an analysis on the efficiency of these additional pairing functionalities.

Based on these criteria we identified the most promising candidate families of pairing-friendly elliptic curves in the literature which can result in efficient pairing-related operations at 192-bit security. In particular, we have concluded with the following families:

* Kachisa-Schaefer-Scott (KSS) [KSS08]. Families KSS16 and KSS18 for embedding degrees 16 and 18 respectively.

* Freeman-Scott-Teske (FST) [FST10]. We follow Construction 6.4 in [FST10] for families with $k = 20$ and $k = 28$ and we refer to these families as FST20 and FST28.

* Barreto-Lynn-Scott [BLS03]. Families BLS12, BLS15, BLS21, BLS24, BLS27, for embedding degrees 12, 15, 21, 24 and 27. Family BLS12 does not comply with the embedding degree selection criteria (C2). However, we include this family to justify our earlier claim that although BLS12 is the most efficient choice for 128-bit security, increasing the size of $p$ to reach 192-bit security is not the optimal strategy to follow. In addition, we include BLS15 to compare to FM15.

* Fotiadis-Martindale [FM19]. Families FM15, FM16, FM18 and FM20, for embedding degrees 15, 16, 18 and 20. These correspond to the families with number #21, #23, #25 and #27 in [FM19, Table 2]. We note that family FM20 coincides with FST20.

* Scott-Guillevic [SG18]. Families SG18 and SG20 for embedding degrees 18 and 20. These types of families are also known as Aurifeuillean and they are constructed

<footnote n="3">³Simulation tool in SageMath under MIT license: https://gitlab.inria.fr/tnfs-alpha/alpha</footnote>
<table><caption>**Table 5:** Curves of embedding degree 15 to 28 with a high degree twist $d \in \{3, 4, 6\}$ and such that the curve $E(\mathbb{F}_p)$ offers at least 192 bits of security. FM20 is the same as FST20. BLS12 security comes from [Gui20], KSS16, KSS18, BLS24 from [GS21].</caption><thead><tr><th>k</th><th>curve</th><th>seed</th><th>(a, b)</th><th>p<br>[k]</th><th>p<br>(bits)</th><th>r<br>(bits)</th><th>ρ</th><th>p<sup>k</sup><br>(bits)</th><th>security</th></tr></thead><tbody><tr><td>12</td><td>BLS12</td><td>-(2<sup>192</sup>-2<sup>188</sup>+2<sup>115</sup>+2<sup>110</sup>+2<sup>44</sup>+1)</td><td>(0, 1)</td><td>7</td><td>1150</td><td>768</td><td>1.50</td><td>13800</td><td>193</td></tr><tr><td>15</td><td>BLS15</td><td>2<sup>74</sup>+2<sup>73</sup>+2<sup>62</sup>+2<sup>59</sup>+2<sup>6</sup></td><td>(0, -2)</td><td>1</td><td>894</td><td>597</td><td>1.50</td><td>13410</td><td>190</td></tr><tr><td></td><td>FM15</td><td>2<sup>47</sup>+2<sup>46</sup>+2<sup>34</sup>+2<sup>14</sup>+2<sup>13</sup>+2<sup>11</sup></td><td>(0, 1)</td><td>1</td><td>762</td><td>381</td><td>2.00</td><td>11430</td><td>191</td></tr><tr><td>16</td><td>KSS16</td><td>2<sup>78</sup>-2<sup>76</sup>-2<sup>28</sup>+2<sup>14</sup>+2<sup>7</sup>+1</td><td>(1, 0)</td><td>13</td><td>766</td><td>605</td><td>1.25</td><td>12255</td><td>194</td></tr><tr><td></td><td>FM16</td><td>2<sup>48</sup>-2<sup>44</sup>-2<sup>38</sup>+2<sup>31</sup></td><td>(1, 0)</td><td>1</td><td>765</td><td>384</td><td>2.00</td><td>12232</td><td>196</td></tr><tr><td></td><td>AFG16</td><td>2<sup>48</sup>-2<sup>28</sup>-2<sup>25</sup>+2<sup>2</sup></td><td>(1, 0)</td><td>1</td><td>766</td><td>384</td><td>2.00</td><td>12256</td><td>196</td></tr><tr><td>18</td><td>KSS18</td><td>2<sup>80</sup>+2<sup>77</sup>+2<sup>76</sup>-2<sup>61</sup>-2<sup>53</sup>-2<sup>14</sup></td><td>(0, 6)</td><td>7</td><td>638</td><td>474</td><td>1.33</td><td>11477</td><td>193</td></tr><tr><td></td><td>SG18</td><td>-(2<sup>63</sup>+2<sup>54</sup>+2<sup>16</sup>)</td><td>(0, 15)</td><td>7</td><td>638</td><td>383</td><td>1.66</td><td>11484</td><td>187</td></tr><tr><td></td><td>SG18</td><td>2<sup>66</sup>+2<sup>60</sup>+2<sup>43</sup>+2<sup>3</sup></td><td>(0, 17)</td><td>1</td><td>669</td><td>401</td><td>1.66</td><td>12027</td><td>191</td></tr><tr><td></td><td>SG18</td><td>2<sup>70</sup>-2<sup>68</sup>-2<sup>54</sup>+2<sup>28</sup></td><td>(0, 23)</td><td>1</td><td>704</td><td>423</td><td>1.66</td><td>12668</td><td>194</td></tr><tr><td></td><td>FM18</td><td>-2<sup>64</sup>+2<sup>33</sup>+2<sup>30</sup>+2<sup>20</sup>+1</td><td>(0, 5)</td><td>7</td><td>768</td><td>384</td><td>2.00</td><td>13824</td><td>197</td></tr><tr><td>20</td><td>FM20</td><td>-2<sup>48</sup>+2<sup>22</sup>-2<sup>15</sup>-1</td><td>(29, 0)</td><td>1</td><td>574</td><td>384</td><td>1.50</td><td>11480</td><td>182</td></tr><tr><td></td><td>FM20</td><td>-2<sup>53</sup>-2<sup>49</sup>+2<sup>10</sup>+1</td><td>(1, 0)</td><td>1</td><td>636</td><td>425</td><td>1.50</td><td>12701</td><td>189</td></tr><tr><td></td><td>FM20</td><td>-2<sup>56</sup>+2<sup>44</sup>+1</td><td>(1, 0)</td><td>1</td><td>670</td><td>448</td><td>1.50</td><td>13400</td><td>193</td></tr><tr><td></td><td>SG20</td><td>-2<sup>47</sup>-2<sup>45</sup>+2<sup>15</sup>+2<sup>13</sup></td><td>(1, 0)</td><td>1</td><td>670</td><td>383</td><td>1.75</td><td>13391</td><td>203</td></tr><tr><td></td><td>GG20b</td><td>2<sup>49</sup>+2<sup>46</sup>-2<sup>41</sup>+2<sup>35</sup>+2<sup>30</sup>-1</td><td>(2, 0)</td><td>1</td><td>575</td><td>379</td><td>1.52</td><td>11499</td><td>196</td></tr><tr><td>24</td><td>BLS24</td><td>-2<sup>51</sup>-2<sup>28</sup>+2<sup>11</sup>-1</td><td>(0, 1)</td><td>19</td><td>509</td><td>409</td><td>1.25</td><td>12202</td><td>193</td></tr><tr><td></td><td>BLS24</td><td>-2<sup>51</sup>+2<sup>49</sup>+2<sup>44</sup>+2<sup>35</sup>+1</td><td>(0, 1)</td><td>1</td><td>505</td><td>405</td><td>1.25</td><td>12099</td><td>193</td></tr><tr><td></td><td>BLS24</td><td>2<sup>51</sup>+2<sup>44</sup>+2<sup>41</sup>-2<sup>37</sup>+1</td><td>(0, 1)</td><td>1</td><td>509</td><td>409</td><td>1.25</td><td>12205</td><td>193</td></tr><tr><td>21</td><td>BLS21</td><td>-2<sup>32</sup>+2<sup>25</sup>+2<sup>6</sup>+2</td><td>(0, 16)</td><td>1</td><td>511</td><td>384</td><td>1.33</td><td>10715</td><td>199</td></tr><tr><td>27</td><td>BLS27</td><td>-2<sup>21</sup>-2<sup>19</sup>-2<sup>15</sup>+2<sup>10</sup>+2<sup>4</sup>+2<sup>2</sup>+1</td><td>(0, 1)</td><td>19</td><td>426</td><td>383</td><td>1.11</td><td>11481</td><td>212</td></tr><tr><td></td><td>BLS27</td><td>2<sup>21</sup>+2<sup>19</sup>+2<sup>17</sup>-2<sup>11</sup>+2<sup>5</sup>-2<sup>3</sup></td><td>(0, -2)</td><td>7</td><td>427</td><td>384</td><td>1.11</td><td>11509</td><td>212</td></tr><tr><td>28</td><td>FST28</td><td>2<sup>32</sup>-2<sup>25</sup>+2<sup>22</sup>+2<sup>15</sup>+1</td><td>(1, 0)</td><td>1</td><td>510</td><td>384</td><td>1.33</td><td>14276</td><td>208</td></tr><tr><td></td><td>GG28</td><td>-2<sup>32</sup>-2<sup>28</sup>+2<sup>19</sup>+2<sup>9</sup>-2<sup>3</sup>-1</td><td>(9, 0)</td><td>1</td><td>500</td><td>381</td><td>1.31</td><td>13983</td><td>223</td></tr></tbody></table>

following the method of Scott and Guillevic [SG18].

* Gasnier–Guillevic [GG23]. Families GG20b and GG28 for $k = 20$ and $k = 28$. As mentioned in [GG23], although they don't improve the $\rho$-value compared to FST10 and FST28, they are more resistant to the TNFS attack.

FM15, FM16 and FM18 families have $\rho = 2$. In Section 3.4 we compare these families with others which have smaller $\rho$ for the same embedding degree. Furthermore, for completeness we also considered the case $k = 22$ and specifically the families of Freeman–Scott–Teske obtained by Constructions 6.3 and 6.4 (FST22 (6.3), FST22 (6.6)) and the family of Gasnier–Guillevic (GG22). Such examples of pairings do not follow the selection criterion (C1), since such elliptic curves have only quadratic twists, and they don't seem to be competitive to pairings on elliptic curves that admit high degree twists. However, because we already have SageMath implementations of these curves and in order to justify that indeed they are not competitive, we include these examples in Appendix A (see Table 19). As we were finalizing our paper, Lin, Zhao and Zheng posted [LZZ24] on ePrint, on implementing $k = 22$ $D = 7$ GG curves, investigating the strategy of super-optimal pairings [FAGA23]. In addition to the aforementioned families of pairing-friendly elliptic curves, we also include the following family for embedding degree 16 and $\rho = 2$ in our analysis.

**Family 1 (Aranha-Fotiadis-Guillevic (AFG16)).** The following polynomials $p(x), t(x), r(x) \in$
$Q[x]$, where:

$$p(x) = (x^{16} + 2x^{13} + x^{10} + 5x^8 + 6x^5 + x^2 + 4)/4$$

$$t(x) = r(x) + x^5 + 1 = x^8 + x^5 + 2$$

$$r(x) = \Phi_{16}(x) = x^8 + 1$$

define a polynomial family of pairing-friendly elliptic curves with embedding degree $k = 16$, CM discriminant $D = 1$ and $\rho = 2$. The order of the curve in parametric form is $\#E(\mathbb{F}_p) = h(x)r(x)$, where $h(x) = (x(x^3 + 1)/2)^2$. The family is integer-valued for all $u \in \mathbb{Z}$. The polynomial $r$ evaluated at integers of the form $2u$ is odd, and is even at integers of the form $2u + 1$, for $u \in \mathbb{Z}$. $\square$

The above family of elliptic curves is similar to the one proposed in [FK19, Table 5] for $k = 16$. The difference is that the cofactor $h(x)$ is a perfect square and $\sqrt{h(x)}$ divides $p(x) - 1$, hence the trick of Wahby and Boneh [WB19] for fast cofactor clearing applies. That is, in order to fix a point $P$ on the curve to have order $r$, one needs to multiply with the scalar $u(u^3 + 1)$ instead of $h(u)$, which can potentially be more efficient compared to other candidates of the same embedding degree. We refer to the new family as AFG16.

The seeds that we have chosen for instantiating these families are given in Table 5. We searched for seed with minimal Hamming weight, which would give curves with either $a = 0$ or $a = 1$ and $p \equiv 1 \pmod 3$ for fast hashing, and a nice towering of extensions with only small non-residues. For some families multiple seeds are reported, however we choose the ones highlighted in grey for our theoretical comparison, as well as for our benchmarking in Section 5. The resulting curves offer security level of at least 192-bit with respect to the TNFS attacks, except for the ones highlighted in red which offer slightly less. The seed $2^{48} + 2^{28} + 2^{26}$ for FM16 [FM19] does not give machine-word aligned parameters: $p$ is 767-bit long but $r$ is 385-bit long, this overflows the 384-bit standard size. We replace it with $2^{48} - 2^{44} - 2^{38} + 2^{31}$ which has heavier Hamming weight but whose $r$ fits in 384 bits. The seed $-(2^{64} + 2^{35} - 2^{11} + 1)$ for FM18 does not give machine-word aligned parameters, we replace it with $-2^{64} + 2^{33} + 2^{30} + 2^{20} + 1$. The seed for KSS16 from [GS21] (see Table 3) does not fulfill all criteria for fast hashing (see 4.2) and we replace it with a new one. For BLS24, we consider the seed given in [GS21] which dates back to [CLN11] and we give two new ones well-suited for SNARKs, with a high 2-valuation of $p - 1$ and $r - 1$. Curve parameters, pairing computation and group operations considered in this work are implemented in Sagemath (relying on the finite field arithmetic of Sagemath) at

https://gitlab.inria.fr/guillevi/pairings-192

## 3.2 Pairing Computation: Miller Loop

As stated earlier, for all curves given in Table 5 we apply the optimal ate pairing, introduced by Vercauteren [Ver10], following our selection criterion (C5). In Table 6 we give the form of Equation (1), as well as the corresponding optimal ate pairing formulas, for all families of pairing-friendly elliptic curves considered in Table 5. These formulas are simplified using the properties described in Section 2. We note that for some curves, there exist alternative choices for the short vectors, which however do not offer any advantage in terms of efficiency compared to the ones that we have chosen.

**Remark 1** (Concerning BLS curves with odd embedding degrees $k = 3 \pmod 6$, examples are BLS15, BLS21, and BLS27 in Table 6). For these curves, the verticals are not in a subfield and there is no easy *denominator elimination* as for even embedding degrees. Nevertheless the optimal ate Miller loop simplifies to $f_{u,Q}(P)$. One starts expanding the Miller loop of length $u - p$: $f_{u-p,Q}(P) = f_{u,Q}(P)f_{-p,Q}(P)l_{uQ,-[p]Q}(P)$. Now observe that $f_{-p,Q}(P) = f_{p,Q}^{-1}(P)/v_{[p]Q}(P)$ with a vertical at $[p]Q$ evaluated at $P$. Also the line through
<table><caption>**Table 6:** Optimal ate Miller loop formulas. The Miller functions $f_{u,Q}$ and lines $\ell_{Q,R}$ are evaluated at the point $P \in \mathbb{G}_1$.</caption><thead><tr><th>k</th><th>curve</th><th>Equation (1)</th><th>Optimal ate formula</th></tr></thead><tbody><tr><td>12</td><td>BLS12</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td>15</td><td>BLS15</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td></td><td>FM15</td><td>$u - p^4 \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td>16</td><td>KSS16</td><td>$2 + up^3 + p^4 \equiv 0 \mod r$</td><td>$[f_{u,Q}(P) \cdot \ell_{[u]Q,\pi(Q)}(P)]^{p^3} \cdot \ell_{Q,Q}(P)$</td></tr><tr><td></td><td>FM16</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td></td><td>AFG16</td><td>$u + p^5 \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td>18</td><td>KSS18</td><td>$1 + up^2 + 2p^3 \equiv 0 \mod r$</td><td>$f_{u,Q}(P) \cdot f_{2,Q}(P)^p \cdot \ell_{[u]Q,\pi([2]Q)}(P)$</td></tr><tr><td></td><td>SG18</td><td>$u + p^2 + up^3 \equiv 0 \mod r$</td><td>$[f_{u,Q}(P)]^{1+p^3} \cdot \ell_{[u]Q,\pi_2(Q)}(P)$</td></tr><tr><td></td><td>FM18</td><td>$1 + up^2 \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td>20</td><td>FM20/FST20</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td></td><td>SG20</td><td>$2u + p^2 + p^7 \equiv 0 \mod r$</td><td>$f_{2u,Q}(P) \cdot \ell_{[2u]Q,\pi_2(Q)}(P)$</td></tr><tr><td></td><td>GG20b</td><td>$u - p - 2p^6 \equiv 0 \mod r$</td><td>$f_{u,Q}(P) \cdot f_{2,\pi_6(-Q)}(P) \cdot \ell_{[u]Q,-\pi(Q)}(P)$</td></tr><tr><td>21</td><td>BLS21</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td>24</td><td>BLS24</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td>27</td><td>BLS27</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td>28</td><td>FST28</td><td>$u - p \equiv 0 \mod r$</td><td>$f_{u,Q}(P)$</td></tr><tr><td></td><td>GG28</td><td>$u - p - 2p^8 \equiv 0 \mod r$</td><td>$f_{u,Q}(P) f_{2,-\pi_8(Q)}(P) \ell_{-2\pi_8(Q),-\pi(Q)}(P)$</td></tr></tbody></table>

$[u]Q$ and $-[p]Q$ is a vertical since $[u - p]Q = \mathcal{O}$. Finally $1/v_{[p]Q}(P)$ and $\ell_{[u]Q,-[p]Q}(P)$ cancel themselves, and $f_{p,Q}(P)$ is a pairing and can be taken out. The final formula is indeed $f_{u,Q}(P)$ like for BLS curves of even embedding degrees.

In Table 7 we report the cost for the different elliptic curve operations that are relevant to the pairing computation and especially the Miller loop. Specifically, we include the cost for computing the point addition and point doubling (column 3), as well as the cost of the line computation (column 3) and result accumulation (column 4) that occur in the Miller loop. The elliptic curve model that we have considered is the Weierstrass model, where points are represented in the projective coordinate system, following the works of Chatterjee, Sarkar, Barua [CSB05] and Costello, Lange, Naehrig [CLN10]. In addition, these costs refer to elliptic curves admitting degree 2, 3, 4 and 6 twists. In Table 10 we denote by $\mathbf{m}_i$ and $\mathbf{s}_i$ the multiplication and squaring, respectively, in the finite field $\mathbb{F}_{p^i}$, for $i > 1$ and by $\mathbf{m}$ we denote multiplication over the base field $\mathbb{F}_p$.

In column 4 of Table 7 we report the cost in terms of $\mathbb{F}_p$ multiplications for computing a product of two elements in $\mathbb{F}_{q^d}$, where $q = p^{k/d}$ and $d \in \{2, 3, 4, 6\}$ is the degree of the twist. More concretely, we write $a, b \in \mathbb{F}_{q^d}$, such that:

$$a = \sum_{i=0}^{d-1} a_i w^i \quad \text{and} \quad b = \sum_{i=0}^{d-1} b_i w^i,$$

where $a_i, b_i \in \mathbb{F}_q$ and $w$ is the generator of the degree $d$ extension $\mathbb{F}_{q^d}$ of $\mathbb{F}_q$. The term **sparse-sparse-m**$_k$ refers to the case where in the representations of $a$ and $b$, some of the coefficients $a_i$ and $b_i$ are zero (sparse representation), while on the other hand, **full-sparse-m**$_k$ is the case where one of the two representations is sparse. Such types of $\mathbb{F}_{q^d}$-multiplications appear when updating the Miller function after the doubling and addition steps in the Miller loop when sextic or quartic twists are applied. Note that when quadratic or cubic twists are employed, the **sparse-sparse-m**$_k$ and **full-sparse-m**$_k$ multiplications are equivalent to an $\mathbf{m}_k$ multiplication, as reported in Table 7.
<table><caption>**Table 7:** Miller loop cost in Weierstrass model from [CSB05, CLN10], sp = sparse.</caption><thead><tr><th>k</th><th>curve</th><th>Db1 step, tangent line<br>Add step, chord line</th><th>sparse-sp-m<sub>k</sub><br>full-sp-m<sub>k</sub></th><th>reference</th></tr></thead><tbody><tr><td rowspan="2">2 | k</td><td>y<sup>2</sup> = x<sup>3</sup> + ax + b</td><td>5m<sub>k/2</sub> + 6s<sub>k/2</sub> + km</td><td>m<sub>k</sub></td><td rowspan="2">[CSB05]</td></tr><tr><td>quadratic twist</td><td>10m<sub>k/2</sub> + 3s<sub>k/2</sub></td><td>m<sub>k</sub></td></tr><tr><td rowspan="2">2 | k</td><td>y<sup>2</sup> = x<sup>3</sup> - 3x + b</td><td>6m<sub>k/2</sub> + 4s<sub>k/2</sub> + km</td><td>m<sub>k</sub></td><td rowspan="2">[CSB05]</td></tr><tr><td>quadratic twist</td><td>10m<sub>k/2</sub> + 3s<sub>k/2</sub></td><td>m<sub>k</sub></td></tr><tr><td rowspan="2">2 | k</td><td>y<sup>2</sup> = x<sup>3</sup> + b</td><td>2m<sub>k/2</sub> + 7s<sub>k/2</sub> + km</td><td>m<sub>k</sub></td><td rowspan="2">[CLN10, §5,<br>Table 3]</td></tr><tr><td>quadratic twist</td><td>10m<sub>k/2</sub> + 2s<sub>k/2</sub> + km</td><td>m<sub>k</sub></td></tr><tr><td rowspan="2">2 | k</td><td>y<sup>2</sup> = x<sup>3</sup> + ax</td><td>2m<sub>k/2</sub> + 8s<sub>k/2</sub> + km</td><td>m<sub>k</sub></td><td rowspan="2">[CLN10, §4,<br>Table 3]</td></tr><tr><td>quadratic twist</td><td>9m<sub>k/2</sub> + 5s<sub>k/2</sub> + km</td><td>m<sub>k</sub></td></tr><tr><td rowspan="2">3 | k</td><td>y<sup>2</sup> = x<sup>3</sup> + b</td><td>6m<sub>k/3</sub> + 7s<sub>k/3</sub> + km + m<sub>b</sub></td><td>m<sub>k</sub></td><td rowspan="2">[CLN10, §6]</td></tr><tr><td>cubic twist</td><td>13m<sub>k/3</sub> + 5s<sub>k/3</sub> + km</td><td>m<sub>k</sub></td></tr><tr><td rowspan="2">6 | k</td><td>y<sup>2</sup> = x<sup>3</sup> + b</td><td>2m<sub>k/6</sub> + 7s<sub>k/6</sub> + (k/3)m</td><td>6m<sub>k/6</sub></td><td rowspan="2">[CLN10, §5]</td></tr><tr><td>sextic twist</td><td>10m<sub>k/6</sub> + 2s<sub>k/6</sub> + (k/3)m</td><td>13m<sub>k/6</sub></td></tr><tr><td rowspan="2">6 | k</td><td>y<sup>2</sup> = x<sup>3</sup> + b</td><td>3m<sub>k/6</sub> + 6s<sub>k/6</sub> + (k/3)m</td><td>6m<sub>k/6</sub></td><td rowspan="2">[AKL<sup>+</sup>11,<br>§4,6]</td></tr><tr><td>sextic twist</td><td>11m<sub>k/6</sub> + 2s<sub>k/6</sub> + (k/3)m</td><td>13m<sub>k/6</sub></td></tr><tr><td rowspan="2">4 | k</td><td>y<sup>2</sup> = x<sup>3</sup> + ax</td><td>2m<sub>k/4</sub> + 8s<sub>k/4</sub> + (k/2)m</td><td>6m<sub>k/4</sub></td><td rowspan="2">[CLN10, §4]</td></tr><tr><td>quartic twist</td><td>9m<sub>k/4</sub> + 5s<sub>k/4</sub> + (k/2)m</td><td>8m<sub>k/4</sub></td></tr></tbody></table>

### 3.3 Pairing Computation: Final Exponentiation

Table 8 shows the formulas for the easy and hard parts of the final exponentiation for each embedding degree we consider in this paper. The computation of the easy part is straightforward, while for the hard part we follow the state of the art approaches to obtain an optimized formula for the final exponentiation in the examples that we present here. That is, according to [HHT20], there are three distinct techniques for the efficient computation of the hard part: (i) a base-$p$ expansion to exploit cheap Frobenius powers, (ii) a lattice-reduction technique on the exponent in base $p$ to reduce further the size of the coefficients of the base-$p$ expansion, and (iii) a cyclotomic decomposition of the exponent. The latter technique is better suited when the trace of Frobenius of the curve is represented as a polynomial of degree one, which is the case for all BLS curves.

<table><caption>**Table 8:** Exponents for the final exponentiation, easy and hard parts.</caption><thead><tr><th>k</th><th>final exp. easy part</th><th>final exp. hard part</th></tr></thead><tbody><tr><td>12</td><td>(p<sup>6</sup> - 1)(p<sup>2</sup> + 1)</td><td>(p<sup>4</sup> - p<sup>2</sup> + 1)/r</td></tr><tr><td>15</td><td>(p<sup>5</sup> - 1)(p<sup>2</sup> + p + 1)</td><td>(p<sup>8</sup> - p<sup>7</sup> + p<sup>5</sup> - p<sup>4</sup> + p<sup>3</sup> - p + 1)/r</td></tr><tr><td>16</td><td>p<sup>8</sup> - 1</td><td>(p<sup>8</sup> + 1)/r</td></tr><tr><td>18</td><td>(p<sup>9</sup> - 1)(p<sup>3</sup> + 1)</td><td>(p<sup>6</sup> - p<sup>3</sup> + 1)/r</td></tr><tr><td>20</td><td>(p<sup>10</sup> - 1)(p<sup>2</sup> + 1)</td><td>(p<sup>8</sup> - p<sup>6</sup> + p<sup>4</sup> - p<sup>2</sup> + 1)/r</td></tr><tr><td>21</td><td>(p<sup>7</sup> - 1)(p<sup>2</sup> + p + 1)</td><td>(p<sup>12</sup> - p<sup>11</sup> + p<sup>9</sup> - p<sup>8</sup> + p<sup>6</sup> - p<sup>4</sup> + p<sup>3</sup> - p + 1)/r</td></tr><tr><td>24</td><td>(p<sup>12</sup> - 1)(p<sup>4</sup> + 1)</td><td>(p<sup>8</sup> - p<sup>4</sup> + 1)/r</td></tr><tr><td>27</td><td>p<sup>9</sup> - 1</td><td>(p<sup>18</sup> + p<sup>9</sup> + 1)/r</td></tr><tr><td>28</td><td>(p<sup>14</sup> - 1)(p<sup>2</sup> + 1)</td><td>(p<sup>12</sup> - p<sup>10</sup> + p<sup>8</sup> - p<sup>6</sup> + p<sup>4</sup> - p<sup>2</sup> + 1)/r</td></tr></tbody></table>

In the following we give the formulas for the optimized hard part of the final exponentiation for all families of Table 5. In each case we present the theoretical cost in terms of the number of required operations. Section 3.3.1 decomposes the hard part exponent $\Phi_k(p)/r$ with the techniques in [HHT20] while Section 3.3.2 considers lattice reduction [FKR12] before a fine tuning, resulting in a final exponentiation by a multiple of the hard part
exponent $\Phi_k(p)/r$.

### 3.3.1 With Cyclotomic Decomposition

**BLS12.** The optimal formula [HHT20, §5 p.14] is:

$$3 \frac{\Phi_{12}(p)}{r} = (u-1)^2(p+u)(p^2+u^2-1)+3$$

with cost: $2 \exp(|u-1|) + 3 \exp(|u|) + 5\mathbf{m}_{12} + 1\mathbf{s}_{12} + 2\mathbf{f}_{12} + 1\mathbf{f}_{6}$.

**BLS15.** The formula in [HHT20, §5 p.14] is:

$$3 \frac{\Phi_{15}(p)}{r} = (u-1)^2(u^2+u+1) \left( \sum_{i=0}^{7} \lambda_i p^i \right) + 3,$$

where $\lambda_7 = 1$ and the rest of the $\lambda_i$ are defined as follows:

$$\lambda_6 = u\lambda_7 - 1, \lambda_5 = u\lambda_6, \lambda_4 = u\lambda_5 + 1, \lambda_3 = u\lambda_4 - 1, \lambda_2 = u\lambda_3 + 1, \lambda_1 = u\lambda_2, \lambda_0 = u\lambda_1 - 1.$$

The cost is: $1 \exp(|u-1|) + 1 \exp(|u^3-1|) + 7 \exp(|u|) + 14\mathbf{m}_{15} + 1\mathbf{s}_{15} + 7\mathbf{f}_{15} + \mathbf{linv-cyclo}_{15}$, where $\mathbf{inv-cyclo}_{15}$ corresponds to cyclotomic inversion in $\mathbb{F}_{p^{15}}$ and is equivalent to $f^{-1} = f^{p^{10}}f^{p^5}$ with cost $\mathbf{inv-cyclo}_{15} = \mathbf{f}_{10} + \mathbf{f}_{5} + \mathbf{m}_{15}$.

**FM16.** We obtain the formula:

$$\frac{\Phi_{16}(p)}{r} = \left[ \frac{u^2}{4}(u^6 + 1) + 1 \right] (p+u)(p^2+u^2)(p^4+u^4) + 1$$

with cost: $13 \exp(|u|) + 2 \exp(|u|/2) + 6\mathbf{m}_{16} + 3\mathbf{f}_{16} + (\mathbf{c}\mathbf{j}_{16})$. We note that the seed $u$ for this family is always even, in order to produce primes $p$ and $r$ [FM19]. In addition, our implementation works for negative seeds as well, in which case one cheap conjugation is needed in the operation count $(\mathbf{c}\mathbf{j}_{16})$.

**AFG16.** We compute this formula for Family 1 for $k = 16$:

$$\frac{\Phi_{16}(p)}{r} = \left[ \left( \frac{u^2}{4}(u^3 + 1)^2 + 1 \right) \left( p^5 + u(u^3p(1 + up^3) - 1) \right) + up(1 + up^3) \right] + 1$$

with cost: $2 \exp(u/2) + 13 \exp(u) + 9\mathbf{m}_{16} + 4\mathbf{f}_{16}$.

**SG18.** For the hard part of SG18 we apply the formula of Scott-Guillevic [SG18], namely:

$$\frac{\Phi_{18}(p)}{r} = (3u^2 - 1)^2 \left[ (p^2 + 3pu^2 + 9u^4 + 3u)(1 - 3up + p^3) - 3p^2 \right] + (1 - 3up + p^3)$$

with total cost: $9 \exp(|u|) + 14\mathbf{m}_{18} + 5\mathbf{s}_{18} + 5\mathbf{f}_{18} + 3\mathbf{c}\mathbf{j}_{18} + (\mathbf{c}\mathbf{j}_{18})$. The additional conjugation is added to include the case of negative seeds.

**FM18.** Our formula for the hard part of the final exponentiation is the following:

$$\frac{\Phi_{18}(p)}{r} = (p-u) \left[ \left( u^6 + \frac{(u-1)^2}{3} + 1 \right) \left( p^4 + p^3 u - p - u^3(p^3 u - p - u) \right) + u(p^3 u - p - u) \right] + 1$$
with cost: $7 \exp(|u|) + \exp(|u-1|) + \exp(|u-1|/3) + 2 \exp(|u+1|) + 13\mathbf{m}_{18} + 2\mathbf{s}_{18} + 4\mathbf{f}_{18} + 4\mathbf{c}_{j_{18}}$.
We note also that $(u-1)^2 \equiv 0 \bmod 3$. Alternatively, one can multiply by 3 the exponent
to avoid a possibly non-sparse $(u-1)/3$:

$$
\frac{3\Phi_{18}(p)}{r} = (p-u) \left[ \left( 2(2(u^6+1)-u) + u^2 - u^6 \right) \left( p^4 + p^3u - p - u^3(p^3u - p - u) \right) \right. \\
\left. \qquad + 3u(p^3u - p - u) \right] + 3
$$

with cost: $11 \exp(|u|) + 12\mathbf{m}_{18} + 3\mathbf{s}_{18} + 4\mathbf{f}_{18} + 6\mathbf{c}_{j_{18}}$.

**FM20/FST20.** The hard part of the final exponentiation for FM20 [FM19, Family #27, Table 2] is equivalent to FST6.4 [FST10, Construction 6.4] for $k = 20$. The formula we considered is:

$$
\frac{\Phi_{20}(p)}{r} = \frac{(u-1)^2}{4} (u^2+1)(p+u) \left[ (p^2+u^2-1)(p^4+u^4+1) - u^2 p^2 \right] + 1,
$$

with total cost: $2 \exp(|u-1|/2) + 9 \exp(|u|) + 8\mathbf{m}_{20} + 1\mathbf{f}_{20} + 2\mathbf{f}_{2} + 1\mathbf{f}_{4} + 2\mathbf{c}_{j_{20}} + (1\mathbf{c}_{j_{20}})$,
where the one additional conjugation is required when the seed is negative.

**BLS21.** For this type of curves, we apply [HHT20, Theorem 1] to obtain the following formula for the hard part of the final exponentiation:

$$
3 \frac{\Phi_{21}(p)}{r} = (u-1)(u^3-1) \left( \sum_{i=0}^{11} \lambda_i p^i \right) + 3,
$$

where $\lambda_{11} = 1$, $\lambda_i = u\lambda_{i+1} + c_i$ and $c_i$ is defined as:

$$
c_i = \begin{cases} 1, & \text{for } i = 2, 5, 8 \\ 0, & \text{for } i = 1, 4, 6, 9 \\ -1, & \text{for } i = 0, 3, 7, 10 \end{cases}
$$

with cost: $15 \exp(|u|) + 15\mathbf{m}_{21} + \mathbf{s}_{21} + 11\mathbf{f}_{21} + 2\text{inv-cyclo}_{21}$.

**BLS24.** The hard part of the final exponentiation is written as [HHT20, §5 p.16]:

$$
3 \frac{\Phi_{24}(p)}{r} = (u-1)^2(u+p)(u^2+p^2)(u^4+p^4-1)+3
$$

with cost: $2 \exp(|u-1|) + 7 \exp(|u|) + 6\mathbf{m}_{24} + \mathbf{s}_{24} + 3\mathbf{f}_{24} + \mathbf{c}_{j_{24}}$.

**BLS27.** We apply the formula of [HHT20, §5 p.16] for computing the hard part of the
final exponentiation for BLS27. We have:

$$
\frac{\Phi_{27}(p)}{r} = (u-1)^2(p^2 + pu + u^2)(p^6 + p^3u^3 + u^6)(p^9 + u^9 + 1) + 3
$$

The total cost is: $2 \exp(|u-1|) + 17 \exp(|u|) + 8\mathbf{m}_{27} + \mathbf{s}_{27} + \mathbf{f}_{27} + \mathbf{f}_{27}^2 + \mathbf{f}_{27}^3 + \mathbf{f}_{27}^6 + \mathbf{f}_{27}^9 + 3(\mathbf{m} + 2\mathbf{f})$ if $u < 0$.
**FST28.** Our optimal formula for the hard part of the final exponentiation is:

$$ \frac{\Phi_{28}(p)}{r} = \frac{(u-1)^2}{4} (u^2+1)(p+u)e + 1, $$

where the value $e$ is determined as follows:

$$ e = \left( u^2(u^2 + p^2) + p^4 \right) \left( u^2(u^2(u^2 - 1) + 1) + p^6 - 1 \right) + \left( 1 - p^6 \right) \left( (u^2 - 1) + p^2 \right). $$

The total cost is: $2 \exp(|u-1|/2) + 13 \exp(|u|) + 12\mathbf{m}_{28} + 1\mathbf{f}_{28} + 2\mathbf{f}_{2} + 1\mathbf{f}_{4} + 2\mathbf{f}_{6} + 2\mathbf{c}\mathbf{j}_{28} + (1\mathbf{c}\mathbf{j}_{28})$, where the extra conjugation appears in the case where the seed is negative.

### 3.3.2 With Lattice Reduction

**FM15.** We use the following formula for the hard part in the case of FM15:

$$ 3u(u^3 - u^2 + 1) \frac{\Phi_{15}(p)}{r} = \sum_{i=0}^{7} \lambda_i p^i, $$

where the $\lambda_i$ are defined by the following relations:

$$ \lambda_6 = -3 - 3u^2 + 2u^4 + u^5 + 2u^6 - 3u^8, $$

$$ \lambda_0 = -(u^6 - u^4 + u^3)\lambda_6 + 3u^2 + 3u $$

$$ \lambda_1 = u^7\lambda_6 - (3u^3 + 3u^3 + 3u), $$

$$ \lambda_2 = u^3\lambda_6 $$

$$ \lambda_3 = -(u^7 + u^2 - 1)\lambda_6 + 3u^3 + 3u^2 + 3u, $$

$$ \lambda_4 = (u^7 - u^5 - 1)\lambda_6 - (3u^3 + 3u^2 - 3) $$

$$ \lambda_5 = u^4\lambda_6 - 3, $$

$$ \lambda_7 = -(u^4 - u^3 + u)\lambda_6 + 3 $$

Then the total cost is: $15 \exp(|u|) + 37\mathbf{m}_{15} + 6\mathbf{s}_{15} + 11\mathbf{f}_{15} + 2\mathbf{f}_{5} + 2\mathbf{inv-cyclo}_{15}$ when $u > 0$, while one less multiplication in $\mathbb{F}_{p^{15}}$ is required for negative seeds.

**KSS18.** For the computation of the hard part of the final exponentiation, the most efficient method is presented in [CHZ22]. We write

$$ \frac{3u^2}{49} \cdot \frac{\Phi_{18}(p)}{r} = \sum_{i=0}^{5} \lambda_i p^i $$

where the $\lambda_i$ are defined in terms of the cofactor $c = 3h(u)/49 = u^2 + 5u + 7$:

$$ \lambda_5 = u^2c + 3, $$

$$ \lambda_4 = -3u\lambda_5 - 49c, $$

$$ \lambda_3 = 2u^2\lambda_5 + 35uc, $$

$$ \lambda_1 = 2\lambda_4 + u\lambda_5, $$

$$ \lambda_0 = 2\lambda_3 + u\lambda_4, $$

$$ \lambda_2 = -u\lambda_0 + 2\lambda_5 $$

The cost for the hard part in this case is: $7 \exp(u) + 24\mathbf{m}_{18} + 11\mathbf{s}_{18} + 7\mathbf{f}_{9} + 5\mathbf{f}_{18}$.

**SG20.** For the hard part of the final exponentiation for the SG20 family we apply the lattice reduction to obtain the formula $\Phi_{20}(p)/r = \sum_{i=0}^{7} \lambda_i p^i$. The $\lambda_i$ in this representation are defined as $\lambda_6 = uh + 1$, $\lambda_7 = uy$, with $y = 2u\lambda_6 - 1$, $\lambda_0 = -uy'$, with $y' = 2u\lambda_7$, $\lambda_1 = -uy''$, with $y'' = -2u\lambda_0$ and for the rest of the $\lambda_i$ we have:

$$ \lambda_4 = \lambda_1 - \lambda_6 - y, \lambda_3 = -\lambda_1 - \lambda_6 + y'', \lambda_2 = -\lambda_3 + y' + \lambda_7 - h, \lambda_5 = -\lambda_3 + \lambda_0 - h $$

The total cost is: $13 \exp(|u|) + 19\mathbf{m}_{20} + 6\mathbf{s}_{20} + 7\mathbf{f}_{20} + 7\mathbf{c}\mathbf{j}_{20} + (\mathbf{c}\mathbf{j}_{20})$, where the additional conjugation is to account for the case of negative seeds.
### 3.3.3 Base-p Expansion

KSS16. For the hard part of the KSS16 family we obtained the following formula:

$$ \frac{2u^7 + 48u^3}{125} \cdot \frac{\Phi_{16}(p)}{r} = (u^3c + 56)e_1 + ce_2 - 1540p^7, $$

where $c = 2h(u)/125 = u^2 + 2u + 5$ and the values $e_1, e_2$ are defined as:

$$ e_1 = u^4 p^7 + u^3(1 - 2p^4) + u^2 p(3 + 4p^4) + up^2(-11 + 2p^4) + p^3(7 + 24p^4) $$

$$ e_2 = 125p^2(p^4 - 2) + 25up(3p^4 + 4) + 5u^2(-11p^4 + 2) $$

The total cost for computing the hard part for KSS16 is: $2 \exp(u-1) + 7 \exp(u) + 29s_{16} + 30m_{16} + 10f_4 + 4f_{16}$, improving on the previous best count from [Gha16, §4.3 p.107, Eq. (4.9) p.114] (also at [GF16]) of $2 \exp(u+1) + 7 \exp(u) + 37s_{16} + 35m_{16} + 4f_{16} + 2f_2 + f_4$.

**GG20a and GG20b.** For the hard part of the final exponentiation we use the fact that $p^8 = (p^6 - p^4 + p^2 - 1) \mod r$ and we set the following values: $c = u^2 - 2u + 5$, $\alpha_{\pm} = 2 \pm p^5$, $\beta_{\pm} = 4 \pm 3p^5$, $\gamma_{\pm} = 7 \pm 24p^5$ and $\delta_{\pm} = 11 \pm 2p^5$. Then we obtain the following formula for the hard part of the GG20a family, where $s$ is a scaling factor coprime to $r$:

$$ s \frac{\Phi_{20}(p)}{r} = (u^4c + 328)(-41p^2 + up\gamma_{-} + u^2\delta_{-} + u^3p^4\beta_{-} + u^4p^3\alpha_{+} + u^5p^7) + c(625p\alpha_{-} + 125u\beta_{+} + 25u^2p^4\delta_{+} + 5u^3p^3\gamma_{+} + 38u^4p^7) + 6724p^7 $$

with a total cost: $2 \exp(u-1) + 9 \exp(u) + 51s_{20} + 42m_{20} + 4f_5 + 9f_{20}$.

Using the same logic as for GG20a and changing only $\alpha_{\pm} = \pm 2 + p^5$ and $\beta_{\pm} = \pm 4 + 3p^5$, the GG20b final exponent is written as follows, with exactly the same cost as GG20a:

$$ s' \frac{\Phi_{20}(p)}{r} = (u^4c - 328)(-41p^2 + up\gamma_{+} + u^2\delta_{+} + u^3p^4\beta_{+} + u^4p^3\alpha_{-} + u^5p^7) + c(-625p\alpha_{+} + 125u\beta_{-} + 25u^2p^4\delta_{-} + 5u^3p^3\gamma_{-} - 38u^4p^7) + 6724p^7 $$

**GG28.** With a strategy similar to GG20, we use the fact that $p^{12} = (p^{10} - p^8 + p^6 - p^4 + p^2 - 1) \mod r$ and we set the following values: $c = u^2 - 2u + 5$, $\alpha_{\pm} = -2 \pm p^7$, $\beta_{\pm} = -4 \pm 3p^7$, $\gamma = 11p^7 + 2$, $\bar{\gamma} = 11 + 2p^7$, $\bar{\delta} = 24 + 7p^7$, $\bar{\delta} = 24p^7 + 7$, $\epsilon_{\pm} = -41 \pm 38p^7$, and $\zeta_{\pm} = -117 \pm 44p^7$. Then we obtain the following formula for the hard part, where $s$ is a scaling factor coprime to $r$:

$$ s \frac{\Phi_{28}(p)}{r} = (u^6c - 232)e_1 + ce_2 + 3364p^{11} $$

where the values $e_1, e_2$ are defined as follows:

$$ e_1 = -29p^4 + up^3\zeta_{-} + u^2p^2\epsilon_{+} + u^3p\bar{\delta} + u^4\bar{\gamma} + u^5p^6\beta_{-} + u^6p^5\alpha_{+} + u^7p^{11} $$

$$ e_2 = 5^6p^3\alpha_{-} + 5^5up^2\beta_{+} + 5^4u^2p\gamma + 5^3u^3\delta + 5^2u^4p^6\epsilon_{-} + 5u^5p^5\zeta_{+} + 278u^6p^{11} $$

The total cost is: $2 \exp(u-1) + 13 \exp(u) + 68s_{28} + 83m_{28} + 12f_7 + 14f_{28}$.

## 3.4 Pairing Computation: Theoretical Comparison

We present a theoretical analysis of the total cost for computing the different pairing instances of Table 5. More concretely, the usual practice in estimating the cost of a pairing is to express the Miller loop and the final exponentiation in terms of $\mathbb{F}_p$-multiplications. Then we aim at presenting a theoretical comparison of the different pairings Table 5,
<table><caption>**Table 9:** Relative cost of multiplication $\mathbf{m}_k$, squaring $\mathbf{s}_k$, Frobenius $\mathbf{f}_k$, and inversion $\mathbf{i}_k$ in finite field extensions assuming $p \equiv 1 \bmod k$ for fast $f_k$.</caption><thead><tr><th>k</th><th>m<sub>k</sub></th><th>s<sub>k</sub></th><th>f<sub>k</sub></th><th>s<sub>k</sub><sup>cyclo</sup></th><th>i<sub>k</sub> - i<sub>1</sub></th><th>i<sub>k</sub>, s = m<br>i<sub>1</sub> = 25m</th></tr></thead><tbody><tr><td>1</td><td>m</td><td>s</td><td>0</td><td>-</td><td>0</td><td>25m</td></tr><tr><td>2</td><td>3m</td><td>2m</td><td>0</td><td>2s</td><td>2m + 2s</td><td>29m</td></tr><tr><td>3</td><td>6m</td><td>2m + 3s [CH07]</td><td>2m</td><td>-</td><td>9m + 3s</td><td>37m</td></tr><tr><td>4</td><td>9m</td><td>2m<sub>2</sub> = 6m</td><td>2m</td><td>2s<sub>2</sub> = 4m</td><td>12m + 2s</td><td>39m</td></tr><tr><td>5</td><td>13m</td><td>13s [Mon05]</td><td>4m</td><td>-</td><td>48m</td><td>73m</td></tr><tr><td>6</td><td>18m</td><td>2m<sub>2</sub> + 3s<sub>2</sub> = 12m</td><td>4m</td><td>6m [GS10]</td><td>34m</td><td>59m</td></tr><tr><td>7</td><td>22m</td><td>22s</td><td>6m</td><td>-</td><td>104m</td><td>129m</td></tr><tr><td>8</td><td>27m</td><td>2m<sub>4</sub> = 18m</td><td>6m</td><td>2s<sub>4</sub> = 12m</td><td>44m</td><td>69m</td></tr><tr><td>9</td><td>36m</td><td>2m<sub>3</sub> + 3s<sub>3</sub> = 18m + 9s</td><td>8m</td><td>-</td><td>69m + 12s</td><td>106m</td></tr><tr><td>10</td><td>39m</td><td>2m<sub>5</sub> = 26m</td><td>8m</td><td>2s<sub>5</sub> = 26s</td><td>74m + 26s</td><td>125m</td></tr><tr><td>12</td><td>54m</td><td>2m<sub>6</sub> = 36m</td><td>10m</td><td>6m<sub>2</sub> = 18m</td><td>97m</td><td>119m</td></tr><tr><td>15</td><td>78m</td><td>2m<sub>5</sub> + 3s<sub>5</sub> = 26m + 39s</td><td>14m</td><td>-</td><td>165m + 39s</td><td>229m</td></tr><tr><td>16</td><td>81m</td><td>2m<sub>8</sub> = 54m</td><td>14m</td><td>2s<sub>8</sub> = 36m</td><td>134m</td><td>159m</td></tr><tr><td>18</td><td>108m</td><td>2m<sub>9</sub> = 72m</td><td>16m</td><td>6m<sub>3</sub> = 36m</td><td>232m</td><td>257m</td></tr><tr><td>20</td><td>117m</td><td>2m<sub>10</sub> = 78m</td><td>18m</td><td>2s<sub>10</sub> = 52m</td><td>255m</td><td>280m</td></tr><tr><td>21</td><td>132m</td><td>110m</td><td>20m</td><td>-</td><td>393m</td><td>418m</td></tr><tr><td>24</td><td>162m</td><td>2m<sub>12</sub> = 108m</td><td>22m</td><td>6m<sub>4</sub> = 54m</td><td>318m</td><td>343m</td></tr><tr><td>27</td><td>216m</td><td>153m</td><td>26m</td><td>-</td><td>511m</td><td>536m</td></tr><tr><td>28</td><td>198m</td><td>132m</td><td>26m</td><td>88m</td><td>437m</td><td>462m</td></tr></tbody></table>

based on the total number of $\mathbb{F}_p$-multiplications required. This theoretical comparison is outlined in Table 10 and will serve as the baseline for selecting the most promising pairing candidates to be included in our benchmark experiments in Section 5.

Such a theoretical comparison necessitates that all operations needed in the Miller loop and in the final exponentiation are translated to $\mathbb{F}_p$-multiplications. This conversion is described in Table 9, following the usual estimates, e.g. [GMT20, Table 4] for a recent presentation. We denote $\mathbf{m}_i$, resp. $\mathbf{s}_i$ a multiplication, resp. squaring in $\mathbb{F}_{p^i}$. Furthermore, we denote $\mathbf{f}_i$, $\mathbf{s}_k^{\text{cyclo}}$ and $\mathbf{i}_i$ the Frobenius $p$-power, the cyclotomic squaring and inversion in $\mathbb{F}_{p^i}$. When it is clear from the context, $\mathbf{f}_j$ denotes a $p^j$-th power in $\mathbb{F}_{p^i}$. Based on the theoretical comparison in Table 10, we can extract the most promising curves to be benchmarked. We discuss the results of Table 10 and justify our selections of pairing-friendly curves to be benchmarked.

*Remark 2* (Inversions in extension fields). For inversions in $\mathbb{F}_{p^k}$, we use the classical formula:

$$x^{-1} = \frac{x^{p+p^2+\dots+p^{k-1}}}{x^{1+p+\dots+p^{k-1}}},$$

where the denominator is the norm $\text{Norm}_{\mathbb{F}_{p^k}/\mathbb{F}_p}(x)$ in $\mathbb{F}_p$. It costs the computation of the numerator with Frobenius powers and multiplications in $\mathbb{F}_{p^k}$, the denominator computation knowing that it is in $\mathbb{F}_p$, one inversion in $\mathbb{F}_p$, and a coefficient-wise multiplication. One can factor the exponent to minimize the multiplications. For $\mathbb{F}_{p^5}$: $p+p^2+p^3+p^4 = p(p+1)(p^2+1)$ and the numerator costs $3\mathbf{f}_5 + 2\mathbf{m}_5 = 38\mathbf{m}$. The denominator costs $5\mathbf{m}$. The total cost is $48\mathbf{m}+\mathbf{i}$. For $\mathbb{F}_{p^7}$ see [Mas20, page ix]: $104\mathbf{m}+\mathbf{i}$. $p+p^2+p^3+p^4+p^5+p^6 = p(p^3+1)(1+p+p^2)$ and the numerator costs $4\mathbf{f}_7 + 3\mathbf{m}_7 = 90\mathbf{m}$. The denominator costs $7\mathbf{m}+\mathbf{i}$. The result costs 7 more $\mathbf{m}$. Finally $\mathbf{i}_7 = 104\mathbf{m}+\mathbf{i}$.

In Table 10 we observe that of all curve instances, BLS12-1150 requires the smallest number of $\mathbb{F}_p$-multiplications, however the base field prime $p$ is 1150-bit long. At this
point it is not clear how BLS12-1150 compares to the other candidate curves, however this will become apparent in Section 5 where we discuss the benchmarking results. We now compare the curves of same embedding degree. For $k = 15$, FM15-762 clearly offers a more efficient pairing computation than its competitor BLS15-894 as it requires much less $\mathbb{F}_p$-multiplications and operates over a much smaller prime field. Recall also that FM15-762 has $\rho = 2$, while BLS15-894 has $\rho = 1.5$ showing that in this case, a larger $\rho$ offers better performances. However, we exclude both curves from our benchmark comparison, since both curves are not competitive to other embedding degrees.

For $k = 16$, all three curves KSS16-766, FM16-765 and AFG16-766 are defined over a prime field of almost the same size. The difference in the three families is that FM16-765 and AFG16-766 have $\rho = 2$, while on the contrary, KSS16-766 has $\rho \approx 1.25$. Both FM16-765 and AFG16-766 require almost the same number of $\mathbb{F}_p$-multiplications, which is approximately 20% less than the case of KSS16-766. This justifies our earlier claim that for some embedding degrees, having a larger $\rho$ is beneficial, improving the total pairing computation. We include all three curves for $k = 16$ to verify that the 20% improvement of FM16-765 and AFG16-766 over KSS16-766 is also captured in the benchmarking results.

In the case of $k = 18$, the curves KSS18-638 and SG18-638 operate on a smaller prime field compared to FM18-768. In this case, the theoretical analysis shows that SG18-638 requires less $\mathbb{F}_p$-multiplications for the pairing computation than the two competitors KSS18-638 and FM18-768 and in particular, it requires 15% less $\mathbb{F}_p$-multiplications than KSS18-638. In Section 5 we benchmark all three curves to have more conclusive evidence on their actual performance.

<table><caption>**Table 10:** Optimal ate pairing and final exponentiation cost estimates in terms of finite field multiplications. The name of each curve is derived from the name of the corresponding family in Table 5, plus the size of the prime $p$.</caption><thead><tr><th rowspan="2">Curve name</th><th rowspan="2">r (bits)</th><th rowspan="2">Miller loop opt. ate (m)</th><th colspan="3">final exp (m)</th><th rowspan="2">pairing total (m)</th></tr><tr><th>easy</th><th>hard</th><th>total</th></tr></thead><tbody><tr><td>BLS12-1150</td><td>768</td><td>19288</td><td>245</td><td>14176</td><td>14421</td><td>33709</td></tr><tr><td>BLS15-894</td><td>597</td><td>25259</td><td>501</td><td>58014</td><td>58515</td><td>83774</td></tr><tr><td>FM15-762</td><td>381</td><td>16731</td><td>501</td><td>55321</td><td>55822</td><td>72553</td></tr><tr><td>KSS16-766</td><td>605</td><td>16784</td><td>240</td><td>32826</td><td>33066</td><td>49850</td></tr><tr><td>FM16-765</td><td>384</td><td>10020</td><td>255</td><td>30024</td><td>30279</td><td>40299</td></tr><tr><td>AFG16-766</td><td>384</td><td>10020</td><td>255</td><td>30282</td><td>30537</td><td>40557</td></tr><tr><td>KSS18-638</td><td>474</td><td>17433</td><td>480</td><td>27008</td><td>27488</td><td>44921</td></tr><tr><td>SG18-638</td><td>383</td><td>13351</td><td>480</td><td>24308</td><td>24788</td><td>38139</td></tr><tr><td>FM18-768</td><td>384</td><td>13410</td><td>464</td><td>33184</td><td>33648</td><td>47058</td></tr><tr><td>FM20-670</td><td>448</td><td>18416</td><td>507</td><td>35276</td><td>35783</td><td>54199</td></tr><tr><td>SG20-670</td><td>383</td><td>16427</td><td>507</td><td>39152</td><td>39659</td><td>56086</td></tr><tr><td>GG20b-575</td><td>379</td><td>17554</td><td>507</td><td>42017</td><td>42524</td><td>60078</td></tr><tr><td>BLS24-509</td><td>409</td><td>15345</td><td>658</td><td>24310</td><td>24968</td><td>40313</td></tr><tr><td>BLS21-511</td><td>384</td><td>19321</td><td>717</td><td>62426</td><td>63143</td><td>82464</td></tr><tr><td>BLS27-426</td><td>383</td><td>22212</td><td>1185</td><td>88438</td><td>89907</td><td>112119</td></tr><tr><td>FST28-510</td><td>384</td><td>18940</td><td>859</td><td>56080</td><td>56939</td><td>75879</td></tr><tr><td>GG28-500</td><td>381</td><td>20326</td><td>859</td><td>78474</td><td>79333</td><td>99659</td></tr></tbody></table>

In the case of $k = 20$ the theoretical analysis is less inconclusive as to which curve is the best option for this embedding degree. Note that FM20/FST20-670 and SG20-670 operate on a prime field of the same size and require comparable number of $\mathbb{F}_p$-multiplications, with FM20/FST20-670 having a slight advantage (approximately 3% less $\mathbb{F}_p$-multiplications). On the other hand, although GG20b-575 requires 5879m more compared to FM20/FST20-
<figure><img src="image_3.png" /><figcaption>**Figure 1:** Estimates of Miller loop in terms of normalized multiplications in $\mathbb{F}_p$ of 512 bits.</figcaption></figure>

670, the prime field size is significantly smaller in the case of GG20b-575. Nevertheless, we do not provide benchmarks for these curves, since they are certainly not competitive to other candidates for different embedding degrees. Note that these curves admit degree 4 twists, forcing elliptic curve point operations in the Miller loop to be executed over $\mathbb{F}_{p^5}$.

The curves BLS21-511, BLS24-509, BLS27-426, FST28-510 and GG28-500 offer the smallest primes $p$, compared to the previous candidate curves. Of these five curves, BLS24-509 is the most promising since it admits degree 6 twists and hence point additions and doublings in the Miller loop are executed over $\mathbb{F}_{p^3}$. In BLS21-511, FST28-510 and GG28-500 additions and doublings are executed over $\mathbb{F}_{p^7}$, while in the case of BLS27-426 over $\mathbb{F}_{p^9}$. Furthermore, Table 10 shows that BLS21-511, FST28-510 and GG28-500 require almost $2 \times$ more $\mathbb{F}_p$-multiplications than BLS24-509 and BLS27-426 requires almost $3 \times$ more $\mathbb{F}_p$-multiplications than BLS24-509. Therefore, of these five curves we only benchmark BLS24-509.

To summarize, the curves that we have chosen to include in our optimized implementation step are, BLS12-1150, KSS16-766, FM16-765, AFG16-766, KSS18-638, SG18-638, FM18-768 and BLS24-509.

**Normalized arithmetic cost.** We compared the estimated cost of the Miller loop and final exponentiation in Table 10. However when the base field size is different, the comparison is not always obvious. For example, how do the $j = 1728$ curve families compare to each other in terms of Miller loop? Assuming an architecture with 64-bit words, the fields need 12, 11, 9, and 8 machine-words for 768, 672, 576, and 512 bits resp. We apply the methodology from [AFK+13, Sect. 8]. Elements of $\mathbb{F}_p$ are assumed to be represented with $\ell = 1 + \lfloor \log_2 p \rfloor$ bits, packed in $w = \lfloor \ell/64 \rfloor$ 64-bit machine-words. If the Montgomery representation is implemented, a multiplication with reduction in $\mathbb{F}_p$ has complexity $O(2w^2 + w)$. The authors deduce that one can estimate the ratio $m_{640} = 210/136 = 1.544m_{512}$ (for $10w$). In the same way, we estimate $m_{576} = 171/136 = 1.257m_{512}$ (for $9w$), $m_{704} = 253/136 = 1.860m_{512}$ (for $11w$), $m_{768} = 300/136 = 2.205m_{512}$ (for $12w$). We finally obtain Table 11 and Figure 1.
<table><caption>**Table 11:** Optimal ate pairing and final exponentiation cost estimates in terms of finite field multiplications, normalized w.r.t. a multiplication in $\mathbb{F}_p$ of 512 bits ($\mathbf{m} = \mathbf{m}_{512}$), with the ratios $m_{448} = 0.772\mathbf{m}$, $m_{576} = 1.257\mathbf{m}$, $m_{640} = 1.544\mathbf{m}$, $m_{704} = 1.860\mathbf{m}$, $m_{768} = 2.205\mathbf{m}$, $m_{896} = 2.986\mathbf{m}$, $m_{1152} = 4.897\mathbf{m}$.</caption><thead><tr><th>Curve name</th><th>r (bits)</th><th>Miller loop opt. ate (m<sub>512</sub>)</th><th>final exp (m<sub>512</sub>)</th><th>pairing</th></tr><tr><th></th><th></th><th></th><th>easy</th><th>hard</th><th>total</th></tr></thead><tbody><tr><td>BLS12-1150</td><td>768</td><td>94455</td><td>1200</td><td>69421</td><td>70621</td><td>165075</td></tr><tr><td>BLS15-894</td><td>597</td><td>75406</td><td>1496</td><td>173189</td><td>174685</td><td>250091</td></tr><tr><td>FM15-762</td><td>381</td><td>36907</td><td>1106</td><td>122032</td><td>123137</td><td>160044</td></tr><tr><td>KSS16-766</td><td>605</td><td>37024</td><td>530</td><td>72411</td><td>72940</td><td>109964</td></tr><tr><td>FM16-765</td><td>384</td><td>22103</td><td>563</td><td>66230</td><td>66792</td><td>88895</td></tr><tr><td>AFG16-766</td><td>384</td><td>22103</td><td>563</td><td>66799</td><td>67362</td><td>89464</td></tr><tr><td>KSS18-638</td><td>474</td><td>26919</td><td>742</td><td>41704</td><td>42445</td><td>69364</td></tr><tr><td>SG18-638</td><td>383</td><td>20616</td><td>742</td><td>37535</td><td>38276</td><td>58892</td></tr><tr><td>FM18-768</td><td>384</td><td>29581</td><td>1024</td><td>73200</td><td>74224</td><td>103805</td></tr><tr><td>FST20-670</td><td>448</td><td>34260</td><td>944</td><td>65624</td><td>66567</td><td>100827</td></tr><tr><td>SG20-670</td><td>383</td><td>30560</td><td>944</td><td>72835</td><td>73778</td><td>104337</td></tr><tr><td>GG20b-575</td><td>379</td><td>22072</td><td>638</td><td>52831</td><td>53468</td><td>75540</td></tr><tr><td>BLS21-511</td><td>384</td><td>19321</td><td>717</td><td>62426</td><td>63143</td><td>82464</td></tr><tr><td>BLS24-509</td><td>409</td><td>15345</td><td>658</td><td>24310</td><td>24968</td><td>40313</td></tr><tr><td>BLS27-426</td><td>383</td><td>17149</td><td>915</td><td>68280</td><td>69414</td><td>86563</td></tr><tr><td>FST28-510</td><td>384</td><td>18940</td><td>859</td><td>56080</td><td>56939</td><td>75879</td></tr><tr><td>GG28-500</td><td>381</td><td>20326</td><td>859</td><td>78474</td><td>79333</td><td>99659</td></tr></tbody></table>

# 4 Other pairing operations

In this section, we collect notes about how to implement other operations in pairing groups. We start by briefly surveying scalar multiplications and exponentiation algorithms, with their constant-time counterparts. We then continue by giving closed formulas for hashing and cofactor-clearing according to the latest state-of-the-art, and finish by enumerating techniques for subgroup membership testing.

## 4.1 Scalar multiplication and exponentiation in pairing groups

Pairing-friendly curves are typically equipped with additional efficient endomorphisms, such that the widely known Gallant-Lambert-Vanstone (GLV) [GLV01] and Galbraith-Lin-Scott (GLS) [GLS11] scalar multiplication and exponentiation algorithms are the most efficient.

**Endomorphisms on $\mathbb{G}_1$ and GLV.** All the curves we consider have either $D = 1$ and $j$-invariant 1728, or $D = 3$ and $j$-invariant 0. The curves of $j$-invariant 1728 (e.g. KSS16) have an endomorphism $\phi$ of the form $(x, y) \mapsto (-x, iy)$ where $i^2 = -1 \in \mathbb{F}_p$ as $p \equiv 1 \mod 4$, of characteristic polynomial $\chi_{\phi}(X) = X^2 + 1$. The curves of $j$-invariant 0 (e.g. KSS18, BLS) have an endomorphism $\phi$ of the form $(x, y) \mapsto (\omega x, y)$ where $\omega$ is a primitive third root of unity in $\mathbb{F}_p$, $\omega^2 + \omega + 1 = 0 \mod p$, as $p \equiv 1 \mod 3$, of characteristic polynomial $\chi_{\phi}(X) = X^2 + X + 1$. In the case of $\mathbb{G}_1$, it is well-known that the GLV technique can be used together with the endomorphism $\phi$ to decompose a scalar $\ell \in \mathbb{Z}_r$ into half-sized subscals $(\ell_0, \ell_1)$ such that $\ell \equiv \ell_0 + \ell_1\lambda_{\phi} \mod r$, with $\lambda_{\phi} \in \mathbb{Z}_r$ the eigenvalue of the $\phi$ map. The scalar multiplication can then proceed through the formula $[\ell]P = \ell_0P + \ell_1\phi(P)$, for $P \in \mathbb{G}_1$. A widely used algorithm to compute scalar multiplication combines the w-NAF scalar recoding algorithm and interleaving of the two smaller scalar multiplications to save point doublings. Because applying $\phi$ is very efficient in our pairing-friendly curves,
we can compute a single precomputation table with $2^{w-2}$ points for $P$ and apply $\phi$ to points obtained from the table. Constant-time versions of the algorithm typically replace the recoding process with a regular $w$-NAF expansion [JT09], which increases the density of non-zero digits from $\frac{1}{w+1}$ to $\frac{1}{w-1}$ and force secure table lookups to prevent leaking what points from the table are being used in the main loop [OLAR13]. From the point of view of efficiency, this approach compares favorably to alternatives such as the GLV-SAC method [FLS15], by computing fewer point additions at the same cost in precomputed storage.

**Endomorphisms on $G_2$ and $G_T$, and GLS.** In the case of $G_2$ and $G_T$, the GLS technique is used instead, assuming again that an efficient endomorphism is available. For $G_2$, the map $\psi$ is constructed as $(\tau^{-1} \circ \pi \circ \tau)$, where $\tau$ is the twisting isomorphism $\tau : E'(\mathbb{F}_{p^k/d}) \to E(\mathbb{F}_{p^k})$ and $\pi$ is the Frobenius map over $E(\mathbb{F}_{p^k})$. This endomorphism $\psi$ has characteristic polynomial $X^2 - tX + p$. It is well-known that $\psi$ has eigenvalue $p \equiv t - 1 \bmod r$ on $G_2$, by definition of $G_2 = \ker(\pi - [p])$ [HSV06, GS08, DLZZ23]. For $G_T$, we choose $\phi$ as a small multiple or power of the Frobenius $\pi_p$ in $\mathbb{F}_{p^k}$. In both cases $(G_2$ and $G_T)$, we can represent the scalar or exponent in base $p$ (the eigenvalue) by decomposing it in $m = \varphi(k)$ subscalsars, where $\varphi$ is Euler's totient function, such that $\ell = \sum_{0 \le i < m} \ell_i p^i \bmod r$. We can then use the Frobenius map to evaluate a scalar multiplication in $G_2$ as $[\ell]Q = \sum_{0 \le i < m} [\ell_i] \psi^i(Q)$ in interleaved $w$-NAF fashion, or the analogue in $G_T$ after translating to multiplicative notation. The endomorphisms $\psi$ in $G_2$ and $\pi_p G_T$ are quite efficient to evaluate, but it is typical to precompute the various tables over $\psi^i(Q)$ to avoid the cost of applying $\psi^i$ dynamically in succession. This can be efficiently performed either by precomputing the table over $Q$ and producing the other tables by applying $\psi^i$; or by computing each table over $\psi^i(Q)$ directly, depending on what is faster based on the cost of $\psi$. For constant-time implementation in both $G_2$ and $G_T$, we employ the GLV-SAC approach defined for the GLV dimension $m$. The method computes a table of $2^{m-1}$ elements and performs $\lceil \frac{\log_2 r}{m} \rceil$ point additions in the main loop, consuming less memory than the regular $w$-NAF approach for the same number of point additions, which happens with $m > 2$. We use the same approach for variable-time scalar multiplication when $m = 6$, due to the fewer point additions; and we employ the partitioned variant of GLV-SAC with $c = 2$ for $m = 8$, as to reduce memory requirements from $2^{m-1}$ to $c \cdot 2^{\frac{m}{c}-1}$ [FLS15]. The same notes about constant-time implementation apply, noting that the endomorphisms are more expensive to evaluate than in the case of $G_1$ and now there are $m$ subscalsars involved.

One simple implementation trick is useful when supporting multiple pairing-friendly curves simultaneously. Decomposing the scalar into base $p$ can be performed by finding a suitable relationship between the prime subgroup order $r$, the curve generation seed $u$ and the prime modulus $p$, such that we can exploit the fact that $p$ and $u$ are related modulo $r$ to decompose in base $u$. After writing the seed $u$ as an expression involving a few powers of $p$ for all curves, then we can decompose scalar $\ell$ in base $u$, and perform the scalar recoding with successive (constant-time) integer divisions. Many suitable relationships come directly from the Optimal ate formulas in Table 6, but some require further algebraic manipulation. For AFG16 curves, we exploit $u \equiv -p^5 \bmod r$, to define $\psi$ as the inverse $p^5$-power Frobenius. For KSS16 curves, we exploit $u \equiv (2p^5 - p) \bmod r$ instead. For KSS18 curves, we exploit $u = (p^3 - 3)p \bmod r$, and for FM18 curves we exploit $u \equiv (p^4 - p) \bmod r$. For SG18 curves, we exploit $-3u = (2p^2 - p^5) \bmod r$ to recode in base $3u$ and define $\psi$ as the $(p^5 - 2p^2)$-power Frobenius, while noting that inversion in both $G_2$ and $G_T$ can be efficiently computed.
## 4.2 Hashing to pairing source groups

Many cryptographic protocols involve hashing arbitrary bit strings to a group of points in an elliptic curve. The security requirements are generally the same for an ideal collision-resistant hash function, such that protocols can rely on the hash function to behave as closely as possible to a conventional random oracle. This notion is formalized as *indifferentiability* to a random oracle, or the infeasibility of differentiating the hash function from a random oracle with non-trivial probability [BCI+10], given a polynomially-bounded number of queries. Given an indifferentiable hash function $h$ with bit strings as inputs/outputs, we can hash to curves by initially constructing a function to hash to a field $\mathbb{F}_q$ and then an encoding function to map field elements to points in the curve, followed by a scalar multiplication by a cofactor to map the output to the right subgroup. From an implementation security standpoint, the full process should also be efficient when evaluated in constant time [WB19, AHST23].

The state-of-the-art approach for indifferentiable hashing to pairing-friendly elliptic curves is the SwiftEC algorithm [CSRT22] and its generalization [Kos24] to broader classes of elliptic curves. The former is restricted to curves with $q \equiv 1 \bmod 3$, with either odd order or order divisible by 4, having $a = 0$ (or $j$-invariant 0) as a special simpler case. Koshelev's generalization expands the constructions to all curves with $q \equiv 1 \bmod 3$ with non-zero $j$-invariant, which covers our remaining curves with $b = 0$ (or $j$-invariant 1728).

Let $\ell = [\log_2 q]$ be the bit length required to encode an element from $\mathbb{F}_q$. Function $H: \{0,1\}^* \to E(\mathbb{F}_q)$ can be constructed by the composition of functions $H = [c] \circ f \circ \eta \circ h$, where $h: \{0,1\}^* \to \{0,1\}^{2\ell+1}$ is a deterministic indifferentiable hash function, $\eta: \{0,1\}^{2\ell+1} \to \mathbb{F}_q^2 \times \{0,1\}$ is an encoding to the field (with an additional sign bit), $f: \mathbb{F}_q^2 \times \{0,1\} \to E(\mathbb{F}_q)$ is an admissible encoding to the group of points (the additional bit is to choose the $y$-coordinate), and $[c]$ corresponds to scalar multiplication by the cofactor. We select $h$ as the message expansion function XMD [FHSS+23] instantiated with SHA256 as the underlying hash function, and elaborate on the other choices below.

Given $(t_1, t_2) \in \mathbb{F}_q^2$ and a sign bit $s$, define the constants $\tau = \sqrt{-3} \in \mathbb{F}_q$ and $\omega = \frac{\tau-1}{2}$, and respectively the denominators $d_j$ and numerators $n_j$ for fractions $X_i = \frac{n_j}{d_j}$ with $j \in \{1, 2, 3\}$:

$$d_1 = -2\tau\omega(t_1^6 + 2^3 3\tau b t_1^3 + 2^6 a^3 + 2^3 3\tau t_1^3 t_2^2)t_1$$

$$d_2 = d_1 \cdot \omega$$

$$d_3 = -2^4 3^3 (t_1^2 - 2^2 a)^2 t_1^4 t_2^2$$

$$n_1 = t_1^8 + 2^2 \omega^2 a t_1^6 + 2^3 3 \tau b t_1^5 + 2^5 3 \tau \omega^2 a b t_1^3 + 2^6 a^3 t_1^2 + 2^8 \omega^2 a^4 + 2^3 3 \tau (\omega^2 t_1^2 + 2^2 a) t_1^3 t_2^2$$

$$n_2 = t_1^8 + 2^2 \omega a t_1^6 + 2^3 3 \tau b t_1^5 + 2^5 3 \tau \omega a b t_1^3 + 2^6 a^3 t_1^2 + 2^8 \omega a^4 + 2^3 3 \tau (\omega t_1^2 + 2^2 a) t_1^3 t_2^2$$

$$n_3 = t_1^{12} + 2^4 3 \tau b t_1^9 + 2^6 (2a^3 - 3^3 b^2)t_1^6 + 2^{10} 3 \tau a^3 b t_1^3 + 2^{12} a^6 - 2^3 3 \tau (t_1^6 - 2^2 3 a t_1^4 - 2^4 3 \tau b t_1^3 - 2^4 3 a^2 t_1^2 + 2^6 a^3 - 2^3 3 \tau t_1^3 t_2^2)t_1^3 t_2^2.$$

When all of the $X_j$ fractions are defined ($d_j \neq 0$), we select $X_j$ with highest $j$ as the $x$-coordinate, such that $g(X_j) = X_j^2 + aX_j + b$ is a quadratic residue, to compute $Y = \sqrt{g(X_j)}$. We then take the additional output bit of $\eta$ to select one of the square roots as $y$, and the output is $(X_j, y)$. Otherwise, we output the point at infinity $\mathcal{O}$, which happens only with negligible probability under the assumption that $h$ is indifferentiable from a random oracle. More formally,
$$f(t_1, t_2, s) = \begin{cases} \mathcal{O}, & \text{if any } d_j = 0, \text{ with } j \in \{1, 2, 3\}. \\ (X_i, (1-2s)Y), & \text{with } i = \max\left\{j \mid \left(\frac{g(X_j)}{q}\right) = 1\right\} \text{ otherwise.} \end{cases}$$

The baseline cost for computing $X_j$ is one square-root extraction to compute $Y$, two tests for squaredness, one squaring and one multiplication in $\mathbb{F}_q$ to compute each $g(X_j)$ for pairing-friendly curves. Testing for squaredness in $\mathbb{F}_{p^k}$ costs 1 Legendre symbol computation, $(k-1)$ Frobenius $p^k$-powers and $(k-1)$ multiplications in $\mathbb{F}_{p^k}$ [AR14]. Multiplications by $\omega$ or $\tau$ consist in $k$ multiplications in $\mathbb{F}_p$, since the constants lie in the base field. Under the guarantee that at least one of the $g(X_j)$ is a square, we can initially assume that $g(X_1)$ is a square and update the choice of $X_j$ after testing the other two values with one symbol computation each. For curves with either $a=0$ or $b=0$, we can evaluate the curve equation with one squaring and one multiplication in $\mathbb{F}_q$. Below we discuss the various cases in more details and compute the total operation counts.

**The case $b=0$.** We have two subcases in our curve selection. For $\mathbb{G}_2$, we have that multiplicative twists with coefficient $a' = \xi$, for some small non-residue $\xi$ in a subfield, allowing for multiplications by $a'$ to be cheap and evaluated with additions only. By substituting $b=0$ in the expressions above, after optimizing for common subexpressions and using Montgomery's simultaneous inversion technique, we can evaluate the composition $(f \circ \eta \circ h)$ at the cost of 1 square-root, 2 Legendre symbols and $5\mathbf{s}_{k/d} + 19\mathbf{m}_{k/d} + 5(k/d)\mathbf{m} + \mathbf{i}_{k/d} + ((k/d) - 1)(\mathbf{f}_{k/d} + \mathbf{m}_{k/d})$ while adding the baseline costs to evaluating the formulas:

$$\begin{align*} h_0 &= t_1^2, & h_1 &= h_0^2, & h_2 &= 4a', & h_3 &= 64a'^3, & h_4 &= h_0h_1 + h_3, & h_5 &= t_2^2, & h_6 &= \tau t_1 \\ h_7 &= 24h_0h_5h_6, & h_8 &= h_0h_3, & h_9 &= h_1^2, & h_{10} &= \omega(4a'h_4 + h_0h_7) \\ d_1 &= -2h_6\omega(h_4 + h_7), & d_2 &= d_1\omega, & d_3 &= -432(h_0 - h_2)^2h_1h_5 \\ n_1 &= h_9 + h_8 + 4a'h_7 + h_{10}\omega, & n_2 &= h_9 + h_8 + 4a'h_7 + h_{10} \\ n_3 &= h_1(h_9 + 2h_8) + 4096a'^6 - h_7(h_4 - 12a'(h_1 + 4a'h_0) - h_7). \end{align*}$$

By further specializing to the case $a=1$ for $\mathbb{G}_1$, the formulas cost 1 square-root, 2 Legendre symbols and $5\mathbf{s} + 23\mathbf{m} + \mathbf{i}$:

$$\begin{align*} h_0 &= t_1^2, & h_1 &= h_0^2, & h_4 &= h_1h_0 + 64, & h_5 &= t_2^2, & h_6 &= \tau t_1 \\ h_7 &= 24h_0h_5h_6, & h_9 &= h_1^2, & h_{10} &= \omega(4h_4 + h_0h_7) \\ d_1 &= -2h_6\omega(h_4 + h_7), & d_2 &= d_1\omega, & d_3 &= -432(h_0 - 4)^2h_1h_5 \\ n_1 &= h_9 + 4(16h_0 + h_7) + h_{10}\omega, & n_2 &= h_9 + 4(16h_0 + h_7) + h_{10} \\ n_3 &= h_1(h_9 + 8(16h_0)) + 4096 - h_7(h_4 - 3(4h_1 + 16h_0) - h_7). \end{align*}$$

**The case $a=0$.** For this case, we turn instead to the SwiftEC algorithm, which can be evaluated through 1 square-root extraction, 2 Legendre symbol computations and the additional costs of $7\mathbf{s}_{k/d} + 11\mathbf{m}_{k/d} + (k/d)\mathbf{m} + \mathbf{i}_{k/d} + ((k/d) - 1)(\mathbf{f}_{k/d} + \mathbf{m}_{k/d})$ in $\mathbb{G}_2$, and $7\mathbf{s} + 12\mathbf{m} + \mathbf{i}$ in $\mathbb{G}_1$:

$$\begin{align*} h_0 &= t_1^3, & h_1 &= t_2^2, & h_2 &= h_0 + b - h_1, & h_3 &= 2h_1 + h_2, & h_6 &= \tau t_1, & h_7 &= h_0h_6, & h_8 &= 2h_6t_2 \\ d_1 &= 2h_3h_8, & n_1 &= h_8(h_7 - t_1h_3), & n_2 &= (2h_3)^2 \\ X_1 &= n_1/d_1, & X_2 &= -t_1 - n_1/d_1, & X_3 &= t_1 + (n_2/d_1)^2. \end{align*}$$
### 4.2.1 Cofactor clearing for $\mathbb{G}_1$.

As in Section 2, we denote $c_1$ the cofactor of the curve, that is, $\#E(\mathbb{F}_p) = c_1 \cdot r$, and define the cofactor clearing operation as

$$ 
\begin{aligned}
E(\mathbb{F}_p) & \to \mathbb{G}_1 \\
P & \mapsto [c_1]P
\end{aligned}
 $$

In Appendix B Table 22 we give the parameterized formulas for the cofactor $c_1$ of $\mathbb{G}_1$. Because $c_1$ might be quite large, there are two strategies to speed-up the multiplication-by-c1 map $[c_1]$. First, the curves admit an endomorphism for fast GLV scalar multiplication. Second, when the cofactor $c_1$ has some square factor $n_1^2$ satisfying the properties of Schoof's [Sch87, Proposition 3.7] (also in [EHG22, Theorem 1]), the strategy of Wahby-Boneh applies [WB19] (multiplying by $n_1$ instead of $n_1^2$).

It is important to note that the two techniques (GLV and Wahby-Boneh) are orthogonal w.r.t. the $\mathbb{F}_p$-rational curve endomorphism $\phi$. In other words, we cannot combine the two techniques, we apply them respectively on disjoint subgroups. Following [HGP22], we aim at obtaining the structure of $E(\mathbb{F}_p)$ so as to identify the respective subgroups where to apply each technique:

$$ E(\mathbb{F}_p) \simeq \mathbb{Z}/n_1\mathbb{Z} \oplus \mathbb{Z}/n_2\mathbb{Z}, \quad n_1 \mid n_2 \qquad (2) $$

so that $E[n_1] \subset E(\mathbb{F}_p)$, $n_1^2 \mid E(\mathbb{F}_p)$. In our context, we know that $r$ is prime, and $r^2$ does not divide the curve order over $\mathbb{F}_p$, so that $r$ divides $n_2$ in Eq. (2) that we rewrite as

$$ E(\mathbb{F}_p) \simeq \mathbb{Z}/n_1\mathbb{Z} \oplus \mathbb{Z}/n_1c_1'r\mathbb{Z}, \quad n_1^2c_1' = c_1. \qquad (3) $$

We apply the Wahby-Boneh technique to clear the square factor $n_1^2$, followed by the GLV technique to clear the factor $c_1' = \#E(\mathbb{F}_p)/(n_1^2r)$.

**Faster co-factor clearing with the GLV method.** To improve the cofactor clearing step, one would like to use the endomorphism $\phi$. For that one needs to identify the cyclic subgroup of $E(\mathbb{F}_p)$ stable under $\phi$, so that $\phi$ acts as a multiplication by an eigenvalue $\lambda_\phi$. With the notations above, this subgroup has order $c_1' = \#E(\mathbb{F}_p)/(n_1^2r)$. We compute in SageMath the parameters: eigenvalue $\lambda_\phi$ modulo $c_1'$, short scalars $(a_0, a_1)$ so that $a_0 + a_1\lambda_\phi$ is a multiple of $c_1'$. The multiplication-by-$c_1'$ map becomes

$$ 
\begin{aligned}
E(\mathbb{F}_p) & \to E(\mathbb{F}_p) \\
P & \mapsto [a_0]P + [a_1]\phi(P).
\end{aligned}
 $$

**Faster co-factor clearing with the Wahby-Boneh technique and Schroof's theorem.** We apply the Wahby-Boneh technique to the appropriate subgroup of order $n_1$ (Eq. (2)), which satisfies the conditions of Theorem 1. We compute in SageMath the parameter $n_1$ for each curve.

**Theorem 1** ([Sch87, Proposition 3.7]). Let $E$ be an elliptic curve over $\mathbb{F}_p$ and $n_1 \in \mathbb{Z}_{\ge 1}$ with $p \nmid n_1$. Let $\pi_p$ denote the Frobenius endomorphism of $E$ and its trace. Then,

$$ E[n_1] \subset E(\mathbb{F}_p) \iff \left\{ 
\begin{array}{l}
n_1^2 \mid \#E(\mathbb{F}_p), \\
n_1 \mid p-1 \text{ and} \\
\pi_p \in \mathbb{Z} \text{ or } \mathcal{O}(\frac{t^2-4p}{n_1^2}) \subset \mathrm{End}_{\mathbb{F}_p}(E).
\end{array}
\right. $$

To conclude, we are looking for a decomposition of the curve order so that the Wahby-Boneh technique applies to $n_1$ and the GLV technique applies to $c_1'$:

$$ \#E(\mathbb{F}_p) = \underbrace{n_1^2 \cdot c_1' \cdot r}_{=c_1} . \qquad (4) $$
### 4.2.2 Cofactor clearing for $\mathbb{G}_2$

Recently Dai, Kaizhan, Zhao and Zhou [DLZZ23] extended on finding efficient formulas and provided a Magma script [Dai23]. We rely on their work to obtain the formulas for our curves. As the formulas are quite long for $\mathbb{G}_2$, we implemented them in SageMath to validate the equations. The general strategy is the same as for $\mathbb{G}_1$, but with $\psi$ instead. Note that [FAG20] investigated SG curves.

## 4.3 Subgroup membership testing

The authors in [DLZZ23] consider subgroup membership testing on pairing-friendly curves and generalize Scott's technique [Sco21]. The strategy dates back to GLV idea and for $\mathbb{G}_1$ it consists in finding a short vector $(a_0, a_1)$ such that $a_0 + a_1\lambda_\phi \equiv 0 \pmod{r}$, then testing if $[a_0]P + [a_1]\phi(P) = \mathcal{O}$. Dai, Kaizhan, Zhao and Zhou solve the problem for KSS16 and KSS18 curves where the textbook formula of short vector $(a_0, a_1) = (1, \lambda_\phi \pmod{r})$, resp. $(1, \lambda_\phi + 1 \pmod{r})$ induces a multiplication by a multiple of $r$ but which is not coprime to the cofactor $c_1$. Moreover they obtain a generic technique that can be applied to all curves for $\mathbb{G}_1$ and $\mathbb{G}_2$. We apply their criterion [DLZZ23, Theorem 1] to our curves in Table 12 and solve the problem of cofactors for $\mathbb{G}_1$ in Table 16.

### 4.3.1 Subgroup membership testing in $\mathbb{G}_1$

**Theorem 2** ([DLZZ23, Theorem 3] $\mathbb{G}_1$ for $j = 0$ or $j = 1728$ curves). Let $E$ be an ordinary elliptic curve defined over a finite field $\mathbb{F}_q$ with $j$-invariant 0 or 1728, and $r$ a large prime such that $r \nmid \#E(\mathbb{F}_q)$. Let $\phi$ be a GLV endomorphism on $E$, and act as multiplication by an integer $\lambda_\phi$ in $\mathbb{G}_1$. Let $(a_0, a_1) \in \mathbb{Z}^2$ with $a_0 + a_1 \cdot \lambda_\phi \equiv 0 \pmod{r}$. Assume

* $\gcd(a_0^2 - a_0a_1 + a_1^2, \#E(\mathbb{F}_q)) = r$, if $j(E) = 0$,

* $\gcd(a_0^2 + a_1^2, \#E(\mathbb{F}_q)) = r$, if $j(E) = 1728$.

Given a non-zero point $P \in E(\mathbb{F}_q)$, then

$$P \in \mathbb{G}_1 \text{ if and only if } [a_0]P + [a_1]\phi(P) = \mathcal{O}.$$

For $\mathbb{G}_1$ membership testing there is a problem for KSS-like curves (KSS16, KSS18, GG20, GG28). The naive vector is $(a_0, a_1) = (1, \lambda_\phi \pmod{r})$ ($D = 1$), resp. $(a_0, a_1) = (1, \lambda_\phi + 1 \pmod{r})$ ($D = 3$) or the half-gcd of $(r, \lambda_\phi)$. To apply the criterion of Theorem 2, one computes $a_0^2 + a_1^2 = 1 + \lambda_\phi^2$, resp. $a_0^2 - a_0a_1 + a_1^2 = 1 + \lambda_\phi + \lambda_\phi^2$ but this value is not coprime to the cofactor $c_1$ (see Table 12). In other words if there is a common divisor $c_i$ of $\text{Res}(\chi_\phi(X), a_0 + a_1X)$ and $c_1$, the test returns true for points of order a divisor $c_i r$ (e.g. $1250r$, resp. $343r$ for KSS16 and KSS18), but it should returns true only for points of order exactly $r$. For KSS16 curves, testing for $P + [\lambda_\phi \pmod{r}]\phi(P)$ being $\mathcal{O}$ only answers if $P$ has order a divisor of $1250r$, and for KSS18 curves, testing for $P + [\lambda_\phi + 1 \pmod{r}]\phi(P)$ being $\mathcal{O}$ only answers if $P$ has order a divisor of $343r$. The problem is similar with GG20 and GG28 curves. It means that the naive vector $(a_0, a_1)$ is not as short as possible. There are two strategies to reduce the basis, one experimental involving LLL in [DLZZ23] and one theoretical involving shrinking a basis of a vector space in [Smi15]. We summarise our results in Table 16.

### 4.3.2 Subgroup membership testing for $\mathbb{G}_2$

**Theorem 3** ([DLZZ23, Theorem 1] $\mathbb{G}_2$ for curves with a twist). Let $E$ be an ordinary elliptic curve over $\mathbb{F}_p$ and $t$ the trace of the Frobenius endomorphism $\pi$. Let $\phi: E' \to E$ be the twisting isomorphism, where $E'$ is defined over $\mathbb{F}_{p^e}$. Let $r$ be a large prime such
<table><caption>**Table 12:** Naive $\mathbb{G}_1$ subgroup membership testing. The eigenvalue of the endomorphism $\phi$ is denoted $\lambda_{\phi}$. It assumes testing if $[a_0]P + [a_1]\phi(P)$ is the point at infinity. The $(a_0, a_1)$ are obtained with a half-gcd on $(r(x), \lambda_{\phi}(x))$ if $2\deg(\lambda_{\phi}(x)) > \deg(r(x))$.</caption><thead><tr><th>Curve</th><th>&lambda;<sub>&phi;</sub> mod r(x)</th><th>(a<sub>0</sub>, a<sub>1</sub>)</th><th>DLZZ criterion [DLZZ23]</th></tr></thead><tbody><tr><td>BLS12</td><td>x<sup>2</sup> &minus; 1</td><td>(1, x<sup>2</sup>)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>BLS15</td><td>x<sup>5</sup></td><td>(x<sup>3</sup> &minus; x<sup>2</sup> + 1, x<sup>4</sup> &minus; x<sup>2</sup> + x)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>FM15</td><td>x<sup>5</sup></td><td>(x<sup>3</sup> &minus; x<sup>2</sup> + 1, x<sup>4</sup> &minus; x<sup>2</sup> + x)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>KSS16</td><td>(x<sup>4</sup> + 24)/7</td><td>(1, (x<sup>4</sup> + 24)/7)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = 1250r</td></tr><tr><td>FM16</td><td>x<sup>4</sup></td><td>(1, x<sup>4</sup>)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>AFG16</td><td>x<sup>4</sup></td><td>(1, x<sup>4</sup>)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>KSS18</td><td>x<sup>3</sup> + 18</td><td>(1, x<sup>3</sup> + 19)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = 343r</td></tr><tr><td>SG18</td><td>9x<sup>3</sup> + 1</td><td>(1, 9x<sup>3</sup> + 2)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = 3r</td></tr><tr><td>FM18</td><td>x<sup>3</sup> &minus; 1</td><td>(1, x<sup>3</sup>)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>FST20</td><td>x<sup>5</sup></td><td>(x<sup>4</sup> &minus; x<sup>2</sup> + 1, x<sup>3</sup> &minus; x)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>SG20</td><td>8x<sup>5</sup> + 1</td><td>(2x<sup>3</sup> + 2x<sup>2</sup> + x, 4x<sup>4</sup> + 2x<sup>3</sup> &minus; x &minus; 1)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>GG20a</td><td>(x<sup>5</sup> + 38)/41</td><td>(x<sup>4</sup> + 2x<sup>3</sup> + 3x<sup>2</sup> + 2x &minus; 7, x<sup>3</sup> + 4x<sup>2</sup> + 11x + 24)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = 41 &middot; 5<sup>4</sup>r</td></tr><tr><td>GG20b</td><td>(x<sup>5</sup> &minus; 38)/41</td><td>(x<sup>4</sup> &minus; 2x<sup>3</sup> + 3x<sup>2</sup> &minus; 2x &minus; 7, x<sup>3</sup> &minus; 4x<sup>2</sup> + 11x &minus; 24)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = 41 &middot; 5<sup>4</sup>r</td></tr><tr><td>BLS21</td><td>x<sup>7</sup></td><td>(x<sup>6</sup> &minus; x<sup>4</sup> + x<sup>3</sup> &minus; x + 1, x<sup>5</sup> &minus; x<sup>4</sup> + x<sup>2</sup> &minus; x)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>BLS24</td><td>x<sup>4</sup> &minus; 1</td><td>(1, x<sup>4</sup>)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>BLS27</td><td>x<sup>9</sup></td><td>(1, x<sup>9</sup> + 1)</td><td>gcd(a<sub>0</sub><sup>2</sup> &minus; a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup>, r &middot; h) = 3r</td></tr><tr><td>FST28</td><td>x<sup>7</sup></td><td>(x<sup>5</sup> &minus; x<sup>3</sup> + x, x<sup>6</sup> &minus; x<sup>4</sup> + x<sup>2</sup> &minus; 1)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = r</td></tr><tr><td>GG28</td><td>(x<sup>7</sup> + 278)/29</td><td>(x<sup>5</sup> + 4x<sup>4</sup> + 11x<sup>3</sup> + 24x<sup>2</sup> + 41x + 44, x<sup>6</sup> + 2x<sup>5</sup> + 3x<sup>4</sup> + 2x<sup>3</sup> &minus; 7x<sup>2</sup> &minus; 38x &minus; 117)</td><td>gcd(a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup>, r &middot; h) = 29r</td></tr></tbody></table>

that $r\|\#E(\mathbb{F}_p)$ and $r\|\#E'(\mathbb{F}_{p^e})$. Define $\psi = \phi^{-1}\circ\pi\circ\phi$ with the characteristic polynomial $g(\psi) = \psi^2 - t\cdot\psi + p$. Let $\eta = \sum_{i=0}^s c_i \cdot p^i$ be a multiple of $r$ and $f(\psi) = \sum_{i=0}^s c_i \psi^i$ a polynomial with respect to $\psi$. Denote by $b_0 + b_1\psi$ the remainder for $f(\psi)$ divided by $g(\psi)$, i.e.,

$$b_0 + b_1\psi = f(\psi) \mod g(\psi). \qquad (5)$$

Assume

$$\gcd(b_0^2 + b_0b_1t + b_1^2p, \#E'(\mathbb{F}_{p^e})) = r. \qquad (6)$$

Given a non-identity point $Q \in E'(\mathbb{F}_{p^e})$, then $Q \in \mathbb{G}_2 = E'(\mathbb{F}_{p^e})[r]$ if and only if $f(\psi)(Q) = O_{E'}$.

As noted in [DLZZ23], the formulas for optimal ate pairing computation and fast $\mathbb{G}_2$ membership testing are very similar. For the optimal ate pairing, the formula parameters should satisfy

$$\sum_{i=0}^{\ell} c_i q^i = m \cdot r \text{ and } mkq^{k-1} \not\equiv \frac{q^k - 1}{r} \sum_{i=0}^{\ell} ic_i q^{i-1} \mod r \qquad (7)$$
<table><caption>**Table 13:** $\mathbb{G}_1$ cofactor clearing, where $\lambda_\phi$ is the eigenvalue of the endomorphism $\phi$, $\lambda_\phi \mod c'_1$ is given such that $\lambda_\phi \mod r$ matches the data in Table 12, the short vector $(a_0, a_1)$ means evaluating $R \leftarrow [a_0]P + [a_1]\phi(P)$. BLS12, AFG16, SG18, BLS24, BLS27 have a fully-rational torsion subgroup.</caption><thead><tr><th>Curve</th><th>λ<sub>φ</sub> mod c'<sub>1</sub>(x)</th><th>short vector (a<sub>0</sub>, a<sub>1</sub>)</th><th>criterion</th></tr></thead><tbody><tr><td>BLS15</td><td>-x - 1</td><td>(1, -x)</td><td>a<sub>0</sub><sup>2</sup> - a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup> = c'<sub>1</sub></td></tr><tr><td>FM15</td><td>(6x<sup>4</sup> + 3x<sup>3</sup> + 2x<sup>2</sup> - 4x - 8)/7</td><td>((3x<sup>3</sup> + 2x<sup>2</sup> - 4x)/3, (4x<sup>2</sup> - 2x - 3)/3)</td><td>a<sub>0</sub><sup>2</sup> - a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup> = c'<sub>1</sub></td></tr><tr><td>KSS16</td><td>±(x + 1)/2</td><td>(1, λ<sub>φ</sub> mod c<sub>1</sub>)</td><td>a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup> = c<sub>1</sub>/250</td></tr><tr><td>FM16</td><td>x<sup>3</sup></td><td>(1, λ<sub>φ</sub> mod c'<sub>1</sub>)</td><td>a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup> = c'<sub>1</sub></td></tr><tr><td>KSS18</td><td>x + 2, -x - 3</td><td>(1, λ<sub>φ</sub> + 1 mod c<sub>1</sub>)</td><td>a<sub>0</sub><sup>2</sup> - a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup> = 3/49c<sub>1</sub></td></tr><tr><td>FM18</td><td>- (3x<sup>5</sup> + 3x<sup>4</sup> + 3x<sup>3</sup> + x)/2</td><td>(2(x - 1)/3, x<sup>3</sup> + (x - 1)/3)</td><td>a<sub>0</sub><sup>2</sup> - a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup> = c<sub>1</sub></td></tr><tr><td>FST20</td><td>x</td><td>(1, x)</td><td>a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup> = c'<sub>1</sub></td></tr><tr><td>SG20</td><td>-4x<sup>3</sup> + x</td><td>(2x<sup>2</sup> - 1, x)</td><td>a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup> = c'<sub>1</sub></td></tr><tr><td>GG20b</td><td>x + 2 mod x<sup>2</sup> + 4x + 5</td><td>(1, x + 2)</td><td>a<sub>i0</sub><sup>2</sup> + a<sub>i1</sub><sup>2</sup> = c'<sub>i1</sub></td></tr><tr><td></td><td>(1 - x)/2 mod (x<sup>2</sup> - 2x + 5)/4</td><td>(1, (1 - x)/2)</td><td></td></tr><tr><td>BLS21</td><td>x</td><td>(1, x + 1)</td><td>a<sub>0</sub><sup>2</sup> - a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup> = 3c'<sub>1</sub></td></tr><tr><td>FST28</td><td>-x</td><td>(1, -x)</td><td>a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup> = c'<sub>1</sub></td></tr><tr><td>GG28</td><td>2 - x mod x<sup>2</sup> - 4x + 5</td><td>(1, 2 - x)</td><td>a<sub>i0</sub><sup>2</sup> + a<sub>i1</sub><sup>2</sup> = c'<sub>i1</sub></td></tr><tr><td></td><td>(1 - x)/2 mod (x<sup>2</sup> - 2x + 5)/4</td><td>(1, (1 - x)/2)</td><td></td></tr></tbody></table>

for some non-zero integer $m$ and short integers $c_i$ [Ver10, Theorem 1].

As explained in [Smi15, HGP22, DLZZ23], the points on the $d$-th twist $E'(\mathbb{F}_{p^{k/d}})$ containing $\mathbb{G}_2$ have eigenvalue $\lambda_\psi$ under Galbraith-Scott endomorphism $\psi = \tau^{-1} \circ \pi \circ \tau$, where $\lambda_\psi$ is a root of the characteristic polynomial $\chi_\psi(X) = X^2 - tX + p$, with the trace $t$ of $E(\mathbb{F}_p)$. A point in $\mathbb{G}_2$ has eigenvalue $\lambda_\psi \mod r = p \mod r = t - 1 \mod r$ under $\psi$. But for subgroup membership testing, one cannot assume that the point being tested has eigenvalue $t-1$, one relies on the generic formula of $\lambda_\psi$ the root of $\chi_\psi(X)$ modulo the curve order which maps to $t-1$ when reduced modulo $r$. One checks that the resultant of $\chi_\psi(X)$ and the polynomial formula $f(X) = c_0 + c_1X + \dots + c_\ell X^\ell$ (see eq. (7)) has no common factor with the cofactor $c_2$ of $\mathbb{G}_2$, that is, $\mathrm{Res}_x(\mathrm{Res}_X(\chi_\psi(X), f(X)), c_2(x)) \neq 0$ [DLZZ23, Theorem 1]. The result is a rational number. The final step is to check that $c_2(x)$ has no root modulo each prime divisor of the numerator of that result.

We start from the data in Table 6 and check if Theorem 3 is satisfied. The authors in [DLZZ23] already solved the case for KSS16 with $x = 45 \mod 70$, and KSS18, see Table 15.

**BLS curves.** All BLS curves have a trace $t = u + 1$, so that the curve order is $p + 1 - t = p - u$, and this number is a multiple of the prime order $r$ of $\mathbb{G}_1$. The optimal ate pairing formula is based on the equation $u - p = 0 \mod r$. For BLS12 and BLS24 curves, this equation directly gives a $\mathbb{G}_2$ membership test: as soon as $r = \Phi_k(u)$ is prime (it corresponds to $\gcd(c_1, c_2) = 1$), $Q \in \mathbb{G}_2 \iff [u]Q - \psi(Q) = O$ that is, $Q \in \mathbb{G}_2 \iff [u]Q = \psi(Q)$. This is not the case for BLS15, BLS21 nor BLS27 curves.

**BLS12, BLS24 curves.** Solutions appear already in previous works [Sco21, HGP22, DLZZ23]. Assuming that the order $r$ of $\mathbb{G}_1, \mathbb{G}_2$ is prime and $\gcd(c_1, c_2) = 1$ (the cofactors of $\mathbb{G}_1$ and $\mathbb{G}_2$ respectively are coprime), the test is $[u]Q = \psi(Q)$.
<table><caption>**Table 14:** $\mathbb{G}_1$ cofactor clearing formula according to Table 13.</caption><thead><tr><th>Curve</th><th>cofactor clearing</th></tr></thead><tbody><tr><td>BLS12</td><td>R &larr; (x &minus; 1)P</td></tr><tr><td>BLS15</td><td>Q &larr; (x &minus; 1)P; R &larr; Q &minus; [x]&phi;(Q)</td></tr><tr><td>FM15</td><td>Q &larr; [x]P; R &larr; [a<sub>0</sub>]Q + [a<sub>1</sub>]&phi;(Q)</td></tr><tr><td>KSS16</td><td>Q &larr; P + [&lambda;<sub>&phi;</sub> mod c<sub>1</sub>]&phi;(P); R &larr; 1250Q</td></tr><tr><td>FM16</td><td>Q &larr; [x/2]P; R &larr; Q + [x<sup>3</sup>]&phi;(Q)</td></tr><tr><td>AFG16</td><td>R &larr; [x(x<sup>3</sup> + 1)/2]P</td></tr><tr><td>KSS18</td><td>Q &larr; P + [&lambda;<sub>&phi;</sub> + 1 mod c<sub>1</sub>]&phi;(P); R &larr; 343Q</td></tr><tr><td>SG18</td><td>R &larr; [3x<sup>2</sup> &minus; 1]P</td></tr><tr><td>FM18</td><td>Q &larr; [(x &minus; 1)/3]P; R &larr; [3(x<sup>2</sup> + x + 1)]Q + Q + P + [2]&phi;(Q)</td></tr><tr><td>FST20</td><td>Q &larr; [(x &minus; 1)/2]P; R &larr; Q + [x]&phi;(Q)</td></tr><tr><td>SG20</td><td>Q &larr; [2x]P; R &larr; [2x<sup>2</sup> &minus; 1]Q + &phi;([x]Q)</td></tr><tr><td>GG20b</td><td>Q<sub>1</sub> &larr; [20]P; Q<sub>2</sub> &larr; [8]([2]Q<sub>1</sub> + Q<sub>1</sub> + &phi;(Q<sub>1</sub>)) &minus; &phi;(Q<sub>1</sub>); Q<sub>3</sub> &larr; Q<sub>2</sub> + [x + 2]&phi;(Q<sub>2</sub>); R &larr; Q<sub>3</sub> + [(1 &minus; x)/2]&phi;(Q<sub>3</sub>)</td></tr><tr><td>BLS21</td><td>Q &larr; [x &minus; 1]P; R &larr; Q + [x + 1]&phi;(Q)</td></tr><tr><td>BLS24</td><td>R &larr; (x &minus; 1)P</td></tr><tr><td>BLS27</td><td>R &larr; (x &minus; 1)P</td></tr><tr><td>FST28</td><td>Q &larr; [(x &minus; 1)/2]P; R &larr; Q &minus; [x]&phi;(Q)</td></tr><tr><td>GG28</td><td>Q &larr; P + [2 &minus; x]&phi;(P); R &larr; Q + [(1 &minus; x)/2]&phi;(Q)</td></tr></tbody></table>

<table><caption>**Table 15:** From [DLZZ23, Table 2]. Note that for KSS18 $\mathbb{G}_2$, we translate the short vector $(2x/7, 1, 0, x/7, 0, 0)$ to $(0, 0, 2x/7, 1, 0, x/7)$ otherwise $\sum_i a_i \mu_r^i$ produces 0, not a multiple of $r(x)$. For KSS16, we use the data from [DLZZ23, §5.2.2].</caption><thead><tr><th>Curve</th><th>G<sub>i</sub></th><th>short vector (a<sub>i</sub>)</th><th>criteria</th></tr></thead><tbody><tr><td>BN</td><td>G<sub>2</sub></td><td>(x + 1, x, x, -2x)</td><td></td></tr><tr><td>BLS12</td><td>G<sub>2</sub></td><td>(x, -1, 0, 0)</td><td></td></tr><tr><td rowspan="3">KSS16</td><td>G<sub>1</sub></td><td>((31x<sup>4</sup> + 625)/8750, -(17x<sup>4</sup> + 625)/8750)</td><td>a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup> = r, a<sub>0</sub> + a<sub>1</sub>(&lambda;<sub>&phi;</sub> mod r) = -17r</td></tr><tr><td></td><td>=( (31(x/5)<sup>4</sup> + 1)/14, -(17(x/5)<sup>4</sup> + 1)/14</td><td>-31a<sub>1</sub> - 1 + 17a<sub>1</sub>(&lambda;<sub>&phi;</sub> mod r) = -17<sup>2</sup>r</td></tr><tr><td>G<sub>2</sub></td><td>1/70(-11x + 5, 9x + 15, -3x - 5, -3x - 5, 13x - 25, -7x + 35, -x - 25, -11x + 5)</td><td>&sum;<sub>i</sub> a<sub>i</sub> &mu;<sub>i</sub><sup>i</sup> = 127r</td></tr><tr><td rowspan="2">KSS18</td><td>G<sub>1</sub></td><td>((x/7)<sup>3</sup>, -18(x/7)<sup>3</sup> - 1)</td><td>a<sub>0</sub><sup>2</sup> - a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup> = r, a<sub>0</sub> + a<sub>1</sub>(&lambda;<sub>&phi;</sub> mod r) = -18r</td></tr><tr><td>G<sub>2</sub></td><td>(0, 0, 2x/7, 1, 0, x/7)</td><td>a<sub>2</sub>&mu;<sup>2</sup> + a<sub>3</sub>&mu;<sup>3</sup> + a<sub>5</sub>&mu;<sup>5</sup> = -18r</td></tr></tbody></table>

**BLS15, BLS21 curves.** This case is different as the gcd of $c_1$ and $c_2$ is $x^2 + x + 1$. For BLS15, note that $\Phi_{15}(p) = p^8 - p^7 + p^5 - p^4 + p^3 - p + 1$. Then $p^7(x - p) = xp^7 - p^8 = 1 - p + p^3 - p^4 + p^5 + (x - 1)p^7 \mod \Phi_{15}(p)$ and this formula satisfies Theorem 3. That is, the $\mathbb{G}_2$ membership test is $Q - \psi(Q) + \psi^3(Q) - \psi^4(Q) + \psi^5 + [u - 1]\psi^7(Q) = \mathcal{O}$. When $7 | h_2$, this test still does not distinguish points of order $7r$. For BLS21, note that $\Phi_{21}(p) = p^{12} - p^{11} + p^9 - p^8 + p^6 - p^4 + p^3 - p + 1$. Then $p^{11}(x - p) = xp^{11} - p^{12} = 1 - p + p^3 - p^4 + p^6 - p^8 + p^9 + (x - 1)p^{11} \mod \Phi_{21}(p)$ and this formula succeeds in Theorem 3 when $c_2$ is odd. The $\mathbb{G}_2$ membership test is $Q - \psi(Q) + \psi^3(Q) - \psi^4(Q) + \psi^6 - \psi^8(Q) + \psi^9(Q) + [u - 1]\psi^{11}(Q) = \mathcal{O}$.

**BLS27 curves.** The gcd of the resultant and $c_2$ is 3 with the formula $(u, -1)$. The formula $p^{17}(u - p) = 1 + p^9 + up^{17} \mod \Phi_{27}(p)$ does not solve the problem of the cofactor 3. With Smith technique we obtain that $(1 + p + p^2 + \dots + p^8)(1 - p^9)(1 - u)/3 + p^9$ is a multiple of $r$ and avoids the cofactor 3 issue. The $\mathbb{G}_2$ membership test is $[(1 - u)/3](S - \psi^9(S)) + \psi^9(Q) = \mathcal{O}$ where $S \leftarrow Q + \psi(Q) + \psi^2(Q) + \dots + \psi^8(Q)$.
<table><caption>**Table 16:** $\mathbb{G}_1$ membership testing, solving the issues in Table 12. The endomorphism $\phi$ has eigenvalue $\lambda_\phi$, the short vector $(a_0, a_1)$ satisfies $a_0^2+a_1^2 = r$ ($j = 1728$), resp. $a_0^2-a_0a_1+a_1^2 = r$ ($j = 0$), where $a_0, a_1$ are integers. Note that for KSS16, $x \equiv 25, 45 \pmod{70}$ hence $5 \mid x$; for KSS18, $x \equiv 14 \pmod{21}$ hence $7 \mid x$; for GG20b, $x \equiv 1465, 1565 \pmod{2050}$ hence $5 \mid x$.</caption><thead><tr><th>Curve</th><th>&lambda;<sub>&phi;</sub> mod r</th><th>(a<sub>0</sub>, a<sub>1</sub>) s.t. a<sub>0</sub><sup>2</sup> + a<sub>1</sub><sup>2</sup> = r, resp. a<sub>0</sub><sup>2</sup> - a<sub>0</sub>a<sub>1</sub> + a<sub>1</sub><sup>2</sup> = r</th><th>observation</th></tr></thead><tbody><tr><td>KSS16</td><td>(x<sup>4</sup> + 24)/7</td><td>((-443(x/5)<sup>4</sup> - 17)/14, ((x/5)<sup>4</sup> + 5)/14)</td><td>a<sub>0</sub> = -443a<sub>1</sub> + 157</td></tr><tr><td>KSS18</td><td>x<sup>3</sup> + 18</td><td>(19(x/7)<sup>3</sup> + 1, (x/7)<sup>3</sup>)</td><td>a<sub>0</sub> = 19a<sub>1</sub> + 1</td></tr><tr><td>SG18</td><td>9x<sup>3</sup> + 1</td><td>(-3x<sup>3</sup>, 3x<sup>3</sup> + 1)</td><td>a<sub>1</sub> = -a<sub>0</sub> + 1</td></tr><tr><td>GG20b</td><td>(x<sup>5</sup> - 38)/41</td><td>((61(x/5)<sup>4</sup> - 54(x/5)<sup>3</sup> + 31(x/5)<sup>2</sup> - 14(x/5) + 5)/41, (148(x/5)<sup>4</sup> - 47(x/5)<sup>3</sup> + 8(x/5)<sup>2</sup> + 3(x/5) - 4)/41)</td><td>u = 30 mod 41</td></tr><tr><td></td><td></td><td>((92(x/5)<sup>4</sup> - 63(x/5)<sup>3</sup> + 32(x/5)<sup>2</sup> - 13(x/5) + 4)/41), (131(x/5)<sup>4</sup> - 34(x/5)<sup>3</sup> + (x/5)<sup>2</sup> + 6(x/5) - 5)/41</td><td>u = 7 mod 41</td></tr><tr><td>BLS27</td><td>x<sup>9</sup></td><td>((-x<sup>9</sup> + 1)/3, (x<sup>9</sup> + 2)/3)</td><td>a<sub>1</sub> = -a<sub>0</sub> + 1</td></tr><tr><td>GG28</td><td>(x<sup>7</sup> + 278)/29</td><td>((2x<sup>6</sup> + 9x<sup>5</sup> + 26x<sup>4</sup> + 59x<sup>3</sup> + 106x<sup>2</sup> + 129x - 14)/29, (5x<sup>6</sup> + 8x<sup>5</sup> + 7x<sup>4</sup> - 12x<sup>3</sup> - 83x<sup>2</sup> - 272x - 673)/29)</td><td>u = 14 mod 29</td></tr><tr><td></td><td></td><td>((5x<sup>6</sup> + 12x<sup>5</sup> + 23x<sup>4</sup> + 32x<sup>3</sup> + 13x<sup>2</sup> - 108x - 497)/29, (2x<sup>6</sup> - x<sup>5</sup> - 14x<sup>4</sup> - 51x<sup>3</sup> - 134x<sup>2</sup> - 281x - 454)/29)</td><td>u = 19 mod 29</td></tr></tbody></table>

**FM15 curves.** The formula for optimal ate pairing is $u - p^4$ (Table 6). The gcd in $\mathbb{Q}[u]$ of $\text{Res}_X(X^2 - t(u)X + p(u), u - X^4)$ and $\#E'(\mathbb{F}_{p^5}) = h_2(u)r(u)$ is $r(u)$. Following [HGP22], we then compute

$$ \text{Res}_u(\text{Res}_X(X^2 - t(u)X + p(u), u - X^4)/r(u), h_2(u)) $$

and obtain a very large number whose small factors are $2^4 \cdot 1372471$. We observe that $\text{Res}_X(u)$ and $h_2(u)$ share the irreducible factor $(u^2 + u + 1)$ modulo 2 but do not share a common root. Actually, the resultant $\text{Res}_X(u)$ cannot be even. This ensures that the test based on the optimal ate pairing formula: whether $[u]Q - \psi^4(Q) = \mathcal{O}$ is a valid $\mathbb{G}_2$ subgroup membership test.

**KSS16 curves.** An optimal pairing formula can be $x/5p(x) + p^2(x) + 2x/5p^5(x)$ but the derived subgroup membership testing formula does not distinguish points of order $2r$. With the same technique as [DLZZ23], we obtain the following formula for $\mathbb{G}_2$ membership testing when $x = 25 \pmod{70}$ ([DLZZ23] addresses $x = 45 \pmod{70}$).

$$ 1/70(11x + 5, 11x + 5, -19x - 15, 3x - 5, -3x + 5, -13x - 25, 7x - 35, x + 45) \quad (8) $$

We suggest this formula with larger scalars that works for any $x = 25, 45 \pmod{70}$:

$$ (u_5 + 1, u_5, u_5, u_5, -3u_5 - 2, -3u_5 - 2, -3u_5 - 2, -3u_5 - 2), \quad u_5 = (u - 5)/10 \quad (9) $$

**FM16 curves.** The formula $u - p$ gives the equation $[u]Q - \psi(Q) = \mathcal{O}$ and satisfies Theorem 3.

**AFG16 curves.** The formulas $-1+up^3$ and $u+p^5$ give the equations $-Q+[u]\psi^3(Q) = \mathcal{O}$ and $[u]Q + \psi^5(Q) = \mathcal{O}$ that both satisfy Theorem 3.

**KSS18 curves.** For KSS18 curves, the usual formulas of optimal ate pairing are [Ver10, Section 4]

$$ 2x/7 + p(x) + x/7p^3(x) \text{ or } 1 + xp^2(x) + 2p^3(x). \quad (10) $$

One notes that $2x/7+(p \pmod r)+x/7(p^3 \pmod r) = 0$ and $1+x(p^2 \pmod r)+2(p^3 \pmod r) = -5 \cdot 7 \cdot r(x)$.
**SG18 curves.** The optimal pairing formula $u + p^2 + up^3$ gives the equation $[u]Q + \psi^2(Q) + [u]\psi^3(Q) = \mathcal{O}$ and satisfies Theorem 3.

**FM18 curves.** The formulas $1+up^2$ and $u+p-p^4$ give the equations $Q+[u]\psi^2(Q) = \mathcal{O}$ and $[u]Q + \psi(Q) - \psi^4(Q) = \mathcal{O}$ and satisfy Theorem 3.

**FST20, FST28 curves.** The optimal pairing formula $u-p$ does not give a valid equation, the resultant of $u-X$ and $X^2-t(u)X+p(u)$ is $(u^2+1)r(u)$. We apply the same trick as for BLS: $p^{\varphi(k)-1}(u-p)$ mod $\Phi_k(p)$ gives $1-p^2+p^4-p^6+up^7$ for $k=20$ and $1-p^2+p^4-p^6+p^8-p^{10}+up^{11}$ for $k=28$. The equations $Q-\psi^2(Q)+\psi^4(Q)-\psi^6(Q)+[u]\psi^7(Q)=\mathcal{O}$ for $k=20$ and $Q-\psi^2(Q)+\psi^4(Q)-\psi^6(Q)+\psi^8(Q)-\psi^{10}(Q)+[u]\psi^{11}(Q)=\mathcal{O}$ satisfy Theorem 3.

**SG20 curves.** The optimal pairing formulas $u-up^5-p^7$ and $u+p^2+up^5$ give the equations $[u]Q - [u]\psi^5(Q) - \psi^7(Q) = \mathcal{O}$ and $[u]Q + \psi^2(Q) + [u]\psi^5(Q) = \mathcal{O}$ and satisfy Theorem 3.

**GG20b curves.** The optimal pairing formulas $u-p-2p^6$ and $2+up^4-p^5$ do not satisfy Theorem 3 as the gcd is $(u^2+4u+5)r(u)$. We set $p^{\varphi(k)-5}(2+up^4-p^5)$ mod $\Phi_{20}(p) = 1-p^2+p^4-p^6+2p^3+up^7$ and obtain a formula that satisfies Theorem 3: $(\text{Id}-\psi^2+\psi^4-\psi^6+[2]\psi^3+[u]\psi^7)(Q) = \mathcal{O}$.

**GG28 curves.** The optimal pairing formulas $u-p-2p^8$ and $2+up^6-p^7$ do not satisfy Theorem 3 as the gcd is $(u^2-4u+5)r(u)$. We set $p^{\varphi(k)-7}(2+up^6-p^7)$ mod $\Phi_{28}(p) = 1-p^2+p^4-p^6+p^8-p^{10}+2p^5+up^{11}$ and obtain a formula that satisfies Theorem 3: $(\text{Id}-\psi^2+\psi^4-\psi^6+\psi^8-\psi^{10}+[2]\psi^5+[u]\psi^{11})(Q) = \mathcal{O}$.

# 5 Experimental results

We implemented the most promising curves from Section 3.4 within the RELIC cryptographic toolkit [AGM$^+$] due to its strong support to pairing-based cryptography. RELIC already implemented several pairing-friendly curves (such as BLS) with state-of-the-art performance, so extending the library to include new curve families is natural and favors a fair comparison between candidates. The library is implemented in the C programming language, with handwritten ASM acceleration for finite field arithmetic in multiple sizes of the prime moduli. For each of the new or previously supported curve families, we included group operations and pairing computation, by either speeding-up existing routines or including entirely new ones. The resulting source code can be found at the RELIC repository, and our SageMath and Magma scripts can also be found at the *alpha* repository$^4$.

Benchmarking measurements were taken by computing the average latency of running the operation for $10^4$ consecutive executions on an Intel Kaby Lake Core i7-7700 CPU running at 3.60GHz. The main compiler used was GCC version 13.2.1, with optimization flags `-O3 -funroll-loops -march=native -mtune=native`; but we also verified that `clang` would exhibit similar performance. Following best practices$^5$, the TurboBoost and HyperThreading features were disabled in the benchmarking machine for higher stability.

Table 17 shows the cycle counts observed for executing scalar multiplications or exponentiation in pairing groups using a w-NAF algorithm with $w=4$ and Jacobian coordinates in the Weierstrass model. The constant-time version for the source groups was implemented with almost-complete exception-free homogeneous projective coordinates [RCB16] using a

<footnote>$^4$https://gitlab.inria.fr/tnfs-alpha/alpha</footnote>

<footnote>$^5$https://bench.cr.yp.to/supercop.html</footnote>
regular w-NAF algorithm in $\mathbb{G}_1$ with $w = 5$ to compensate the performance loss, or the GLV-SAC approach for $\mathbb{G}_2$ and $\mathbb{G}_T$. The table also shows timings for hashing to source groups, testing group elements for subgroup membership and pairing computation, split in the Miller loop and Final Exponentiation. From the table, it is clear that BLS24-509 has superior performance for all benchmarked operations, with speedups ranging from to 6.4% to 56.1%. We also highlight the fastest operations in curves with embedding degree 16 or 18, and show that AFG16 is a competitive candidate in comparison to other curves with the same embedding degree.

When checking for consistency between the timings for pairing computation and the normalized operation counts from Table 11, we can conclude that most figures are consistent, showing strong alignment between the implementation effort and the performance estimates. There are two exceptions, curve BLS12-1150 and FM16-765. The former deviates from the other implementations in the sense that it ends up more efficient than estimated, because it uses the low-level interface of the GMP library with Karatsuba splitting, leading to a slightly different cost model than the Schoolbook method assumed during normalization. For FM16-765, the observed performance is worse than AFG16 due to a less efficient choice of towering, that particular affects the timings for the final exponentiation. This is why the pairing latency looks closer to KSS16 than AFG16. Furthermore, we do not claim that all of our timings are the best possible for all parameters. Our emphasis was to fairly optimize all parameters with similar effort, such that meaningful comparisons could be made. For this reason, we decided to not implement techniques that could favor one parameter over the others [Lon23, BCN14] due to availability of more efficient code, although we leave to implement them as future work, as long as we feel confident that the same optimization level can be achieved across all parameters.

<table><caption>**Table 17:** Latency in $10^3$ clock cycles for performing scalar multiplication or exponentiation in $\mathbb{G}_1$, $\mathbb{G}_2$ and $\mathbb{G}_T$, possibly with constant-time (CT) countermeasures.</caption><thead><tr><th>Curve</th><th>BLS12</th><th>FM16</th><th>KSS16</th><th>AFG16</th><th>FM18</th><th>SG18</th><th>KSS18</th><th>BLS24</th></tr></thead><tbody><tr><td>Size of p</td><td>1150</td><td>765</td><td>766</td><td>766</td><td>768</td><td>638</td><td>638</td><td>509</td></tr><tr><td>[ℓ]P in G<sub>1</sub></td><td>6803</td><td>2158</td><td>3282</td><td>2157</td><td>1928</td><td>1368</td><td>1718</td><td>1066</td><td>(22.1%)</td></tr><tr><td>[ℓ]Q in G<sub>2</sub></td><td>11470</td><td>9956</td><td>16996</td><td>11227</td><td>7897</td><td>6101</td><td>7000</td><td>4190</td><td>(31.3%)</td></tr><tr><td>g<sup>ℓ</sup> in G<sub>T</sub></td><td>21148</td><td>7804</td><td>11910</td><td>7969</td><td>11181</td><td>8991</td><td>10566</td><td>6479</td><td>(18.7%)</td></tr><tr><td>CT [ℓ]P in G<sub>1</sub></td><td>9168</td><td>2805</td><td>4288</td><td>2802</td><td>2764</td><td>2130</td><td>2587</td><td>1275</td><td>(40.1%)</td></tr><tr><td>CT [ℓ]Q in G<sub>2</sub></td><td>17795</td><td>12524</td><td>18840</td><td>11921</td><td>9083</td><td>6957</td><td>8102</td><td>6144</td><td>(11.7%)</td></tr><tr><td>CT g<sup>ℓ</sup> in G<sub>T</sub></td><td>25973</td><td>8971</td><td>13156</td><td>8438</td><td>11918</td><td>9862</td><td>11628</td><td>7897</td><td>(06.4%)</td></tr><tr><td>Hash to G<sub>1</sub></td><td>6280</td><td>2845</td><td>1759</td><td>2495</td><td>3970</td><td>1490</td><td>1115</td><td>489</td><td>(56.1%)</td></tr><tr><td>Hash to G<sub>2</sub></td><td>18662</td><td>27573</td><td>22907</td><td>22052</td><td>27350</td><td>15130</td><td>8894</td><td>5788</td><td>(34.9%)</td></tr><tr><td>Testing in G<sub>1</sub></td><td>4547</td><td>1652</td><td>3060</td><td>1639</td><td>1494</td><td>1018</td><td>1808</td><td>797</td><td>(21.7%)</td></tr><tr><td>Testing in G<sub>2</sub></td><td>4935</td><td>3029</td><td>6547</td><td>2536</td><td>2057</td><td>1634</td><td>1927</td><td>1061</td><td>(35.0%)</td></tr><tr><td>Testing in G<sub>T</sub></td><td>5351</td><td>2579</td><td>5895</td><td>2125</td><td>4225</td><td>9878</td><td>2359</td><td>1294</td><td>(39.1%)</td></tr><tr><td>Miller Loop</td><td>28484</td><td>8188</td><td>11871</td><td>6950</td><td>9749</td><td>7135</td><td>9327</td><td>5429</td><td>(21.9%)</td></tr><tr><td>Final Exp.</td><td>29317</td><td>31694</td><td>28533</td><td>25666</td><td>27176</td><td>13628</td><td>15607</td><td>9670</td><td>(29.0%)</td></tr><tr><td>Pairing</td><td>57802</td><td>39882</td><td>40404</td><td>32617</td><td>36925</td><td>20763</td><td>24971</td><td>15100</td><td>(27.3%)</td></tr></tbody></table>

# 6 Conclusion

We performed an extensive comparison of several candidate families of pairing-friendly curves at the 192-bit level, both from theoretical and practical perspectives. Our recommended choices of pairing-friendly curves are the following. For a **prime-order curve**, choose a BN curve of ≈1152 bits. For **the fastest pairing**, take a BLS24 curve of ≈512 bits. For **smallest $\mathbb{G}_1$**, a BLS27 curve can have $p$ of ≈427 bits. While we focus exclusively
on the asymmetric pairings that offer the best performance, curves with embedding degree $k=1$ and supersingular curves with $k=2$ can be used to instantiate a symmetric pairing, at high performance penalty due to the very large base fields.

**Funding.** Georgios Fotiadis acknowledges the financial support from the Luxembourg National Research Fund (FNR) under the CORE project Privacy-Preserving Tokenisation of Artworks –PABLO (C21/IS/16326754/PABLO) and the CORE project Real-World Implementation and Human-Centered Design of PAKE Technologies –ImPAKT (C21/IS/16221219/ImPAKT). Aurore Guillevic received financial support from the Inria Sabbatical program and France 2030 ANR-22-PECY-0010 project.

## References

[AFK$^{+13}$] Diego F. Aranha, Laura Fuentes-Castañeda, Edward Knapp, Alfred Menezes, and Francisco Rodríguez-Henríquez. Implementing pairings at the 192-bit security level. In Michel Abdalla and Tanja Lange, editors, *PAIRING 2012*, volume 7708 of LNCS, pages 177–195. Springer, Berlin, Heidelberg, May 2013. doi:10.1007/978-3-642-36334-4_11.

[AFK24] Mónica P. Arenas, Georgios Fotiadis, and Elisavet Konstantinou. Special TNFS-secure pairings on ordinary genus 2 hyperelliptic curves. In Serge Vaudenay and Christophe Petit, editors, *AFRICACRYPT 2024*, volume 14861 of LNCS, pages 285–310, Douala, Cameroon, July 10-12 2024. Springer. doi:10.1007/978-3-031-64381-1_13.

[AGM$^{+}$] Diego F. Aranha, Conrado P. L. Gouvêa, Tobias Markmann, Riad S. Wahby, and K. Liao. RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit/relic.

[AHG23] Diego F. Aranha, Youssef El Housni, and Aurore Guillevic. A survey of elliptic curves for proof systems. *Des. Codes Cryptography*, 91(11):3333–3378, 2023. doi:10.1007/s10623-022-01135-y.

[AHST23] Diego F. Aranha, Benjamin Salling Hvass, Bas Spitters, and Mehdi Tibouchi. Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, *CCS*, pages 3228–3238. ACM, 2023. ePrint 2023/1261. doi:10.1145/3576915.3616597.

[AKL$^{+11}$] Diego F. Aranha, Koray Karabina, Patrick Longa, Catherine H. Gebotys, and Julio Cesar López-Hernández. Faster explicit formulas for computing pairings over ordinary curves. In Kenneth G. Paterson, editor, *EU-ROCRYPT 2011*, volume 6632 of LNCS, pages 48–68. Springer, Berlin, Heidelberg, May 2011. doi:10.1007/978-3-642-20465-4_5.

[ALH10] Diego F. Aranha, Julio Cesar López-Hernández, and Darrel Hankerson. High-speed parallel software implementation of the $\eta_T$ pairing. In Josef Pieprzyk, editor, *CT-RSA 2010*, volume 5985 of LNCS, pages 89–105. Springer, Berlin, Heidelberg, March 2010. doi:10.1007/978-3-642-11925-5_7.

[APR21] Diego F. Aranha, Elena Pagnin, and Francisco Rodríguez-Henríquez. LOVE a pairing. In Patrick Longa and Carla Ràfols, editors, *LATINCRYPT 2021*, volume 12912 of LNCS, pages 320–340. Springer, Cham, October 2021. doi:10.1007/978-3-030-88238-9_16.
[AR14] Gora Adj and Francisco Rodríguez-Henríquez. Square root computation over even extension fields. *IEEE Trans. Computers*, 63(11):2829-2841, 2014. ePrint 2012/685. doi:10.1109/TC.2013.145.

[BBHR18] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. ePrint 2018/046, 2018.

[BCI+10] Eric Brier, Jean-Sébastien Coron, Thomas Icart, David Madore, Hugues Randriam, and Mehdi Tibouchi. Efficient indifferentiable hashing into ordinary elliptic curves. In Tal Rabin, editor, *CRYPTO 2010*, volume 6223 of LNCS, pages 237-254. Springer, Berlin, Heidelberg, August 2010. doi:10.1007/978-3-642-14623-7_13.

[BCN14] Joppe W. Bos, Craig Costello, and Michael Naehrig. Exponentiating in pairing groups. In Tanja Lange, Kristin Lauter, and Petr Lisonek, editors, *SAC 2013*, volume 8282 of LNCS, pages 438-455. Springer, Berlin, Heidelberg, August 2014. doi:10.1007/978-3-662-43414-7_22.

[BD19] Razvan Barbulescu and Sylvain Duquesne. Updating key size estimations for pairings. *Journal of Cryptology*, 32(4):1298-1336, October 2019. doi: 10.1007/s00145-018-9280-5.

[BEG19] Razvan Barbulescu, Nadia El Mrabet, and Loubna Ghammam. A taxonomy of pairings, their security, their complexity. ePrint 2019/485, rev. Sept. 24, 2019, 2019.

[BF01] Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. In Joe Kilian, editor, *CRYPTO 2001*, volume 2139 of LNCS, pages 213-229. Springer, Berlin, Heidelberg, August 2001. doi: 10.1007/3-540-44647-8_13.

[BGW+22] Dan Boneh, Sergey Gorbunov, Riad S. Wahby, Hoeteck Wee, Christopher A. Wood, and Zhenfei Zhang. Bls signatures. https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/, Jun 2022. IETF draft.

[BKLS02] Paulo S. L. M. Barreto, Hae Yong Kim, Ben Lynn, and Michael Scott. Efficient algorithms for pairing-based cryptosystems. In Moti Yung, editor, *CRYPTO 2002*, volume 2442 of LNCS, pages 354-368. Springer, Berlin, Heidelberg, August 2002. doi:10.1007/3-540-45708-9_23.

[BL13] Daniel J. Bernstein and Tanja Lange. Non-uniform cracks in the concrete: The power of free precomputation. In Kazue Sako and Palash Sarkar, editors, *ASIACRYPT 2013, Part II*, volume 8270 of LNCS, pages 321-340. Springer, Berlin, Heidelberg, December 2013. doi:10.1007/978-3-642-42045-0_17.

[BLS01] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. In Colin Boyd, editor, *ASIACRYPT 2001*, volume 2248 of LNCS, pages 514-532. Springer, Berlin, Heidelberg, December 2001. doi:10.1007/3-540-45682-1_30.

[BLS03] Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott. Constructing elliptic curves with prescribed embedding degrees. In Stelvio Cimato, Clemente Galdi, and Giuseppe Persiano, editors, *SCN 02*, volume 2576 of LNCS, pages 257-267. Springer, Berlin, Heidelberg, September 2003. doi:10.1007/3-540-36413-7_19.
[BMDFAF19] Narcise Bang Mbiang, Diego De Freitas Aranha, and Emmanuel Fouotsa. Computing the optimal ate pairing over elliptic curves with embedding degrees 54 and 48 at the 256-bit security level. *International Journal of Applied Cryptography (IJACT)*, 4(1):45–59, 2019. doi:10.1504/IJACT.20 20.107167.

[BMUS23] Marta Bellés-Muñoz, Jorge Jiménez Urroz, and Javier Silva. Revisiting cycles of pairing-friendly elliptic curves. In Helena Handschuh and Anna Lysyanskaya, editors, *CRYPTO 2023, Part II*, volume 14082 of LNCS, pages 3–37. Springer, Cham, August 2023. doi:10.1007/978-3-031-38545-2_1.

[BN06] Paulo S. L. M. Barreto and Michael Naehrig. Pairing-friendly elliptic curves of prime order. In Bart Preneel and Stafford Tavares, editors, *SAC 2005*, volume 3897 of LNCS, pages 319–331. Springer, Berlin, Heidelberg, August 2006. doi:10.1007/11693383_22.

[Bow17] Sean Bowe. BLS12-381: New zk-SNARK elliptic curve construction. Zcash blog, March 11 2017. https://electriccoin.co/blog/new-snark-curve/.

[BS23] Ward Beullens and Gregor Seiler. LaBRADOR: Compact proofs for R1CS from module-SIS. In Helena Handschuh and Anna Lysyanskaya, editors, *CRYPTO 2023, Part V*, volume 14085 of LNCS, pages 518–548. Springer, Cham, August 2023. doi:10.1007/978-3-031-38554-4_17.

[BW05] Friederike Brezing and Annegret Weng. Elliptic curves suitable for pairing based cryptography. *Des. Codes Cryptography*, 37(1):133–141, 2005. ePrint 2003/143. doi:10.1007/s10623-004-3808-4.

[CCW19] Alessandro Chiesa, Lynn Chua, and Matthew Weidner. On cycles of pairing-friendly elliptic curves. *SIAM Journal on Applied Algebra and Geometry*, 3(2):175–192, 2019. doi:10.1137/18M1173708.

[CDS20] Rémi Clarisse, Sylvain Duquesne, and Olivier Sanders. Curves with fast computations in the first pairing group. In Stephan Krenn, Haya Shulman, and Serge Vaudenay, editors, *CANS 20*, volume 12579 of LNCS, pages 280–298. Springer, Cham, December 2020. doi:10.1007/978-3-030-654 11-5_14.

[CH07] Jaewook Chung and M. Anwar Hasan. Asymmetric squaring formulae. In *18th IEEE Symposium on Computer Arithmetic (ARITH-18 2007)*, 25-27 June 2007, Montpellier, France, pages 113–122. IEEE Computer Society, 2007. https://www.lirmm.fr/arith18/papers/Chung-Squaring.pdf. doi:10.1109/ARITH.2007.11.

[CHZ22] Shi Ping Cai, Zhi Hu, and Chang-An Zhao. Faster final exponentiation on the KSS18 curve. *IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences*, E105.A(8):1162–1164, 2022. ePrint 2021/1309. doi:10.1587/transfun.2021EAL2086.

[CL04] Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In Matthew Franklin, editor, *CRYPTO 2004*, volume 3152 of LNCS, pages 56–72. Springer, Berlin, Heidelberg, August 2004. doi:10.1007/978-3-540-28628-8_4.
[CLN10] Craig Costello, Tanja Lange, and Michael Naehrig. Faster pairing computations on curves with high-degree twists. In Phong Q. Nguyen and David Pointcheval, editors, *PKC 2010*, volume 6056 of LNCS, pages 224–242. Springer, Berlin, Heidelberg, May 2010. doi:10.1007/978-3-642-13013-7_14.

[CLN11] Craig Costello, Kristin Lauter, and Michael Naehrig. Attractive subfamilies of BLS curves for implementing high-security pairings. In Daniel J. Bernstein and Sanjit Chatterjee, editors, *INDOCRYPT 2011*, volume 7107 of LNCS, pages 320–342. Springer, Berlin, Heidelberg, December 2011. doi:10.1007/7/978-3-642-25578-6_23.

[Cos12] Craig Costello. Pairings for beginners. https://www.craigcostello.com/au/s/PairingsForBeginners.pdf, 2012.

[CRSCN24] Maria Corte-Real Santos, Craig Costello, and Michael Naehrig. On cycles of pairing-friendly abelian varieties. In Leonid Reyzin and Douglas Stebila, editors, *CRYPTO*, LNCS, Santa Barbara, CA, Aug 19-22 2024. Springer-Verlag. ePrint 2024/869. doi:10.1007/978-3-031-68400-5_7.

[CSB05] Sanjit Chatterjee, Palash Sarkar, and Rana Barua. Efficient computation of Tate pairing in projective coordinate over general characteristic fields. In Choonsik Park and Seongtaek Chee, editors, *ICISC 04*, volume 3506 of LNCS, pages 168–181. Springer, Berlin, Heidelberg, December 2005. doi:10.1007/11496618_13.

[CSRT22] Jorge Chávez-Saab, Francisco Rodríguez-Henríquez, and Mehdi Tibouchi. SwiftEC: Shallue-van de Woestijne indifferentiable function to elliptic curves - faster indifferentiable hashing to elliptic curves. In Shweta Agrawal and Dongdai Lin, editors, *ASIACRYPT 2022, Part I*, volume 13791 of LNCS, pages 63–92. Springer, Cham, December 2022. doi:10.1007/978-3-031-22963-3_3.

[Dai23] Yu Dai. smt-magma. https://github.com/eccdaiy39/smt-magma, 2023.

[DGP21] Gabrielle De Micheli, Pierrick Gaudry, and Cécile Pierrot. Lattice enumeration for tower NFS: A 521-bit discrete logarithm computation. In Mehdi Tibouchi and Huaxiong Wang, editors, *ASIACRYPT 2021, Part I*, volume 13090 of LNCS, pages 67–96. Springer, Cham, December 2021. doi:10.1007/978-3-030-92062-3_3.

[DLZZ23] Yu Dai, Kaizhan Lin, Chang-An Zhao, and Zijian Zhou. Fast subgroup membership testings for $\mathbb{G}_1, \mathbb{G}_2$ and $\mathbb{G}_T$ on pairing-friendly curves. *Designs, Codes and Cryptography*, 91(10):3141–3166, Oct 2023. ePrint 2022/348. doi:10.1007/s10623-023-01223-7.

[DZZ23a] Yu Dai, Fangguo Zhang, and Chang-An Zhao. Don't forget pairing-friendly curves with odd prime embedding degrees. *IACR TCHES*, 2023(4):393–419, 2023. doi:10.46586/tches.v2023.i4.393-419.

[DZZ23b] Yu Dai, Fangguo Zhang, and Chang-An Zhao. Fast hashing to $\mathbb{G}_2$ on pairing-friendly curves with the lack of twists. *Finite Fields and Their Applications*, 91:102263, 2023. ePrint 2022/996. doi:10.1016/j.ffa.2023.102263.

[DZZZ21] Yu Dai, Zijian Zhou, Fangguo Zhang, and Chang-An Zhao. Software implementation of optimal pairings on elliptic curves with odd prime embedding
degrees. *IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences*, E105.A(5):858-870, 2021. ePrint 2021/1162. doi:10.1587/transfun.2021EAP1115.

[EHG22] Youssef El Housni and Aurore Guillevic. Families of SNARK-friendly 2-chains of elliptic curves. In Orr Dunkelman and Stefan Dziembowski, editors, *EUROCRYPT 2022, Part II*, volume 13276 of LNCS, pages 367-396. Springer, Cham, May / June 2022. doi:10.1007/978-3-031-07085-3_13.

[FAG20] Emmanuel Fouotsa and Laurian Azebaze Guimagang. Fast hashing to $G_2$ on aurifeuillean pairing-friendly elliptic curves. *SN Comput. Sci.*, 1(1):51, 2020. doi:10.1007/S42979-019-0053-5.

[FAGA23] Emmanuel Fouotsa, Laurian Azebaze Guimagang, and Raoul Ayissi. *x*-superoptimal pairings on elliptic curves with odd prime embedding degrees: BW13-P310 and BW19-P286. *Applicable Algebra in Engineering, Communication and Computing (AAECC)*, pages 1-19, Feb 2023. ePrint 2022/716. doi:10.1007/s00200-023-00596-5.

[FHSS$^{+23}$] Armando Faz-Hernandez, Sam Scott, Nick Sullivan, Riad S. Wahby, and Christopher A. Wood. Hashing to Elliptic Curves. RFC 9380, August 2023. URL: https://www.rfc-editor.org/info/rfc9380, doi:10.17487/RFC 9380.

[FK19] Georgios Fotiadis and Elisavet Konstantinou. TNFS resistant families of pairing-friendly elliptic curves. *Theoretical Computer Science*, 800:73-89, 31 December 2019. ePrint 2018/1017. arXiv:2018/1017, doi:10.1016/j.tcs.2019.10.017.

[FKR12] Laura Fuentes-Castañeda, Edward Knapp, and Francisco Rodríguez-Henríquez. Faster hashing to $G_2$. In Ali Miri and Serge Vaudenay, editors, *SAC 2011*, volume 7118 of LNCS, pages 412-430. Springer, Berlin, Heidelberg, August 2012. doi:10.1007/978-3-642-28496-0_25.

[FLS15] Armando Faz-Hernández, Patrick Longa, and Ana H. Sánchez. Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves (extended version). *Journal of Cryptographic Engineering*, 5(1):31-52, April 2015. doi:10.1007/s13389-014-0085-7.

[FM19] Georgios Fotiadis and Chloe Martindale. Optimal TNFS-secure pairings on elliptic curves with composite embedding degree. ePrint 2019/555, 2019.

[Fot21] Georgios Fotiadis. Constructing efficient and STNFS-secure pairings. Slides at https://caramba.loria.fr/sem-slides/202102161400.pdf, February 2021. Talk at Inria Nancy seminar.

[FST10] David Freeman, Michael Scott, and Edlyn Teske. A taxonomy of pairing-friendly elliptic curves. *Journal of Cryptology*, 23(2):224-280, April 2010. doi:10.1007/s00145-009-9048-z.

[GF16] Loubna Ghammam and Emmanuel Fouotsa. Adequate elliptic curves for computing the product of *n* pairings. In Sylvain Duquesne and Svetla Petkova-Nikova, editors, *Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers*, volume 10064 of LNCS, pages 36-53, 2016. ePrint 2016/472. doi:10.1007/978-3-319-55227-9_3.
[GG23] Jean Gasnier and Aurore Guillevic. An algebraic point of view on the generation of pairing-friendly curves. preprint available at https://hal.science/hal-04205681, September 2023.

[Gha16] Loubna Ghammam. *Utilisation des Couplages en Cryptographie asymétrique pour la micro-électronique*. thèse de doctorat (PhD thesis), Université de Rennes 1, France, 12 2016. https://hal.science/tel-01469981v1.

[GKL+21] Robert Granger, Thorsten Kleinjung, Arjen K. Lenstra, Benjamin Wesolowski, and Jens Zumbrägel. Computation of a 30750-bit binary field discrete logarithm. *Math. Comp.*, 90(332):2997–3022, 2021. ePrint 2020/965. doi:10.1090/mcom/3669.

[GLS11] Steven D. Galbraith, Xibin Lin, and Michael Scott. Endomorphisms for faster elliptic curve cryptography on a large class of curves. *Journal of Cryptology*, 24(3):446–469, July 2011. doi:10.1007/s00145-010-9065-y.

[GLV01] Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms. In Joe Kilian, editor, *CRYPTO 2001*, volume 2139 of LNCS, pages 190–200. Springer, Berlin, Heidelberg, August 2001. doi:10.1007/3-540-44647-8_11.

[GMT20] Aurore Guillevic, Simon Masson, and Emmanuel Thomé. Cocks–Pinch curves of embedding degrees five to eight and optimal ate pairing computation. *Des. Codes Cryptography*, 88:1047–1081, March 2020. ePrint 2019/431. doi:10.1007/s10623-020-00727-w.

[Gro16] Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, *EUROCRYPT 2016, Part II*, volume 9666 of LNCS, pages 305–326. Springer, Berlin, Heidelberg, May 2016. doi:10.1007/978-3-662-49896-5_11.

[GS08] Steven D. Galbraith and Michael Scott. Exponentiation in pairing-friendly groups using homomorphisms. In Steven D. Galbraith and Kenneth G. Paterson, editors, *PAIRING 2008*, volume 5209 of LNCS, pages 211–224. Springer, Berlin, Heidelberg, September 2008. doi:10.1007/978-3-540-85538-5_15.

[GS10] Robert Granger and Michael Scott. Faster squaring in the cyclotomic subgroup of sixth degree extensions. In Phong Q. Nguyen and David Pointcheval, editors, *PKC 2010*, volume 6056 of LNCS, pages 209–223. Springer, Berlin, Heidelberg, May 2010. doi:10.1007/978-3-642-13013-7_13.

[GS21] Aurore Guillevic and Shashank Singh. On the alpha value of polynomials in the tower number field sieve algorithm. *Mathematical Cryptology*, 1(1):1–39, Feb. 2021. URL: https://journals.flvc.org/mathcryptology/article/view/125142.

[Gui20] Aurore Guillevic. A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, *PKC 2020, Part II*, volume 12111 of LNCS, pages 535–564. Springer, Cham, May 2020. doi:10.1007/978-3-030-45388-6_19.
[Gui21] Aurore Guillevic. Pairing-friendly curves. https://members.loria.fr/AGuillevic/pairing-friendly-curves/, Feb 2021. Last updated February 22, 2021.

[HGP22] Youssef El Housni, Aurore Guillevic, and Thomas Piellard. Co-factor clearing and subgroup membership testing on pairing-friendly curves. In Lejla Batina and Joan Daemen, editors, *AFRICACRYPT 22*, volume 2022 of LNCS, pages 518–536. Springer, Cham, July 2022. doi:10.1007/978-3-031-17433-9_22.

[HHT20] Daiki Hayashida, Kenichiro Hayasaka, and Tadanori Teruya. Efficient final exponentiation via cyclotomic structure for pairings over families of elliptic curves. ePrint 2020/875, 2020.

[Hou23] Youssef El Housni. Pairings in rank-1 constraint systems. In Mehdi Tibouchi and Xiaofeng Wang, editors, *ACNS 23International Conference on Applied Cryptography and Network Security, Part I*, volume 13905 of LNCS, pages 339–362. Springer, Cham, June 2023. doi:10.1007/978-3-031-33488-7_13.

[HSST12] Takuya Hayashi, Takeshi Shimoyama, Naoyuki Shinohara, and Tsuyoshi Takagi. Breaking pairing-based cryptosystems using $\eta_T$ pairing over GF(3$^{97}$). In Xiaoyun Wang and Kazue Sako, editors, *ASIACRYPT 2012*, volume 7658 of LNCS, pages 43–60. Springer, Berlin, Heidelberg, December 2012. doi:10.1007/978-3-642-34961-4_5.

[HSV06] F. Hess, N.P. Smart, and F. Vercauteren. The eta pairing revisited. *IEEE Transactions on Information Theory*, 52(10):4595–4602, 2006. ePrint 2006/110. doi:10.1109/TIT.2006.881709.

[Jou04] Antoine Joux. A one round protocol for tripartite Diffie–Hellman. *Journal of Cryptology*, 17(4):263–276, September 2004. doi:10.1007/s00145-004-0312-y.

[JT09] Marc Joye and Michael Tunstall. Exponent recoding and regular exponentiation algorithms. In Bart Preneel, editor, *AFRICACRYPT 09*, volume 5580 of LNCS, pages 334–349. Springer, Berlin, Heidelberg, June 2009. doi:10.1007/978-3-642-02384-2_21.

[KB16] Taechan Kim and Razvan Barbulescu. Extended tower number field sieve: A new complexity for the medium prime case. In Matthew Robshaw and Jonathan Katz, editors, *CRYPTO 2016, Part I*, volume 9814 of LNCS, pages 543–571. Springer, Berlin, Heidelberg, August 2016. doi:10.1007/978-3-662-53018-4_20.

[KIK$^{+}$17] Yutaro Kiyomura, Akiko Inoue, Yuto Kawahara, Masaya Yasuda, Tsuyoshi Takagi, and Tetsuro Kobayashi. Secure and efficient pairing at 256-bit security level. In Dieter Gollmann, Atsuko Miyaji, and Hiroaki Kikuchi, editors, *ACNS 17International Conference on Applied Cryptography and Network Security*, volume 10355 of LNCS, pages 59–79. Springer, Cham, July 2017. doi:10.1007/978-3-319-61204-1_4.

[KJ17] Taechan Kim and Jinhyuck Jeong. Extended tower number field sieve with application to finite fields of arbitrary composite extension degree. In Serge Fehr, editor, *PKC 2017, Part I*, volume 10174 of LNCS, pages 388–408. Springer, Berlin, Heidelberg, March 2017. doi:10.1007/978-3-662-54365-8_16.
[KM16] Neal Koblitz and Alfred Menezes. A riddle wrapped in an Enigma. *IEEE Security & Privacy*, 14(6):34–42, 2016. ePrint 2015/1018. doi:10.1109/MS P.2016.120.

[Kos24] Dmitrii Koshelev. Simultaneously simple universal and indifferentiable hashing to elliptic curves. ePrint 2024/085, Jan 2024.

[KSS08] Ezekiel J. Kachisa, Edward F. Schaefer, and Michael Scott. Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclo-tomic field. In Steven D. Galbraith and Kenneth G. Paterson, editors, *PAIRING 2008*, volume 5209 of LNCS, pages 126–135. Springer, Berlin, Heidelberg, September 2008. doi:10.1007/978-3-540-85538-5_9.

[KZG10] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, *ASIACRYPT 2010*, volume 6477 of LNCS, pages 177–194. Springer, Berlin, Heidelberg, December 2010. doi:10.1007/978-3-642-17373-8_11.

[Lip24] Helger Lipmaa. Polymath: Groth16 is not the limit. In *CRYPTO (10)*, volume 14929 of LNCS, pages 170–206. Springer, 2024. ePrint 2024/916. doi:10.1007/978-3-031-68403-6_6.

[Lon23] Patrick Longa. Efficient algorithms for large prime characteristic fields and their application to bilinear pairings. *IACR TCHES*, 2023(3):445–472, 2023. doi:10.46586/tches.v2023.i3.445-472.

[LZZ24] Jianming Lin, Chang-An Zhao, and Yuhao Zheng. Efficient implementation of super-optimal pairings on curves with small prime fields at the 192-bit security level. ePrint 2024/1195, Jul 2024.

[Mas20] Simon Masson. *Algorithmic of curves in the context of bilinear and post-quantum cryptography*. Doctorat, Université de Lorraine, Nancy, France, December 2020. https://tel.archives-ouvertes.fr/tel-03052499.

[MNT01] A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve traces for FR-reduction. *IEICE Transactions on Fundamentals*, E84-A(5):1234–1243, 2001. https://dspace.jaist.ac.jp/dspace/bits tream/10119/4432/1/73-48.pdf. URL: http://hdl.handle.net/10119 /4432.

[Mon05] P. L. Montgomery. Five, six, and seven-term Karatsuba-like formulae. *IEEE Transactions on Computer*, 54:362–369, March 2005. doi:10.1109/TC.200 5.49.

[MSS16] Alfred Menezes, Palash Sarkar, and Shashank Singh. Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography. In Raphael C.-W. Phan and Moti Yung, editors, *Mycrypt Conference*, volume 10311 of LNCS, pages 83–108, Kuala Lumpur, Malaysia, December 1-2 2016. Springer. arXiv:2016/1102, doi:10.1007/978-3-3 19-61273-7_5.

[OLAR13] Thomaz Oliveira, Julio Cesar López-Hernández, Diego F. Aranha, and Francisco Rodríguez-Henríquez. Lambda coordinates for binary elliptic curves. In Guido Bertoni and Jean-Sébastien Coron, editors, *CHES 2013*, volume 8086 of LNCS, pages 311–330. Springer, Berlin, Heidelberg, August 2013. doi:10.1007/978-3-642-40349-1_18.
[PS16] David Pointcheval and Olivier Sanders. Short randomizable signatures. In Kazue Sako, editor, *CT-RSA 2016*, volume 9610 of LNCS, pages 111–126. Springer, Cham, February / March 2016. doi:10.1007/978-3-319-29485-8_7.

[RCB16] Joost Renes, Craig Costello, and Lejla Batina. Complete addition formulas for prime order elliptic curves. In Marc Fischlin and Jean-Sébastien Coron, editors, *EUROCRYPT 2016, Part I*, volume 9665 of LNCS, pages 403–428. Springer, Berlin, Heidelberg, May 2016. doi:10.1007/978-3-662-49890-3_16.

[Rob22] Oisin Robinson. An implementation of the extended tower number field sieve using 4d sieving in a box and a record computation in $\mathbb{F}_{p^4}$, 2022. arXiv:2212.04999 https://arxiv.org/abs/2212.04999.

[Sch87] René Schoof. Nonsingular plane cubic curves over finite fields. *Journal of Combinatorial Theory, Series A*, 46(2):183–211, 1987. doi:10.1016/0097-3165(87)90003-3.

[Sco21] Michael Scott. A note on group membership tests for $G_1, G_2$ and $G_T$ on BLS pairing-friendly curves. ePrint 2021/1130, 2021.

[SG18] Michael Scott and Aurore Guillevic. A new family of pairing-friendly elliptic curves. In Lilya Budaghyan and Francisco Rodríguez-Henríquez, editors, *Arithmetic of Finite Fields*, pages 43–57, Cham, 2018. Springer. ePrint 2018/193. doi:10.1007/978-3-030-05153-2_2.

[SKSW22] Yumi Sakemi, Tetsutaro Kobayashi, Tsunekazu Saito, and Riad S. Wahby. Pairing-friendly curves. https://datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves/11/, Nov 2022. IETF draft.

[Smi15] Benjamin Smith. Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians. *Contemporary mathematics*, 637:15, May 2015. https://hal.inria.fr/hal-00874925. URL: https://hal.inria.fr/hal-00874925, doi:10.1090/conm/637/12753.

[TL23] Michael B. Jones Tobias Looker. Barreto–lynn–scott elliptic curve key representations for JOSE and COSE. https://datatracker.ietf.org/doc/draft-ietf-cose-bls-key-representations/, Oct 2023. IETF draft.

[TZ23] Stefano Tessaro and Chenzhi Zhu. Revisiting BBS signatures. In Carmit Hazay and Martijn Stam, editors, *EUROCRYPT 2023, Part V*, volume 14008 of LNCS, pages 691–721. Springer, Cham, April 2023. doi:10.1007/978-3-031-30589-4_24.

[Ver10] F. Vercauteren. Optimal pairings. *IEEE Transactions on Information Theory*, 56(1):455–461, Jan 2010. ePrint 2008/096. doi:10.1109/TIT.2009.2034881.

[WB19] Riad S. Wahby and Dan Boneh. Fast and simple constant-time hashing to the BLS12-381 elliptic curve. *IACR TCHES*, 2019(4):154–179, 2019. URL: https://tches.iacr.org/index.php/TCHES/article/view/8348, doi:10.13154/tches.v2019.i4.154-179.
## A Discarded curves

In Table 19 we give the seeds for evaluating the families of pairing-friendly elliptic curves with embedding degree $k = 22$. We focus on Freeman-Scott-Teske (FST) families obtained by construction 6.3 (FST6.3) and construction 6.6 (FST6.6) in [FST10]. In addition we consider the family of curves of Gasnier-Guillevic [GG23], GG22 with CM-discriminant $D = 7$. Further, in Table 20 we present the formula of the optimal ate pairing for the three families of pairing-friendly curves with embedding degree 22. The formula of the easy part of the final exponentiation is given in Table 18. Table A shows

<table><caption>**Table 18:** Exponents for the final exponentiation, easy and hard parts.</caption><thead><tr><th>k</th><th>final exp. easy part</th><th>final exp. hard part</th></tr></thead><tbody><tr><td>22</td><td>(p<sup>11</sup> - 1)(p + 1)</td><td>(p<sup>10</sup> - p<sup>9</sup> + p<sup>8</sup> - p<sup>7</sup> + p<sup>6</sup> - p<sup>5</sup> + p<sup>4</sup> - p<sup>3</sup> + p<sup>2</sup> - p + 1)/r</td></tr></tbody></table>

<table><caption>**Table 19:** Additional families of pairing-friendly elliptic curves and seeds at 192-bit security.</caption><thead><tr><th>k</th><th>curve</th><th>seed</th><th>(a, b)</th><th>p mod k</th><th>log p</th><th>log r</th><th>ρ</th><th>log p<sup>k</sup></th><th>secu/ref</th></tr></thead><tbody><tr><td rowspan="3">22</td><td>FST6.3</td><td>2<sup>21</sup> - 2<sup>13</sup> + 2<sup>6</sup> + 2<sup>3</sup> + 1</td><td>(1, 0)</td><td>1</td><td>544</td><td>420</td><td>1.30</td><td>11965</td><td>194</td></tr><tr><td>FST6.6</td><td>2<sup>19</sup> + 2<sup>15</sup> + 2<sup>13</sup> + 2<sup>11</sup> + 2<sup>3</sup></td><td>(0, -2)</td><td>1</td><td>534</td><td>383</td><td>1.40</td><td>11740</td><td>221</td></tr><tr><td>GG22, D = 7</td><td>-2<sup>20</sup> + 2<sup>18</sup> + 2<sup>13</sup> - 2<sup>10</sup> - 2<sup>8</sup> - 2<sup>2</sup> + 1</td><td>(-5/7, -2/7)</td><td>3</td><td>457</td><td>383</td><td>1.2</td><td>10052</td><td>220</td></tr></tbody></table>

<table><caption>**Table 20:** Optimal ate Miller loop formulas. The Miller functions $f_{u,Q}$ and lines $\ell_{Q,R}$ are evaluated at the point $P \in \mathbb{G}_1$.</caption><thead><tr><th>k</th><th>curve</th><th>Equation (1)</th><th>Optimal ate formula</th></tr></thead><tbody><tr><td rowspan="3">22</td><td>FST6.3</td><td>$u^2 - p \equiv 0 \pmod{r}$</td><td>$f_{u^2,Q}(P)$</td></tr><tr><td>FST6.6</td><td>$u^2 - up^4 + p^8 \equiv 0 \pmod{r}$</td><td>$f_{u^2,Q}(P) \cdot f_{u,Q}(P)^{-p^4} \cdot \ell_{[u^2]Q, -[u]\pi_4(Q)}(P)$</td></tr><tr><td>GG22</td><td>$u^2 - up + 2p^2 \equiv 0 \pmod{r}$</td><td>$f_{u^2,Q}(P) \cdot f_{u,Q}(P)^{-p} \cdot \ell_{[u^2]Q, -[u]\pi(Q)} \cdot \ell_{Q,Q}(P)^{2p^2}$</td></tr></tbody></table>

the number of $\mathbb{F}_p$-multiplications required for the Miller loop and the final exponentiation for the three types of curves with $k = 22$, FST6.3, FST6.6 and GG22. We discarded these curves from our study because they do not seem to be competitive candidates compared to the ones presented in Section 3. We note that such curves admit quadratic twists and hence the point addition and doubling operations in the Miller loop are executed over $\mathbb{F}_{p^{11}}$.

For group operations using GLV, the curve of $j$-invariant $-3375$ (discriminant $D = 7$) has an endomorphism $\phi$ of the form $(x, y) \mapsto (\phi_x(x), y\phi_y(x))$ with some $s = \sqrt{-7} \in \mathbb{F}_p$, of characteristic polynomial $\chi_\phi(X) = X^2 + X + 2$.

**FST 6.3** $k = 22$. Here is a formula for the hard part of the final exponentiation on input $m$:

$$ \bar{m} \leftarrow m^{p^{11}}; $$

$$ a \leftarrow m^{u^2} \cdot \bar{m}; \quad f \leftarrow f^p \cdot a; \quad a \leftarrow a^{u^2} \cdot m; \quad f \leftarrow f^p \cdot a; $$

$$ a \leftarrow m^{u^2} \cdot \bar{m}; \quad f \leftarrow f^p \cdot a; \quad a \leftarrow a^{u^2} \cdot m; \quad f \leftarrow f^p \cdot a; $$

$$ a \leftarrow m^{u^2} \cdot \bar{m}; \quad f \leftarrow f^p \cdot a; \quad a \leftarrow a^{u^2} \cdot m; \quad f \leftarrow f^p \cdot a; $$

$$ a \leftarrow m^{u^2} \cdot \bar{m}; \quad f \leftarrow f^p \cdot a; \quad a \leftarrow a^{u^2} \cdot m; \quad f \leftarrow f^p \cdot a; $$

$$ a \leftarrow m^{u^2} \cdot \bar{m}; \quad f \leftarrow f^p \cdot a; $$

$$ f \leftarrow f^{u^2} \cdot f^{p^{11}}; \quad f \leftarrow f^{u^4} \cdot f^{p^{11}}; \quad f \leftarrow f \cdot m^4 $$
<table><caption>**Table 21:** Optimal ate pairing and final exponentiation cost estimates in terms of finite field multiplications. The name of each curve is derived from the name of the corresponding family in Table 5, plus the size of the prime *p*.</caption><thead><tr><th rowspan="2">curve</th><th rowspan="2">p<br>bits</th><th rowspan="2">r<br>bits</th><th rowspan="2">Miller loop<br>optimal ate</th><th colspan="3">final exp</th><th rowspan="2">pairing<br>total</th></tr><tr><th>easy</th><th>hard</th><th>total</th></tr></thead><tbody><tr><td>FST6.3-544, k = 22</td><td>544</td><td>420</td><td>39.707m</td><td>789m</td><td>65.604m</td><td>66.393m</td><td>106.100m</td></tr><tr><td>FST6.6-534, k = 22</td><td>534</td><td>383</td><td>33.955m</td><td>789m</td><td>64.200m</td><td>64.989m</td><td>98.944m</td></tr><tr><td>GG22-457, D = 7</td><td>457</td><td>383</td><td>41.154m</td><td>789m</td><td>72.352m</td><td>73.141m</td><td>114.295m</td></tr></tbody></table>

which costs $24 \exp(u) + 2s_{22} + 21m_{22} + 9f_{22}$.

**FST 6.6 k = 22.** Here is a formula for the hard part of the final exponentiation:

$$(u^3 - 1)^2((u^{10}(u + q^4) + uq^7 - 1)(u^3 + q)(u^6 + q^2) - u^{10}q^7) + 3(u + q^4)$$

which costs $26 \exp(u) + 11m_{22} + s_{22} + 6f_{22}$.

**GG22D7.** We obtained a final exp hard formula which costs $22 \exp(u) + 20f_{22} + 41m_{22} + 50s_{22}$.

# B Formulas and parameters for group operations

In Table 22 we give polynomial description for families of curves considered in this paper. Specifically, this table lists the CM-discriminant for each type of curves, the polynomial $r(x)$ dividing the order of the curve, the polynomial representation of the cofactor $c_1(x)$, such that $E(\mathbb{F}_{p(x)}) = c_1(x)r(x)$, as well as the congruences that the seeds much satisfy in order for the polynomial family to produce integer values.

# C Curves at the 256-bit security level

In Table 23 we give known instantiations in the literature for existing families of pairing-friendly elliptic curves aiming at 256-bit security level.
<table><caption>**Table 22:** Curve parameters, *k* is the embedding degree, *r* is the prime order of $\mathbb{G}_1$, $c_1$ is the cofactor so that the curve over $\mathbb{F}_p$ has order $r \cdot c_1$, and *x* is the seed.</caption><thead><tr><th>k</th><th>D</th><th>Curve</th><th>r(x)</th><th>c<sub>1</sub>(x)</th><th>x s.t. r, c<sub>1</sub> are integers</th></tr></thead><tbody><tr><td>12</td><td>3</td><td>BLS12</td><td>x<sup>4</sup> - x<sup>2</sup> + 1</td><td>(x - 1)<sup>2</sup>/3</td><td>1 mod 3</td></tr><tr><td>15</td><td>3</td><td>BLS15</td><td>x<sup>8</sup> - x<sup>7</sup> + x<sup>5</sup> - x<sup>4</sup> + x<sup>3</sup> - x + 1</td><td>(x - 1)<sup>2</sup>/3(x<sup>2</sup> + x + 1)</td><td>1, 7 mod 15</td></tr><tr><td></td><td></td><td>FM15</td><td>x<sup>8</sup> - x<sup>7</sup> + x<sup>5</sup> - x<sup>4</sup> + x<sup>3</sup> - x + 1</td><td>x<sup>2</sup>(3x<sup>6</sup> - 2x<sup>4</sup> - x<sup>3</sup> - 2x<sup>2</sup> + 3)/3</td><td>0, 3 mod 15</td></tr><tr><td>16</td><td>1</td><td>KSS16</td><td>(x<sup>8</sup> + 48x<sup>4</sup> + 625)/61250</td><td>125/2(x<sup>2</sup> + 2x + 5), 1250 | c<sub>1</sub></td><td>25, 45 mod 70</td></tr><tr><td></td><td></td><td>FM16</td><td>Φ<sub>16</sub> = x<sup>8</sup> + 1</td><td>x<sup>2</sup>/4(x<sup>6</sup> + 1)</td><td>0 mod 2</td></tr><tr><td></td><td></td><td>AFG16</td><td>Φ<sub>16</sub> = x<sup>8</sup> + 1</td><td>x<sup>2</sup>(x<sup>3</sup> + 1)<sup>2</sup>/4</td><td>any</td></tr><tr><td>18</td><td>3</td><td>KSS18</td><td>(x<sup>6</sup> + 37x<sup>3</sup> + 343)/343</td><td>49/3(x<sup>2</sup> + 5x + 7), 343 | c<sub>1</sub></td><td>14 mod 21</td></tr><tr><td></td><td></td><td>SG18</td><td>27x<sup>6</sup> + 9x<sup>3</sup> + 1</td><td>(3x<sup>2</sup> - 1)<sup>2</sup></td><td>any</td></tr><tr><td></td><td></td><td>FM18</td><td>Φ<sub>18</sub> = x<sup>6</sup> - x<sup>3</sup> + 1</td><td>(3x<sup>6</sup> + x<sup>2</sup> - 2x + 1)/3</td><td>1 mod 3</td></tr><tr><td>20</td><td>1</td><td>FM20</td><td>Φ<sub>20</sub> = x<sup>8</sup> - x<sup>6</sup> + x<sup>4</sup> - x<sup>2</sup> + 1</td><td>(x - 1)<sup>2</sup>(x<sup>2</sup> + 1)/4</td><td>1 mod 2</td></tr><tr><td></td><td></td><td>SG20</td><td>16x<sup>8</sup> + 16x<sup>7</sup> + 8x<sup>6</sup></td><td>2x<sup>2</sup>(4x<sup>4</sup> - 3x<sup>2</sup> + 1)</td><td>any</td></tr><tr><td></td><td></td><td>GG20a</td><td>-4x<sup>4</sup> + 2x<sup>2</sup> + 2x + 1</td><td>125(x<sup>2</sup> - 4x + 5).</td><td>1715, 1815</td></tr><tr><td></td><td></td><td></td><td>(x<sup>8</sup> + 4x<sup>7</sup> + 11x<sup>6</sup> + 24x<sup>5</sup></td><td>(x<sup>2</sup> - 2x + 5)/164</td><td>mod 2050</td></tr><tr><td></td><td></td><td></td><td>+41x<sup>4</sup> + 120x<sup>3</sup> + 275x<sup>2</sup></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>+500x + 625)/(5<sup>4</sup> · 41)</td><td></td><td></td></tr><tr><td></td><td></td><td>GG20b</td><td>(x<sup>8</sup> - 4x<sup>7</sup> + 11x<sup>6</sup> - 24x<sup>5</sup></td><td>125(x<sup>2</sup> + 4x + 5).</td><td>1465, 1565</td></tr><tr><td></td><td></td><td></td><td>+41x<sup>4</sup> - 120x<sup>3</sup> + 275x<sup>2</sup></td><td>(x<sup>2</sup> - 2x + 5)/164</td><td>mod 2050</td></tr><tr><td></td><td></td><td></td><td>-500x + 625)/(5<sup>4</sup> · 41)</td><td></td><td></td></tr><tr><td>21</td><td>3</td><td>BLS21</td><td>Φ<sub>21</sub> = x<sup>12</sup> - x<sup>11</sup> + x<sup>9</sup> - x<sup>8</sup></td><td>(x - 1)<sup>2</sup>/3, 9 | c<sub>1</sub></td><td>1 mod 3</td></tr><tr><td></td><td></td><td></td><td>+x<sup>6</sup> - x<sup>4</sup> + x<sup>3</sup> - x + 1</td><td>(x<sup>2</sup> + x + 1)</td><td></td></tr><tr><td>24</td><td>3</td><td>BLS24</td><td>Φ<sub>24</sub> = x<sup>8</sup> - x<sup>4</sup> + 1</td><td>(x - 1)<sup>2</sup>/3, 3 | c<sub>1</sub></td><td>1 mod 3</td></tr><tr><td>27</td><td>3</td><td>BLS27</td><td>Φ<sub>27</sub>/3 = (x<sup>18</sup> + x<sup>9</sup> + 1)/3</td><td>(x - 1)<sup>2</sup>, 3 | c<sub>1</sub></td><td>1 mod 3</td></tr><tr><td>28</td><td>1</td><td>FST28</td><td>Φ<sub>28</sub> = x<sup>12</sup> - x<sup>10</sup> + x<sup>8</sup></td><td>(x - 1)<sup>2</sup>/4(x<sup>2</sup> + 1), 2 | c<sub>1</sub></td><td>1 mod 2</td></tr><tr><td></td><td></td><td></td><td>-x<sup>6</sup> + x<sup>4</sup> - x<sup>2</sup> + 1</td><td></td><td></td></tr><tr><td></td><td></td><td>GG28</td><td>(x<sup>12</sup> + 4x<sup>11</sup> + 11x<sup>10</sup> + 24x<sup>9</sup> + 41x<sup>8</sup> + 44x<sup>7</sup></td><td>(x<sup>2</sup> - 4x + 5).</td><td>309, 449</td></tr><tr><td></td><td></td><td></td><td>-29x<sup>6</sup> + 220x<sup>5</sup> + 1025x<sup>4</sup> + 3000x<sup>3</sup></td><td>(x<sup>2</sup> - 2x + 5)/580</td><td>1759, 1899</td></tr><tr><td></td><td></td><td></td><td>+6875x<sup>2</sup> + 12500x + 15625)/29</td><td></td><td>mod 2030</td></tr></tbody></table>

<table><caption>**Table 23:** Curves at the 256-bit security level.</caption><thead><tr><th>ref</th><th>curve</th><th>seed</th><th>r (bits)</th><th>p (bits)</th><th>p<sup>k</sup> (bits)</th></tr></thead><tbody><tr><td rowspan="2">[BD19]</td><td>KSS18</td><td>2<sup>186</sup> - 2<sup>75</sup> - 2<sup>22</sup> + 2<sup>4</sup></td><td>1108</td><td>1484</td><td>26712</td></tr><tr><td>BLS24</td><td>-2<sup>103</sup> - 2<sup>101</sup> + 2<sup>68</sup> + 2<sup>50</sup></td><td>827</td><td>1032</td><td>24768</td></tr><tr><td rowspan="5">[KIK<sup>+17</sup>]</td><td>BLS24</td><td>2<sup>109</sup> - 2<sup>75</sup> + 2<sup>65</sup> - 1</td><td>872</td><td>1089</td><td>26122</td></tr><tr><td>KSS32</td><td>2<sup>49</sup> - 2<sup>30</sup> + 2<sup>18</sup> + 2<sup>14</sup> - 2<sup>12</sup> - 2<sup>2</sup> - 1</td><td>738</td><td>861</td><td>27536</td></tr><tr><td>KSS36</td><td>-2<sup>58</sup> + 2<sup>45</sup> + 2<sup>40</sup> + 2<sup>34</sup> + 2<sup>5</sup></td><td>669</td><td>798</td><td>28699</td></tr><tr><td>BLS42</td><td>2<sup>43</sup> - 2<sup>8</sup> + 2<sup>2</sup> - 1</td><td>516</td><td>687</td><td>28830</td></tr><tr><td>BLS48</td><td>-2<sup>32</sup> - 2<sup>30</sup> - 2<sup>10</sup> + 2<sup>7</sup> - 1</td><td>518</td><td>581</td><td>27851</td></tr><tr><td rowspan="2">[BMDFAF19]</td><td>BLS48</td><td>2<sup>32</sup> - 2<sup>18</sup> - 2<sup>10</sup> - 2<sup>4</sup></td><td>512</td><td>575</td><td>27600</td></tr><tr><td>SG54</td><td>2<sup>27</sup> + 2<sup>26</sup> + 2<sup>22</sup> + 2<sup>14</sup> + 2<sup>6</sup> + 2</td><td>512</td><td>569</td><td>30726</td></tr></tbody></table>