Razvan Barbulescu
email: razvan.barbulescu@u-bordeaux.fr

Nadia El Mrabet
email: nadia.el-mrabet@emse.fr

Loubna Ghammam
email: loubna.ghammam@itk-engineering.de

A taxonomy of pairings, their security, their complexity

. At 192 bits of security, we find that the new champions are the less known BLS-24, KSS-16 and KSS-18. At 256 bits of security we conclude that the best pairing is k27method66.

Introduction

Pairings are a crucial ingredient in a series of public-key protocols which started with Joux' [START_REF] Joux | A one round protocol for tripartite Diffie-Hellman[END_REF] tri-partite Diffie-Hellman scheme and Boneh and Franklin's [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] identity-based encryption. Then followed protocols for short signatures [START_REF] Boneh | Short signatures from the Weil pairing[END_REF], a wide variety of aggregate, instance and verifier-local revocation signatures [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF][START_REF] Boneh | Short group signatures[END_REF][START_REF]Identity-Based Cryptography[END_REF], broadcast encryption [START_REF] Boneh | Collusion resistant broadcast encryption with short ciphertexts and private keys[END_REF], cloud computing [START_REF] Ateniese | Improved proxy re-encryption schemes with applications to secure distributed storage[END_REF], privacy enhancing environments [START_REF] Sheedy | Privacy Enhancing Protocols using Pairing Based Cryptography[END_REF], deep package inspection over encrypted traffic [START_REF] Sherry | Blindbox: Deep packet inspection over encrypted traffic[END_REF][START_REF] Canard | Blin-dIDS: Market-compliant and privacy-friendly intrusion detection system over encrypted traffic[END_REF] and many others. The NIST [START_REF] Moody | Pairing project[END_REF] pilots a project dedicated to pairings. Efficient implementations of pairings [START_REF] Beuchat | Multi-core implementation of the Tate pairing over supersingular elliptic curves[END_REF][START_REF] Beuchat | High-speed software implementation of the optimal Ate pairing over Barreto-Naehrig curves[END_REF][START_REF] Grewal | Efficient implementation of bilinear pairings on ARM processors[END_REF][START_REF] Unterluggauer | Practical attack on bilinear pairings to disclose the secrets of embedded devices[END_REF][START_REF] Md | Efficient optimal ate pairing at 128-bit security level[END_REF] made them interesting for industrial development [START_REF]Voltage security[END_REF][START_REF] Chang | Trend micro[END_REF][START_REF]Zcash developers[END_REF]. Pairings are not suited for post-quantum applications as they are based on the difficulty of discrete logarithms. However, quantum computer is not readily available for large computations and one can continue to use pairings for applications where the keys are used for a short period of time. This paper is the mature result of a work we started a few years ago in which we reacted to the Kim-Barbulescu TNFS attack. Before the attack, the security of pairings was a function of the key sizes, regardless on which family of pairings was used. In that context, the fastest pairings were BN, BLS12, KSS16 at the 128 bits security level, KSS18 and BLS24 for higher security which had small values of a parameter called ρ. A recent article [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] showed that these pairings are affected by the TNFS attack. We raised the question whether there are families which are less affected and which become the new champions and whether the existing order is reshuffled. For this we worked over hundred families of pairings. A precise analysis allows us to make the following recommendations, which confirm that the order has changed and that there are new champions:

-128 bits: BLS-24 and BLS-12 are the champions, followed by KSS 16 and DCC 15 families; -192 bits: BLS-24 is the champion, followed by KSS-16 and KSS-18; -256 bits: k27method66 is the clear champion.

At a high level, a pairing is a non-degenerate and bilinear map, e : G1 × G2 → G3, where G1 and G2 are subgroups of an elliptic curve and G3 is a multiplicative sub-group of a finite field. The security of pairing-based cryptography relies on one side on the discrete logarithm problem (DLP) over G1 (and consecutively over G2) which are elliptic curves, we call this the curve side security and note that it is very well understood on the classical computers. On the other side, it relies on the discrete logarithm problem over G3 which is the multiplicative sub-group of a finite field, this is the field side security. The hardness of computing discrete logarithms in a finite field is difficult to evaluate. In a first time one used the approximation that its cost is equal to that of factoring, which is done with a variant of the same algorithm: the number field sieve (NFS). Hence, the first key sizes proposed for pairings [START_REF] Arjen | Unbelievable security: Matching AES security using public key systems[END_REF] were such that log 2 #G3 matches the required bit size for an RSA modulus offering the same security level. In a second time, one computed the cost using a theoretical upper bound [START_REF] Menezes | Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography[END_REF][START_REF] Scott | A new family of pairing-friendly elliptic curves[END_REF] and the recommended key sizes were used go generate new seeds [START_REF] Fotiadis | Generating pairing-friendly elliptic curve parameters using sparse families[END_REF][START_REF] Zhang | Generating pairing-friendly elliptic curves using parameterized families[END_REF] and to propose efficient implementations [START_REF] Fouotsa | Optimal Ate Pairing on Elliptic Curves with Embedding Degree 9, 15 and 27[END_REF]. In a recent article, Barbulescu and Duquesne [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] made a precise real-life analysis with no theoretical assumption. Hence, they found the optimal parameters for each variant of NFS and obtained key sizes which can be used in a future standardization for 5 families of pairing friendly elliptic curves. All the recent works use the practical estimation: we used it in a working version of this article [START_REF] Barbulescu | A taxonomy of pairings, their security, their complexity[END_REF], Martindale and Fotiadis [START_REF] Fotiadis | Optimal tnfs-secure pairings on elliptic curves with even embedding degree[END_REF][START_REF] Fotiadis | Optimal TNFS-secure pairings on elliptic curves with composite embedding degree[END_REF] used it to compute the security of pairings whose embedding degree is even and respectively composite, Guillevic [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] made a short list at 128 bits of security and Guillevic and Singh [START_REF] Guillevic | On the alpha value of polynomials in the tower number field sieve algorithm[END_REF] used it in a preliminary presentation for some families at 192 bits of security.

The core of the security analysis is actually the daily difficulty for a NFS implementer and developer: select polynomials and tune parameters. This task is not automatic in the CADO-NFS software as the tabulated parameters for factoring integers between 80 and 100 decimal digits are not guaranteed to be optimal.

It is an open question to rapidly select the optimal parameters for NFS, especially for the smallest values where NFS is the choice algorithm, i.e. integers of about 80 decimal digits. In our case however, of 128 bits of security, tuning parameters is negligible and we used a brute force approach: we test a wide range of NFS variants and parameters and experimentally measure and extrapolate the cost of an NFS computation until we find the optimal set of parameters. Guillevic found errors in the first version of this article because the range of parameters was not wide enough. We solved this by using more computational time and by launching computations in an automatic manner.

Once the security has been settled, we continue by finding seeds of small NAF weight and optimize as much as possible the computation of the Ate pairing: Miller's loop and final exponentiation. To shorten presentation we use BN as a broom wagon at 128 bits of security and similarly for the higher levels: if Miller's loop of a pairing costs more than the complete computation for BN then we discard this pairing from the final exponentiation optimization.

Our contribution

We make an extensive literature inspection to find as many pairing-friendly families as possible. The main reference is the taxonomy [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] whose title we copy, but we discovered some families [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF][START_REF] Lin | Computing the ate pairing on elliptic curves with embedding degree k= 9[END_REF] which weren't included in that work. We also add a small number of families which were published after the taxonomy: [START_REF] Dry Lo | On constructing families of pairing-friendly elliptic curves with variable discriminant[END_REF][START_REF] Scott | A new family of pairing-friendly elliptic curves[END_REF]. Before the key sizes had to be corrected, the BN family was much faster and received much more attention than the other families in the taxonomy, some of which remained to the status of theoretical formulae. We continue along the lines of the recent works and make the precise estimations of the security for a large number of families. In the case of the families studied in [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] and [START_REF] Guillevic | On the alpha value of polynomials in the tower number field sieve algorithm[END_REF] the authors used a slightly different model which results in key sizes which are within an error of 5% from the model of [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] and [START_REF] Fotiadis | Optimal TNFS-secure pairings on elliptic curves with composite embedding degree[END_REF]. For a fair comparison we compute here the key sizes in the same model as BN, BLS and KSS. We present the first precise analysis at 256 bits of security. We evaluate the complexity of the pairings at the sizes which resist to the new attacks. In the case of pairings whose embedding degree is divisible by 5, 7 or 11 we discuss the formulae introduced in [START_REF] Peter | Five, six, and seven-term karatsuba-like formulae[END_REF][START_REF] Mrabet | Efficient multiplication in finite field extensions of degree 5[END_REF][START_REF] Scott | Missing a trick: Karatsuba variations[END_REF].

Paper overview

In Section 2, we recall the basic notations on pairings, present the classical optimizations of the implementation and recall the various constructions of pairings. In Section 3, we draw the big lines of the NFS algorithm, recall what are the choices for an attacker and compute the updated key sizes for a large number of families. For each family, we construct pairings and evaluate the cost of Miller's loop, first in arithmetic then in binary operations, at 128 bits (Section 4) and respectively 192 and 256 bits of security (Section 4.9 and 4.10). Then, in Section 5 we present the final exponentiation complexity for the Optimal Ate pairings in some of proposed curves. We obtain the overall cost and conclude in Section 6, the result tables are at the end of the article.

Some background on pairings

In this section we present the definition of pairings and we give an overview of the optimization methods for efficient implementations of pairings. The notations about arithmetic are introduced and we give the definition of the Optimal Ate pairing according to the method used to construct pairing-friendly elliptic curves. For a more detailed introduction we refer to [START_REF] Mrabet | Guide to Pairing-Based Cryptography[END_REF] for instance.

Definition of pairings

We briefly recall here elementary definition on pairings [START_REF] Weil | Sur les fonctions algebriques à corps de constantes fini[END_REF]. Let E be an elliptic curve defined over a finite field Fq, with q a large prime integer. We denote by O the neutral element of the additive group law over E. The elliptic curve is described in the Weierstrass model: E(Fq) = {(x, y), y 2 = x 3 + ax + b, a, b ∈ Fq}.

Let r be a large prime divisor of the group order E(Fq) and k be the embedding degree of E with respect to r, i.e. the smallest integer k such that r divides q k -1.

The Weil [START_REF] Weil | Sur les fonctions algebriques à corps de constantes fini[END_REF] and the Tate [START_REF] Tate | Duality theorems in galois cohomology over number fields[END_REF] pairings are constructed using the Miller algorithm [START_REF] Victor | The Weil pairing, and its efficient calculation[END_REF]. For the Ate, twisted Ate [START_REF] Hess | The Eta pairing revisited[END_REF], Optimal Ate pairing [START_REF] Vercauteren | Optimal pairings[END_REF] and pairing lattices [START_REF] Hess | Pairing lattices[END_REF], the most efficient pairings are constructed on the Tate model. Hence, we only recall here the definition of the reduced Tate pairing, a more complete definition being given in [START_REF] Blake | Elliptic Curves in Cryptography[END_REF]§IX.5].

Definition 1 (Tate pairing). Let E(Fq) be an elliptic curve over the finite field Fq for q a large prime number. Let r be a prime divisor of (E(Fq)). Let k be the embedding degree of E relatively to r.

Let G1 = E(Fq)[r], G2 = E(F q k )/rE(F q k ) and G3 = {µ ∈ F q k such that µ r = 1}.
The reduced Tate pairing is defined as

eT : G1 × G2 → G3, (P, Q) → fr,P (Q) q k -1 r
, where fr,P (Q) is the Miller function defined by the divisor

D = r(P ) -(rP ) -(r -1)(O).
The Miller function is computed through the Miller's algorithm [START_REF] Victor | The Weil pairing, and its efficient calculation[END_REF], which is constructed on the double and add scheme using the construction of rP and based on the notion of divisors. We only give here the essential elements for the pairing computation. The Miller algorithm constructs the rational function fr,P associated to the point P , where P is a generator of G1; and at the same time, it evaluates fr,P (Q) for a point

Q ∈ G2 ⊂ E(F q k ).
The final exponentiation is used to ensure the uniqueness of the resulting value of two equal pairing computations (e.g. e(P,

[2]Q) = e([2]P, Q)).
The final exponentiation maps the result of the Miller algorithm into the group formed by the r th roots of unity in F * q k .

Optimizations for pairings

The optimisations of pairings rely on an accurate choice of the embedding degree, the parametrization family of elliptic curves, the use of a twist for E(F q k ), the research for particular curves inside the chosen family.

Choice of the embedding degree The most general optimisations for a pairing implementation are obtained when k is chosen to have only small prime factors, more particularly when k is a product of powers of 2 and 3 [START_REF] Mrabet | Guide to Pairing-Based Cryptography[END_REF]. This property allows the extension field F q k to be constructed using tower field extensions, which have a good arithmetic. The pairing friendly elliptic curves which are the most interesting for implementation purposes are obtained from families, a taxonomy of which was made by Freeman, Scott and Teske in [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF], to which we add some other constructions [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF][START_REF] Lin | Computing the ate pairing on elliptic curves with embedding degree k= 9[END_REF] and families which were published after the taxonomy : [START_REF] Dry Lo | On constructing families of pairing-friendly elliptic curves with variable discriminant[END_REF][START_REF] Scott | A new family of pairing-friendly elliptic curves[END_REF], and [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF]. We do not add the families of [START_REF] Fotiadis | Optimal TNFS-secure pairings on elliptic curves with composite embedding degree[END_REF] as there were studied and our analysis does not improve the results.

Existence of twisted elliptic curve An important trick when computing a Tate-like pairing is the elimination of denominators. This is possible when k is a multiple of 2 [START_REF] Koblitz | Pairing-based cryptography at high security levels[END_REF] or 3 [START_REF] Lin | Computing the ate pairing on elliptic curves with embedding degree k= 9[END_REF] together with the use of a twisted elliptic curve. An elliptic curve E/Fq of embedding degree k is said to have a twist of degree d if d is a factor of k and there exists an elliptic curve E /F q k/d which is F q k -birationally isomorphic to E/F q k/d . The larger d is, the faster the pairing is because one can replace the operations over E(F q k ) by operations over E(F q k/d ) using the embedding map into E(F q k ). The existence of a twist relies on the value of the complex multiplication discriminant ∆ (if D is the squarefree part of t Choice of parameters inside a family A family of pairing friendly elliptic curves with embedding degree k is given by a triple (q(x), r(x), t(x)) of polynomials with coefficients in Q. In this representation, q(x) is the characteristic of the finite field, r(x) a prime factor of E(Fq) and t(x) is the trace of the elliptic curve. If u is an integer such that q(u) and r(u) are prime numbers, then there exists an elliptic curve with embedding degree k and parameters (q(u), r(u), t(u)).

The integer u is used in the exponent in the Miller loop, the final exponentiation, and it can have a great impact on the F q k arithmetic [START_REF] Sylvain Duquesne | Choosing and generating parameters for low level pairing implementation on BN curves[END_REF]. For this reason, u should have a NAF weight as small as possible in order to improve the efficiency of the pairing computation. Once we have found an integer u such that q(u) and r(u) are prime integers, we have to construct the equation of the elliptic curve. This can be done thanks to the complex multiplication (CM) method [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF].

There exists several models for elliptic curves, but the most efficient computation of pairings are obtained using Weierstrass model: E : y = x 3 + ax + b with a ∈ {0, -3} and b ∈ Fq.

As the expression of the final exponentiation is the same for every pairings, the goal is to obtain the shortest Miller loop. In practice, the reduction of Miller's loop is performed using the definition of optimal pairing [START_REF] Vercauteren | Optimal pairings[END_REF]. Last but not least, one must discard the seeds u which are target of the subgroup attack [START_REF] Paulo | Subgroup security in pairing-based cryptography[END_REF].

Arithmetic for finite fields

Notations. In the following we use the classical notations Aq, Mq, Sq and Iq for the binary cost of the addition, multiplication, squaring and respectively inversion over Fq. We denote by M k , S k and I k the binary cost of the multiplication, squaring and inversion in the field F q k . For our level of optimization, the crude estimation M = S is enough. When a multiplication by an element of Fq is necessary (for instance a multiplication by a, denoted da, in the doubling of points) we make the coarse estimation that da = Mq. We call D, A, M A and L the cost of a doubling, addition and mixed addition on the elliptic curve and respectively a final line evaluation.

Arithmetic. The complexity of the multiplication M k is a very challenging task in pairingbased cryptography. Several papers present optimized algorithms for the extension over a finite field [START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Peter | Five, six, and seven-term karatsuba-like formulae[END_REF][START_REF] Mrabet | Efficient multiplication in finite field extensions of degree 5[END_REF][START_REF] Aranha | Implementing pairings at the 192-bit security level[END_REF][START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF][START_REF] Sylvain Duquesne | Choosing and generating parameters for low level pairing implementation on BN curves[END_REF][START_REF] Scott | Missing a trick: Karatsuba revisited[END_REF][START_REF] Rodríguez | Special issue in honor of peter lawrence montgomery[END_REF]. Of course, the schoolbook method can always be applied but for a value k, the complexity of M k is k 2 Mq. The tricks for multiplication in F q k are made to decrease the number of multiplications in Mq, but as all magic comes with a price the tricks increase the number of additions in Mq. The ratio R =

Mq

Aq is then the threshold precising if we could use a method over another. In Table 1 we recall classical complexities that are used in pairings, then we summarize results from the literature [START_REF] Peter | Five, six, and seven-term karatsuba-like formulae[END_REF][START_REF] Fan | Comments on "five, six, and seven-term karatsuba-like formulae[END_REF][START_REF] Mrabet | Efficient multiplication in finite field extensions of degree 5[END_REF] which are asymptotically better but are yet to prove their efficiency in the pairing implementations. These latter formulae often achieve the mathematical lower bound for the number of Mq with the cost of increasing the number of Aq. We use the inequalities M11 ≤ M12, M13 ≤ M14, M17 ≤ M18, and M19 ≤ M20.

Classical exponents extension

F q 2 F q 3 F q 4 F q 12 F q 16 F q 18 Fqn M k /Mq 3 5 9 54 81 108 n(n+1) 2 non classical exponents extention F q 5 F q 6 F q 7 F q 11 F q 13 F q 14 F q 15 F q 17 F q 19 ; F q 20 M k /Mq Upper bound [START_REF] Beuchat | Multi-core implementation of the Tate pairing over supersingular elliptic curves[END_REF] We go from the arithmetic complexity to the binary complexity using the crude estimate that Mq counts for w 2 word multiplications, where w is the number of machine words of q. We denote by m32 (resp. m64) the cost of a word multiplication on a 32-bit (resp. 64-bit machine). A comparison of hardware implementation is beyond the scope of this article because it is much more difficult to take into account the dedicated architectures.

Cost of Miller's loop

The Miller loop is a double-and-add algorithm similar to the fast exponentiation. Hence it consists in a number of iterations of the doubling and addition step, plus a final line evaluation. A doubling step followed by an addition step can be done together in a mixed step. The complexity of each step depends on two parameters: the twist of the elliptic curve and the choice of coordinates, as we summarize in Table 2.

Expression of Optimal Ate pairing

The expression of the Optimal Ate pairing is obtained after the reduction of a lattice constructed using the polynomial expression of q(x) and r(x). As a consequence, for each method of construction, we have a specific equation for the Optimal Ate pairing. There are constructions where the value of k also changes the expression of the Optimal Ate pairing. We present in Table 3 the simple expression, of the Miller loop for the Optimal Ate pairing depending on the method of construction and the embedding degree. By raising the Miller expression to the power

q k -1 r
one obtains the expression of the Optimal Ate pairing. When the Optimal Ate pairing is not uniquely defined we refer to the subsection where the reader can find the details on the formulae.

Operation

Complexity

Twist

Sextic twist Quadratic twist Doubling [START_REF] Costello | Faster pairing computations on curves with high-degree twists[END_REF] ( The extended tower number field sieve, exTNFS, encompasses all the variants of NFS: NFS, SNFS, exTNFS-Conj, SexTNFS-JP etc. Let us present briefly the algorithm with a special care on the choices that can be made by an attacker.

Big lines of the algorithm

At a high level, exTNFS on F q k proceeds as follows. Let κ and η be two divisors of k so that k = κη. In the linear algebra stage, the goal is to solve a linear system having twice as many elements as primes less than B (the number of prime ideals in the number fields of f and g of norm less than B). This is done in two steps: filtering where the size of the matrix is greatly reduced and the proper linear algebra computations where the obtained linear system is solved. Due to heuristic arguments in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF], the filtering stage reduces the size of the matrix by a factor log 2 B and the cost of the linear algebra is 2 7 B 2 /(log(B)

log 2 B) 2 .
The results of the linear algebra allow to compute any discrete logarithm in F q k . Since this step is much faster than the sieving and the linear algebra stages, we neglect it in the complexity analysis.

Identifying the best attacks

There is a consensus in the literature [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF][START_REF] Fotiadis | Optimal TNFS-secure pairings on elliptic curves with composite embedding degree[END_REF][START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] that one obtains a precise estimation of the cost of exTNFS by optimizing the following equation:

cost = csieve 2B A log B ρ log 2 (N f ) log 2 (B) -1 ρ log 2 (Ng) log 2 (B) -1 + csieve (2B) 2 A 2 (log B) 2 c 2 filter , (1)
Construction Embedding degree Twist Miller expression for k an odd integer in the Optimal Ate Method 6.2 Table 3: Expression of the Optimal Ate pairing: Miller expression power (q k -1)/r.

k = k No f x 2 ,Q (P ) × l qQ,x 2 Q (P ) v (x 2 +q)Q (P ) Method 6.3 k = 2k 2 f x 2 ,Q (P ) × l -qQ,x 2 Q (P ) Method 6.4 k = 4k 4 fx,Q(P ) × l -qQ,x 2 Q (P ) Method 6.6 k ≡ 0 mod 6 6 (fx,Q(P ) × l-qQ,xQ(P )) k ≡ 3 mod 6 3 Section 4.4 k ≡ 2 mod 6 2 f x 2 ,Q f q x,Q × l s 1 Q,x 2 Q × ls 2 Q,xqQ s0 = x 2 + xq + q 2 , s1 = -xq + q 2 , s2 = q 2 k ≡ 4 mod 6 2 Section 4.4 k ≡ {1, 5} mod 6 No f x 2 ,Q f q -x,Q l s 1 Q,x 2 Q v s 0 Q l q 2 Q,-xqQ v s 1 Q s0 = x 2 -xq + q 2 , s1 = -xq + q 2 Method 6.7 k = 12 2 (f x 2 ,Q l -qQ,x 2 Q )(
where ρ is Dickman's function and A is the number of automorphisms of h multiplied by the number of common number of automorphisms of f and g (which can be upper bounded by ηκ/ gcd(η, κ)) and where csieve, c lin.alg and c filter are constant or slowly increasing functions explained below. The validity condition is that the number of relations is larger than the cardinality of the factor base, which is as follows:

(2A + 1) 2η 2w • ρ log 2 (N f ) log 2 (B) ρ log 2 (Ng) log 2 (B) ≥ 2B log(B) , ( 2
)
where ω is the half of the number of roots of unity of h.

Comparison between two models. The constants csieve, c filter and c lin.alg are functions which increase very slowly so that they can be considered as constants up to one bit of security. In order to evaluate the reduction factor c filter one can take a default value of 20 which is easily achieved for example with the CADO-NFS software on small computations where log 2 q k is less than 300. The reduction factor can only increase for larger computations and with new implementations, but it is hard to give an upper bound to use in security estimations. According to [5, Conjecture 1] one can take as upper bound c filter ≤ log 2 B, and we discuss later that this safe bound gives similar results to the more realistic but unsupported value csieve = 20:

1. (GS model) The textbook description of NFS states that asymptotically, on a computer with infinite memory, the cost of sieving is the cost of some arithmetic operations which are negligible plus the cost of log e log e (B) memory updates. Experiments of the CADO-NFS team show that the value of c lin.alg is the cost of w × log 2 r/64 machine word additions (replace 64 with the machine word length), where w is the average row weight of the matrix and r is the largest prime factor of the cardinality of the discrete logarithm group. This is in accordance with the textbook description of the block Wiedemann algorithm.

Hence, Guillevic and Singh [START_REF] Guillevic | On the alpha value of polynomials in the tower number field sieve algorithm[END_REF] took c filter = 20 and they set csieve = log log B and c lin.alg = 200 log 2 r/64. 2. (BD model) Barbulescu and Duquesne [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] took c filter = log 2 B and chose the constants which best fit the cost reported by the authors of a dozen NFS records of factorization and discrete log: csieve = 1 and c lin.alg = 128. The BD model has the advantage that it is automatically scaled against the RSA key size. Indeed, our study of NFS allows to compare the cost of a given pairing to the cost of RSA-1024, we cannot directly compare a NFS computation to the security of a symmetric cryptosystem. When RSA-1024 was evaluated to 80 bits of security by the NIST recommendations, the cryptography community accepted an exchange rate between the NFS world and the symmetric cryptography. Hence, by scaling against RSA-1024 we are sure to use the same exchange rate. In the following we call normalized GS model the cost of the GS model divided by 4. Let us recall the values of c filter , csieve and c lin.alg used by the models of Barbulescu and Duquesne [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF][START_REF] Fotiadis | Optimal TNFS-secure pairings on elliptic curves with composite embedding degree[END_REF] on the one hand and Guillevic et all [START_REF] Guillevic | On the alpha value of polynomials in the tower number field sieve algorithm[END_REF][START_REF] Guillevic | Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation[END_REF][START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] The actual value of csieve when η > 1 depends on the innovation made on the high-dimensional sieving. At the time when [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] published their model Gremy's implementation [START_REF] Grémy | Higher-dimensional sieving for the number field sieve algorithms[END_REF] had a real-life value of csieve ≈ 20. In a recent record, McGuire and Robinson [START_REF] Mcguire | A new angle on lattice sieving for the number field sieve[END_REF] reduced its value to csieve ≈ 6. So, the model used in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF][START_REF] Fotiadis | Optimal tnfs-secure pairings on elliptic curves with even embedding degree[END_REF] remains a safe lower bound for the security of pairings whereas the model used in [START_REF] Guillevic | On the alpha value of polynomials in the tower number field sieve algorithm[END_REF][START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] corresponds to the state-of-the-art implementations. In this work we use the model of [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. We repeated our key estimations in the normalized GS model and concluded that the same algorithms are the best and that the security estimation in the normalized GS model is the same as the one of the BD model or the pairing has one bit too much security. This is hence not necessary to add the GS estimations alongside the BD estimations. The BD model is at least as conservative as the GS model for all the families. Let us see how to select f , g and h. The values of A and ω are a consequence of the polynomial selection and their choice is explained in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF].

Polynomial selection. The choice of the polynomials f and g for NFS in F q k was the object of many works. When q has a polynomial form one can obtain a product N f Ng which is much smaller than in the general case. This is emphasized by putting an S, for special, before the name of each version of NFS: SNFS, STNFS or SexTNFS.

The special case. Let P ∈ Z[x] and u ∈ Z be such that q = P (u) and

P ∞ = O(log(q k )).
When k is small or prime one can use STNFS [START_REF] Barbulescu | The Towed Number Field Sieve[END_REF], i.e. h an irreducible polynomial of degree k, f = P (x) and g = x -u, or Joux-Pierrot [START_REF] Joux | The special number field sieve in Fpn -application to pairing-friendly constructions[END_REF], i.e. h = t (no tower), f = P (x k + S(x)) and g = x k + S(x) -u where S(x) is a polynomial of degree less than k. When k is large and can be written as k = κη, one can use SexTNFS [START_REF] Kim | The extended tower number field sieve: A new complexity for the medium prime case[END_REF]: one chooses h to be an irreducible polynomial of degree η, f (t, x) = P (x κ + S(x) + t) and g(t, x) = x κ + S(x) + t -u. When gcd(κ, η) = 1 one can drop t in the definition of f and g. In a recent article Guillevic [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] proposed a method similar to the one used to factor Mersenne numbers [START_REF] John | Factoring with cubic integers[END_REF].

The case of arbitrary finite fields. All primes q, of polynomial or non-polynomial form, must withstand the variants of NFS for the general case. When k is small or prime one uses either TNFS [START_REF] Barbulescu | The Towed Number Field Sieve[END_REF], i.e. h is an irreducible polynomial of degree k and f and g are chosen by the "base m" method or the two algorithms of Kleinjung [START_REF] Kleinjung | On polynomial selection for the general number field sieve[END_REF][START_REF] Kleinjung | Polynomial selection[END_REF], or one uses a classical variant, i.e. h = x (no tower) and any of the methods of polynomial selection: GJL [7, Sec. 3.2], [START_REF] Viktorovich | Effective version of the number field sieve for discrete logarithm in a field GF (p k )[END_REF], JLSV1 [49, Sec 3.2], JLSV2 [49, Sec 3.1], Sarkar and Singh's algorithms A,B,C,D [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF][START_REF] Sarkar | New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields[END_REF][START_REF] Sarkar | A generalisation of the conjugation method for polynomial selection for the extended tower number field sieve algorithm[END_REF] and the Conjugation method [START_REF] Barbulescu | Improving NFS for the discrete logarithm problem in non-prime finite fields[END_REF]Sec 3.3]. When k is large and can be written as k = κη, one uses exTNFS [START_REF] Kim | The extended tower number field sieve: A new complexity for the medium prime case[END_REF]: one selects f and g adequated for DLP computations in Fqκ using the afore mentioned methods and then sets h equal to an irreducible polynomial of degree η. If gcd(κ, η) = 1, one follows [START_REF] Kim | Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree[END_REF] and replaces the polynomials with f (x + t) and g(x + t).

Optimizing parameters of for NFS attacks. For each construction of pairings and for each of the security levels 128, 192 and 256, we generated pairings which guarantee that the security on the curve side is greater than or equal to the required security level. The sole condition that q is prime eliminates the existence of small key sizes for many families, for example the families of embedding degree 20 or more have a field size log(q k ) greater that 6000 for 128 bits of security on the curve side. We didn't necessarily check that r is prime at this stage because one generates correct values of q and r when computing complexity and because checking the primality of r here doesn't rule out many families.

Then, for each possible choice of κ, h, f and g, we solved by SageMath scripts the optimization problem consisting in minimizing the cost in Equation ( 1) under the validity condition of Equation ( 2): For each value of log 2 (A) and log 2 (B) up to a precision of 0.01 we estimated experimentally N f and Ng on a sample of 3000 pairs (a, b) chosen randomly in the sieving space. If the field side security is not sufficient, we increase the size of log 2 r and start over. We automatized the attack and the script is available on request. The complete computations took more than 1 CPU year. We summarize the results in the electronic complement available here https://razvanbarbulescu.pages.math.cnrs.fr/Pairings/security.html, as well as in the next section in the tables associated to each family, available at the end of the article. Our results are close to those of Guillevic [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] but the models are slightly different. We don't reproduce here the results of Fotiadis and Martindale [START_REF] Fotiadis | Optimal tnfs-secure pairings on elliptic curves with even embedding degree[END_REF][START_REF] Fotiadis | Optimal TNFS-secure pairings on elliptic curves with composite embedding degree[END_REF] because they were computed by the same method as the other 150 families in our work.

3.3

An example of key size computations: RSA-1024 and MNT of embedding degree 6 RSA 1024. Kleinjung [57] made a precise estimation of the security of a 1024-bit RSA modulus and estimated it to one year on 12 million PCs with processors 2.2 GHz Athlon 64 and 2 GB of main memory. We used the polynomials proposed in Kleinjung's analysis and optimized the parameters in the two models BD and GS. The sieving space consists of the primes up to 56 • 10 12 as special-q's, each of which is made of 2 The GS and the hybrid models give similar results so the value of c filter has a small impact on the analysis. However, the constants csieve and c lin.alg do not correspond to the estimation that RSA 1024 offers 80 bits of security. The parameters A and B correspond relatively well to the ones computed by Kleinjung, the parameter B being slightly larger in the models. Kleinjung didn't discuss in detail the exact choice of log 2 B so that a larger value might be slightly better. But a deeper reason might be that the models don't take into account the state-of-the-art implementation of ECM which is badly optimized to find large primes of size log 2 B ≈ 48.

MNT 6 at 128 bits of security. Let us consider the family of Section 3.3 of the taxonomy [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF]:

the base field is Fq where q is a prime of the form q(u) = 4u 2 + 1, the elliptic curve order #E(Fq) is r(u) = 4u 2 -2u + 1 and the embedding degree equals 6, so the target of the pairing is the multiplicative group of F q 6 . The polynomial form of q is important, and we must compute all the manners to write q(u) as a polynomial with small coefficients. In the case of MNT 6 we take v = 2u and P (v) = v 2 + 1 so that P (v) ≡ 0 (mod q(u)).

One tests in Table 4 the various algorithms and values of κ on the example of MNT-6 such that log 2 q = 700. We didn't compare SexTNFS with Guillevic's polynomial selection because this is used to reduce the degree of the q(t) polynomial, which is 2 for the MNT-6 family.

algorithm κ η h f g field security SexTNFS 1 6 Φ7 x 2 + 1 x -u, log 2 u = 351 199.5 SexTNFS 2 3 t 3 -2t 2 -t -1 x 4 + 1 x 2 -u, log 2 u = 351 141.7 SexTNFS 3 2 t 2 + 1 x 6 + 2tx 3 + t 2 + 1 x 3 + t -u, log 2 u = 351 128.0 SexTNFS 6 1 t x 12 + 2tx 6 + t 2 + 1 x 6 + t -u, log 2 u = 351 148.0 exTNFS base-m 1 6 Φ7 6 i=0 fix i , log 2 u = 98 g1x -g0, log 2 gi = 98 150.5 exTNFS-Conj 2 3 t 3 -2t 2 -t -1 x 4 + 3 g1x 2 -g0, log 2 gi = 351 141.8 exTNFS-Conj 3 2 t 2 + 1 x 6 + 3 vx 3 -u, log 2 gi = 351 128.2 exTNFS-Conj 6 1 t x 12 + 3 g1x 6 -g0, log 2 gi = 351 150.0
Table 4: Security of F q 6 DLP when log 2 q = 700.

We conclude that the algorithm SexTNFS with κ = 3 is the best option. For this choice we optimize the parameters A and B in Table 5. Table 5: The SexTNFS algorithm with κ = 3 on MNT-6 with log 2 q = 700.

model
Because of the small differences in the scaling of the BD and GS models one cannot directly compare the tables computed in the two models. For a given a key size, the two security estimations are within a 2% error. The converse problem, given a security level, compute the key sizes is sensible on the rescaling as we show in Table 6. The GS and the hybrid models correspond to the lower and respectively the upper bound on the key sizes computed in [START_REF] Guillevic | On the alpha value of polynomials in the tower number field sieve algorithm[END_REF], except that the bounds are slightly enlarged to take care of the uncertainty on the Monte Carlo Table 6: Computing log 2 q so that the SexTNFS algorithm with κ = 3 on MNT-6 has a cost of 128 bits of security.

Remark on Murphy's α. The BD and the GS models are within 2% to each other despite the fact that GS uses Murphy's α whereas BD considers α ≈ 0. We conclude that the influence of α is below the estimation error of the two models. The impact of α was analysed in the FSS case, which is analoguous to NFS, in [START_REF] Barbulescu | Selecting polynomials for the function field sieve[END_REF] with the conclusion that the gain is of a few dozen percentages. Experience shows that α has a Gaussian distribution centered about a real value close to 0.6 (the exact value is in [START_REF] Barbulescu | Some mathematical remarks on the polynomial selection in NFS[END_REF]) and a standard deviation which depends on the degree of f which is between 2 and 8 in the record computations. In the S(exT)NFS case, which is the relevant one for all top 5 families of pairings, we only have a few dozen possibilities for f so its α is close to the average or worst, which is positive. In this case BD is a safe realistic lower bound by setting α = 0. In the non-special case, e.g used in MNT, one can have α ≈ -7. The impact on the cost of NFS is

ρ(log 2 N f / log 2 B)/ρ((log 2 (N f ) + α(f ))/ log 2 B)
, where ρ is Dickman's function. Say in a mock example that log 2 N f = 1000 and log 2 B = 70, then NFS is 1.51 times faster, i.e one looses 0.59 bits of security due to Murphy's α. Note that in practice all the record computations make use of polynomials with good α (for instance although Joux doesn't make reference to α in his articles he told the first author that he did compute the number of roots of f modulo small primes to make his choice of polynomials).

Security results

We keep the model of security of Barbulescu and Duquesne [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] which is conservative in that it assumes perfect conditions for an attacker (sieving in TNFS for which no computation record is available, perfect matrix reduction in the filtering step, no memory limitation, ECM having the same performances for slightly larger smoothness bounds). The results are more precise than these obtained by forgetting the o(1) term in the complexity as in [START_REF] Fotiadis | Generating pairing-friendly elliptic curve parameters using sparse families[END_REF][START_REF] Deschamps | Estimating size requirements for pairings: Simulating the tower-NFS algorithm in GF(p n )[END_REF] because we don't omit any term in Equation ( 1). The analysis is also more precise than that of Menezes, Sarkar and Singh [START_REF] Menezes | Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography[END_REF] because we evaluate numerically the size of the norms N f and Ng instead of using the mathematical upper bound.

In the following table we list the known families of pairings with 9 ≤ k ≤ 54, which is a safety margin since the choices among BN, BLS and KSS have k between 12 and 24. The labels follow the format k, value of k, m, a two or three digits number which designs the construction number in the taxonomy [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF], e.g. k9m62 denotes the family having k = 9 in the section 6.2 of the taxonomy, whereas k11m620 denotes the family of k = 11 of section 6.20 in the taxonomy. The sizes of the Dupont-Enge-Morain and Cocks-Pinch were computed in [START_REF] Guillevic | Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation[END_REF] Our results are consistent with those of Guillevic [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF]. At 128 bits of security on the curve side, the security on the field side is larger than or equal to 128 whenever k ≥ 13, in all the models considered in the literature BD, GS or hybrid. Hence, the small difference between our results and the ones in [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] make no change on the key sizes of pairings with k ≥ 13. We note for completeness that for k13method66 and k17method62 Guillevic obtains large differences between the key sizes for a general seed (Table 4 of her work) and a low weight seed (Table 5 of her work). In the case of k = 9, 10, 11 and 12 there are differences between the BD and the GS models, as we write in Table 6. As explained in Section 3.3, the two models are very similar, the difference is due to the security they estimate for RSA-1024. family Table 8: Differences between the field security in the two models of [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] and [START_REF] Guillevic | On the alpha value of polynomials in the tower number field sieve algorithm[END_REF] when k = 12.

Our results can be downloaded at:

https://razvanbarbulescu.pages.math.cnrs.fr/Pairings/Pairings.html

Complexity of Miller's algorithm

In this section, we search for nice parameters for the optimal Ate pairing in order to make a comparison between the most promising families at the 128, 192, and 256 bits security level. We choose the families according to two main criteria:

the popularity of the curve in previous works, which is basically based on a smooth embedding degree multiple of 6; the size of the field F q k , indeed embedding degrees that are not 0 mod 6 were not taken into account in previous works, but as the size of the finite field increases drastically for the most popular curves, we though it worth testing them. The results were interesting as according to our estimation, the most popular curves are no longer the one providing an efficient pairing. We propose seeds for each pairing to match the security results in the previous section. We obtain the cost of Miller's loop in term of operations in Fq and then binary operations. Since we will obtain that the overall cost of the BLS-12 Ate pairings is 3 million 32-bit operations, we keep for the following sections only the pairings whose Miller loop is less than 3 million 32-bit operations. Similarly we keep only a short list which can beat BLS-24 for the 192 and 256 bits of security. In Section 4.1 to Section 4.8, we study the 128 bits security level. We select one promising family by each method of construction and compare them all together in Table 15. For them we compute the cost of the final exponentiation at each level of security. For the comfort of the reader we give all the details of the computations, but one can skip forward to the results of the Miller loop in Table 15.

4.1 Construction 6.2 from [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] In this metafamily of curves we can construct curves whose embedding degree is odd. The curves admit a discriminant D = -1 (we abusively replace D in the sequel by its absolute value), so we have no twist. The complexity of Ate pairing for construction 6.2 is log 2 (u 2 ) doubling step, plus HW (u 2 ) addition step and an extra doubling step for the evaluation of

l qQ,u 2 Q (P ) v (u 2 +q)Q (P ) .
The curves with no twist were not taken into consideration as the pairings computation cannot be improved by the denominator evaluation. We consider them in our study as they are quite resistant to the NFS attack. As a consequence, the size of Fq is smaller for curves without twist and the number of doubling step for the Miller algorithm is also smaller. We computed the arithmetic cost of each step in Table 9.

Operation Complexity affine Complexity projective Complexity Jacobian Modified Jacobian [START_REF] Chatterjee | On instantiating pairing-based protocols with elliptic curves of embedding degree one[END_REF] For the addition step, the difference between the two types of coordinates is more important: in projective coordinates we obtain 3kMq + 18M k and in Jacobian ones we get 3kMq + 33M k . Let α denotes the length of Miller loop and HW (α) be the Hamming Weight of α. The complexity of the pairing evaluation without twist is more efficient for projective coordinates when compared with Jacobian as long as 15HW (α) ≥ log 2 (α). As our goal is to give a first estimation of the pairing complexity, we do not search especially for parameters with very small Hamming weight. Note that the affine coordinates could be more interesting than the projective ones if the complexity of the inversion in F q k is smaller than 20M k . This coarse estimation is obtained by considering that M k = S k and kMq = M k . The expected gain is not important enough, so we don't continue with a precise estimation in this case. The curves of embedding degree 9 are the champion among the curves of construction 6.2 without twists. Yet, they are no match for the curves admitting twists in following constructions.

Doubling step 2M k + S k + I k 3kMq + 12M k + 7S k 3kMq + 10M k + 8S k 8M k + 10S k Addition step 5M k + 2S k + I k 3kMq + 16M k + 2S k 3kMq + 19M k + 14S k 12M k + 5S k

Construction 6.3 from [38]

Using this construction, we obtain elliptic curves having an embedding degree k = 2k , for k an odd number. Those curves have a discriminant D = 1, they admit a twist of degree 2. The optimal Ate pairing for curves constructed using method 6.3 consists in one Miller's algorithm indexed over x 2 , plus an extra line evaluation. The Table 10 presents the value that we find by a quick research and using very large estimation for the cost of arithmetic in the tower field. We used the estimation cost from Table 2 as we are working on elliptic curves with discriminant 1 and a quadratic twist. The smallest number of iterations for Miller's algorithm could be reached for the curve with k = 38, but unfortunately, in practice, we do not find a value of u that makes q and r prime below 15 bits. The smallest size for Fq is theoretically obtained for the curve with embedding degree 26, 34 and 46. Together with the theoretically smallest number of iterations during the Miller algorithm.

In practice, the less expensive Miller's algorithm corresponds to k = 14. For this value we also have the smallest finite field Fq. As a consequence, the best choice for the method 6.3 using a quadratic twist at the 128 bits of security should be the curve with k = 14.

Construction 6.4 from [38]

In this metafamily of curves, we construct curves with embedding degrees 4k where k is an odd integer. The discriminant is D = 1, consequently, curves in this family admit a twist of degree 4.

The optimal Ate pairing for curves constructed using method 6.4 is composed by one Miller's algorithm indexed over x, plus an extra line evaluation. The Table 10 presents some examples of values for u that minimize the number of addition steps during Miller's algorithm. We compare the curves with approximately 10 000 Mq (k = 12, 20, 28) and the curve with the smallest field Fq (k = 44). On a 32 bits architecture, it seems that the curves constructed by method 6.4 with k = 28 provides the most efficient pairing, on a 64 bits architecture, it should be the curve with k = 20. Of course, those results highly depends on the architecture and the implementation.

4.4 Construction 6.6 from [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] In this metafamily of curves, also called BLS when k = 0 mod 6 except when 18 | k, we can construct curves with discriminant D = 3. Hence, in this case the elliptic curves can admit a twist of degree 3 or 6. The method of construction depends on the residue of k modulo 6, and we studied all the families from k = 9 to k = 53, all being possible except those for which 18 divides k, i.e. 18, 36 and 54.

Curves admitting a twist of degree 6. When k = 0 mod 6, then the elliptic curve admits a twist of degree 6. The corresponding embedding degrees are k ∈ {12 (i.e. BLS12), 24 (i.e. BLS24), 30, 36, 42, 48 }.

The smallest number of operations over Fq is obtained for k = 12, but the smallest field is obtained for k = 24.

In order to compare those two curves, we have to estimate the complexity of the Miller algorithm in terms of machine word operations. The Table 12 presents our estimation. We consider that a multiplication over Fq is computed using the schoolbook multiplication. According to our estimation, the optimal Ate pairing seems to be more efficient on BLS24 than on BLS12 curves.

Curves admitting a twist of degree 3. Among the elliptic curves constructed by method 6.6, those for which k = 3 mod 6 admit a twist of degree 3. The expression of the optimal Ate pairing depends on the embedding degree. For each embedding degree k ∈ {15, 21, 27, 33, 39, 45, 51}, we obtain a different short vector that should be used in order to compute the pairing. The expression of the pairing follows a common pattern for k ∈ {15, 33, 51}, respectively for k ∈ {27, 45}; and for k ∈ {21, 39}. For k ∈ {15, 33, 51} using the construction 6.6, we obtain the same pattern for a short vector: [x, -1, 0, . . . 0, -1, 0, . . . , 0]. We give here the definition of an optimal Ate pairing for k = 15.

We choose [x, -1, 0, 0, 0, 0, -1, 0, . . . , 0] as short vector. The expression of the optimal Ate pairing using this vector is the following:

OptAte k15 6.6d3 : G1 × G2 → G3, (P, Q) → ( f x,Q v q+q 6 Q l s 1 Q,xQ v s 0 Q l s 2 Q,-qQ v s 1 Q )(P ) q k -1 r
, where s0 = x -q -q 6 , s1 = -q -q 6 and s2 = -q 6 . When using a twist of degree 3, the vertical line does not vanish during the final exponentiation. We can however simplify the pairing expression. Zhang and Lin in [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF] proposes the latest record for the computation of pairings over curves with a twist of degree 3. They barely improve the result of [START_REF] Costello | Faster pairing computations on curves with high-degree twists[END_REF] but the method is very helpful for the simplification of the optimal Ate pairing in our case. We use Zhang and Lin formulas for the complexity of Miller's algorithm's step 2.

Applying the method developed by Zhang and Lin in [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF], we can make the following transfor-

mation 1 (v Q ) (P ) = X 2 Q +X Q Z Q x P +x 2 q Z 2 Q .
Indeed, using the method developed by Zhang and Lin in [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF], we can transform the fraction

l s 1 Q,xQ v s 0 Q into X 2 s 0 Q -Zs 1 QZxQ(Zs 1 QXxQ -Xs 1 QZxQ) 2 (Zs 1 QYxQ -Ys 1 QZxQ)(Ys 0 Q -Zs 0 QyP )+ Xs 0 QZs 0 QxP + Z 2 s 0 Q x 2 q
which correspond to an extra addition step s0Q = s1Q + xQ. We can apply the same method to the other fraction

l s 2 Q,-qQ v s 1 Q
. The Miller algorithm output the point xQ. We remark that s1Q = s2Q + (-Q q ), thus the evaluation of

l s 2 Q,-qQ v s 1 Q
correspond to the addition step between s2Q and -Q q . We also can notice that s0Q = s1Q + xQ, we then obtain that

l s 1 Q,xQ v s 0 Q
correspond to the addition step between s1Q and xQ the output of Miller's algorithm.In order to perform these computations, we have to precompute the points s2Q = -Q q 6 , s1Q = -Q q + Q q 6 and s0Q = xQ -Q q + Q q 6

. Those computations correspond to two Frobenius Q q and Q q 6 . We follow the example of [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] and the coarse estimation that a Frobenius evaluation cost (k -1)Mq. We want to simplify the evaluation of 1 (v Q ) q+q 6 . The power q + q 6 could be split into two Frobenius evaluation. We will modify the expression of 1 (v Q ) by the following way:

1 (vQ) (P ) = 1 xQ -xP we begin with affine coordinates = (y 2 Q -y 2 q ) (xQ -xP )(y 2 Q -y 2 q ) , = x 2 Q + xQxP + x 2 q y 2 Q -y 2 q .
Using a twist of degree 3, we have that y 2 Q -y 2 q belongs to F q k/d and as a consequence will vanish during the final exponentiation. In [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF], the authors made the assumption that affine coordinates should be more efficient than projective one as long as I k ≤ 5.6M k . In order to be the more general, we will consider only the projective coordinates. We than transform the affine expression into the following projective one:

1 (vQ) (P ) = X 2 Q + XQZQxP + x 2 q Z 2 Q .
When using a twist, the coordinates ZQ belongs to F q k/d . As a consequence, the evaluation of 1 (v Q ) is composed by Sq + kMq + S k/d + M k/d operations. We need two Frobenius maps (one by q and one by q 6 ) plus M k in order to compute 1 (v Q ) q+q 6 . Finally the total complexity of (

f x,Q v q+q 6 Q l s 1 Q,xQ v s 0 Q l s 2 Q,-qQ v s 1 Q
)(P ) is the computation of Miller's algorithm plus

(5k -4)Mq + Sq + S k/d + M k/d + 2M A + 2M k .
We present in Table 11 the estimation of the Miller algorithm when k ∈ {15, 33, 51}.

For k ∈ {27, 45} we obtain a short vector on the pattern [x, 0, . . . 0, 1, 0, . . . , 0]. The optimal Ate pairing expression is then fx,Q

l q 10 Q,xQ v (x+q 10 Q ) (P ) q k -1 r
. An alternative family for the k27method66 family was proposed by Zhang and Lin [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF]. They used a substitution of x by -1/x. The optimal Ate pairing expression is simplified into (fx,Q)

q k -1 r
. Another advantage to the Zhang and Lin family for BSL27 is the existence of x such that q and r are both prime.

For k = 45, the fraction is

l q 16 Q,xQ v (x+q 16 Q) .
As a consequence, for k ∈ {27, 45} the pairing complexity is one Miller execution, plus one addition step. For k = 21, we obtain this short vector [0, 0, 0, 0, 0, 0, x 2 , -x, 1, 0, 0, 0] and for k = 39 this one [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, x 2 , -x, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]. We obtain the following expressions for the pairings

f q 6 x 2 ,Q f q 7 x,Q v q 7 xQ l s 7 Q,x 2 Q v s 6 Q l s 8 Q,-xqQ v s 7 Q v Q vs 8 Q (P ) q k -1 r
, where s6 = x 2 q 6 -xq 7 +q 8 , s7 = -xq 7 +q 8 and s8 = q 8 and

f q 12 x 2 ,Q f q 13 x,Q v q 13 xQ l s 13 Q,x 2 Q v s 12 Q l s 14 Q,-xqQ v s 13 Q v Q v s 14 Q q k -1 r
, where s12 = x 2 q 12 -xq 13 + q 14 , s13 = -xq 13 + q 14 and s14 = q 14 . The pairing computation consists in one Miller execution as its result, fx,Q, is an intermediate step of the computation of f x 2 ,Q . The point xQ can also be saved during the execution of f x 2 ,Q . The output is the point x 2 Q. We must perform 6 Frobenius. The computation of

l s 13 Q,x 2 Q v s 12 Q l s 14 Q,-xQ v s 13 Q
are two extra addition steps. The denominators vs 13 Q and vs 14 Q cost 2(Sq + kMq

+ S k/d + M k/d ).
The complexity of the pairing computation for k = 21 and k = 39 is then one Miller execution

f x 2 ,Q plus the extra computations 26(k -1)Mq + 2M A + 2(Sq + kMq + S k/d + M k/d ) + 5M k + I k .
The Table 11 presents our results. The best candidates among those curves are for k = 15 and k = 27.

Curves admitting a twist of degree 2. The curves constructed using method 6.6 admits a twist of degree 2, when k mod 6 ∈ {2, 4}. This means that k ∈ {14, [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF][START_REF] Canard | Blin-dIDS: Market-compliant and privacy-friendly intrusion detection system over encrypted traffic[END_REF][START_REF] Chatterjee | On instantiating pairing-based protocols with elliptic curves of embedding degree one[END_REF][START_REF]Zcash developers[END_REF][START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF][START_REF] Mrabet | Efficient multiplication in finite field extensions of degree 5[END_REF][START_REF] Fotiadis | Generating pairing-friendly elliptic curve parameters using sparse families[END_REF][START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF][START_REF] Ghammam | Improving the computation of the optimal ate pairing for a high security level[END_REF][START_REF] Guillevic | Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation[END_REF][START_REF] Hess | Pairing lattices[END_REF], 50, 52}. The optimal Ate pairing expression depends on the value of k mod 6. For every k = 2 mod 6 we find the same short vector: [x 2 , x, 1, 0, . . . 0]. The expression of the optimal Ate pairing is

then f x 2 ,Q f q x,Q l s 1 Q,x 2 Q ls 2 Q,xqQ q k -1 r
, where s0 = x 2 + xq + q 2 , s1 = -xq + q 2 and s2 = q 2 . As the results xQ and fx,Q are computed during the computation of f x 2 ,Q we count only one Miller evaluation. Two line evaluations plus 3 Frobenius and 3M k are also necessary.

Its complexity is equal to log 2 (u 2 ) doubling steps, plus HW (u 2 ) addition steps and an extra doubling step for the evaluation of l qQ,x 2 Q (P ). As we do not need the coordinates of the point (x 2 +q)Q, this line evaluation (Le) is cheaper than a full doubling step [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] 4 . We use the projective coordinates, which are better than the affine ones at 128 bits of security [START_REF] Costello | Faster pairing computations on curves with high-degree twists[END_REF][START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF]. The Table 11 presents the cost of the Miller execution. When k = 4 mod 6, one short vector is [x 2 , 0, . . . , 0, -x, 0, . . . , 0, 1, 0, . . . , 0]. For instance, for k = 16, the optimal Ate pairing is then

f x 2 ,Q f q 3 x,Q l s 1 Q,x 2 Q l s 2 Q,-xq 3 Q q k -1 r
, where s0 = x 2 + xq 3 + q 6 , s1 = -xq 3 + q 6 and s2 = q 6 . The cost is one Miller execution, plus 3 Frobenius, two line evaluations, 3M k and one inversion over F q k . Note that D = 1 and the equation of the elliptic curve is y 2 = x 3 + ax. We use the formulas from [START_REF] Costello | Faster pairing computations on curves with high-degree twists[END_REF].

The Ate pairing computation is more efficient. Indeed, it is composed of one execution of the Miller algorithm, which has log 2 (u 2 ) iterations using the denominator elimination. The vertical line v (x 2 +q)Q (P ) belongs to F q k/2 and is eliminated by the final exponentiation. The Ate pairing expression is simplified into:

f x 2 ,Q (P ) × l qQ,x 2 Q (P ) q k -1 r
. Its complexity is equal to log 2 (u 2 ) doubling steps, plus HW (u 2 ) addition steps and an extra doubling step for the evaluation of l qQ,x 2 Q (P ) which is also cheaper than a full doubling step. We use the projective coordinates, which are better than the affine ones at 128 bits of security [START_REF] Costello | Faster pairing computations on curves with high-degree twists[END_REF][START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF].

Curves without twists. The remaining elliptic curves (k = 1 or 5 mod 6) do not admit twists. As we have seen for construction 6.2, even if the theoretical dimension of F q k is smaller for prime embedding degree than for not prime embedding degrees, the lack of denominator elimination is a heavy drawback. The complexity of the optimal Ate pairing computation is one Miller's algorithm execution, two extra addition steps, two Frobenius, hence a total of 5M k + I k operations. Comparison among the method 6.6 (BLS) pairings. The curve k27method66 in the version of Zhang and Lin provides the smallest field Fq and the smallest number of operation over Fq. This curve seems to provide the most efficient choice when considering the Miller loop among the BLS families. We analyse the final exponentiation in Section 5. The curves BLS 24 seems to provide the second most efficient Miller loop. Considering that, the BLS 24 curves have a degree 6 twist and that log 2 (q k 24 ) = 7656 (when log 2 (q k 27 ) = 8058), the comparison with the final exponentiation will decide between this two curves. Potentially, the BLS 15 curves could also be a competitor if a nice arithmetic over F q 5 can be deployed. Indeed, if we compare log 2 (q k 15 ) = 5745 and log 2 (q k 24 ) = 7656, which is roughly the size of the exponent for the final exponentiation, the BLS15 curve provide smaller field but the BLS24 curve can be implemented using the compressed squarings when no practical optimization are available in the literature for k = 15. As a conclusion, a precise implementation and analysis is necessary, in order to choose one between those three families.

4.5 Construction 6.7 from [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] In this metafamily, we can construct curves with discriminant D = 2. They admit a twist of degree 2 if k is even, and no twist otherwise.

Curves having a twist of degree 2. The optimal Ate pairing is different for k = 12, k = 24 and respectively k ∈ {18, 30}. The formulas are presented in Table 3. Table 10 presents the complexity of its implementation. The curves k12m67 and k24m67 are the most promising for this family.

Curves without twists. The optimal Ate pairing is different for k = 15 and k ∈ {9, 21, 27}.

For k = 15, the shortest vector found is [x 4 -1, 1, 0, -1, 1, -1, 0, 1], the cost of the optimal Ate pairing in this case is the evaluation of f x 4 -1,Q , plus 6 addition steps, hence a total of

10M k + I k . For k ∈ {9, 21, 27}, it is f x 4 ,Q l q 5 Q,x 4 Q v [x 4 +q 5 ]Q q k -1 r
.

For k = 21, there are very few possible values for u, so that we could not provide a realistic example of such pairing,

Best candidate for method 6.7. The cost of Miller's loop for the curves without twists is much more expensive than the cost for curve with a quadratic twist. Among the curves with quadratic twists, the curves with k = 12 and k = 24 are the most promising. With k = 12 we have the least number of operation over Fq, with k = 24 the smallest field Fq. According to our estimation, the most efficient pairing for curves constructed with method 6.7 should be implemented over the curve with k = 12.

4.6 Construction 6.20, 6.24 and "+" from [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] We denote by "+" the construction described in [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] that relies on the application of Theorem 6.19 [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF]. The method is to use one construction among 6.2, 6.3, 6.7, 6.20 or 6.24 and made the substitution x 2 → αx 2 in the definition of q and r, where α is a square free positive integer. The best choices for α are described in the Algorithm for Generating Variable-Discriminant Families [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF]. The "+" doesn't change the security (and hence doesn't change the key sizes) because we obtain the same values of k, log 2 q and polynomials in the SexNFS attacks. Indeed, if the fastest SexTNFS attack against a family uses two polynomials f and g, one could use either the same polynomials or f (αx 2 ) and g(αx 2 ) for the "+" family. However, the degree of f and g is "too high" for all the families tested, so an attacker is bound to continue to use f and g. For example, using the "+" method, we generate values of u such that log 2 (u) = 13 for k = 11 and construction 6.20, but for 128 bits of security u should be at least 20 bits. One can use our results and try to generate curves with nice discriminant. It is very important to remark that using the construction "+", we can construct elliptic curve with any discriminant. For instance, in the construction 6.2, when k = 3 mod 6, we cannot use any twist, but with construction "6.2+", we can generate curves with discriminant D = 3 and then use twists in order to improve the computation. By the same way, when k = 0 mod 6, the construction 6.2 allows a quadratic twist, while the construction "6.2+" allows a sextic twist. Using construction 6.20 and 6.24, we obtain elliptic curves with discriminant D = 1. As a consequence, if k is even, we have a quadratic twist, otherwise we do not have a twist. For some embedding degrees, q(x) is reducible so we had to apply the "+" construction. The only drawback of the "+" method is that instead of searching for parameters u of a given bit size b we search for parameters y0 of approximately b/2 bits. This gives less choices and we could not find parameters of low NAF weight for the constructions 6.20+ and 6.24+. We leave it as an open problem the generation of nice parameters and curves using the "+" method.

KSS families from [38]

The KSS families of elliptic curve were introduced by [START_REF] Ezekiel | Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field[END_REF]. It is a promising complete family for specific values of k. They are defined for k = 16, 18, 32, 36, 40 in [START_REF] Ezekiel | Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field[END_REF]. Scott and Guillevic [START_REF] Scott | A new family of pairing-friendly elliptic curves[END_REF] found a similar family with k = 54. The KSS16 and KSS18 were already studied in the literature, we confirm the results from [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF].

For k = 32, an expression of the optimal Ate pairing is fx,Qf q -3,Q f q 8 2,Q ls 1 Q,xQl2q8Q,-3Q, with s1 = -3q + 2q 8 . This is almost the same expression for KSS36 curves, the difference is that the power of q is 7 and not 8. For both KSS32 and KSS36 curves, we search for a value u such that the most significant bits are both 1, this will guarantee that the computation of 3Q is the first addition step during the computation of fx,Q. As a consequence the cost of this optimal Ate pairing is one Miller execution fx,Q plus 3πq + 2L + 4M k + I k .

For k = 40, fx,Qf q 11 2,Q ls 1 Q,xQl2q11Q,-Q, with s1 = -q + 2q 11 . The cost is fx,Q plus 2πq + 2L + 3M k . For k = 54, f q 9 +1
x,Q l q 9 xQ+q 10 Q,xQ l q 10 Q,q 9 xQ [82].

Other families

The article [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] presents a non exhaustive list of pairing-friendly elliptic curve constructions at the beginning of 2010. The MNT curves [START_REF] Miyaji | Characterization of elliptic curve traces under FR-reduction[END_REF] are ordinary curves with embedding degree k = 3, 4, 6. In [START_REF] Page | A comparison of MNT curves and supersingular curves[END_REF][START_REF] Scott | Generating more mnt elliptic curves[END_REF][START_REF] Le | On the near prime-order mnt curves[END_REF], some constructions or examples of MNT curves are given. These parameters are more rare than for the complete families and the algorithms to compute them are more costly, so it is beyond the scope of this article to propose numerical values of u [START_REF] Karabina | On prime-order elliptic curves with embedding degrees k = 3, 4, and 6[END_REF]. A non exhaustive list is available in [START_REF] Lynn | Mnt curves[END_REF]. In our work, we estimate the cost of Miller's loop for this curves, but when considering Table 12, the MNT family is not at all competitive. There were other constructions like [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF][START_REF] Lin | Computing the ate pairing on elliptic curves with embedding degree k= 9[END_REF] not included in [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF]. In 2010, the ρ value was important when considering the efficiency of pairings. The curves constructed in [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF] have embedding degree already included in [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] but with larger ρ. It could be a reason why the results from [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF] were not included in [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF]. However, the curve with embedding degree 15 in [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF] resists better the Kim-Barbulescu attack and we choose to evaluate them in our study. In [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF], other families are constructed with embedding degree k = 12, 13, 14, 24, 48. They do not provide efficient pairings, either because of the lack of discriminant D = 3 (k = 13, 14) or because the Kim-Barbulescu attack is very efficient and the required bit sizes make the pairing less efficient than others families (k = 12, 24, 48). The k = 9 family from [START_REF] Lin | Computing the ate pairing on elliptic curves with embedding degree k= 9[END_REF] and the k = 15 family from [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF] were studied in [START_REF] Fouotsa | Optimal Ate Pairing on Elliptic Curves with Embedding Degree 9, 15 and 27[END_REF], where Fouotsa et al. evaluate the cost the optimal Ate pairing computation for curves with odd embedding degree. The expression of the optimal pairing for this family is nice: (fx,Q)

q k -1 r
. It is the same expression for the family with embedding degree 9 studied by Lin et al. in [START_REF] Lin | Computing the ate pairing on elliptic curves with embedding degree k= 9[END_REF]. Their results were that the k = 9 family is a little bit more expensive than the BN family. We report in Table 14 the estimation of the Miller loop for those families at the 128 bits security level. We add the results for BN curves. According to our new security evaluation, the results from [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] do not provide exactly the 128 bits security, a nice candidate could be u = 1 + 2 3 + 2 13 + 2 14 + 2 32 but the complexity of pairing over BN curves is less efficient than others and we keep the same results as [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. Between those three curves, the construction from [START_REF] Duan | Special polynomial families for generating more suitable elliptic curves for pairing-based cryptosystems[END_REF] with k = 15 is the more efficient when considering the Miller loop. We provide in Section 5 the expression of the final exponentiation in order to decide between those two families. The BN family is no longer a good choice for pairing-based cryptography.

Complexity of the Miller's algorithm at 192 bits security level

We only provide here our most efficient curves for each construction. We select one promising family by method of construction and compare them all together in Table 15. It seems that the curve with k = 27 and construction 6.6 version Zhang Lin could provide the most efficient Miller's algorithm at the 192 bits security level. Other good candidates could be BLS 15, BLS 24 k = 28 construction 6.4 and DCC 15. The final exponentiation could shuffle this ranking. In Section 5 we compare the cost of the final exponentiation in order to determine which curve will provide the most efficient optimal Ate pairing.

Miller's complexity at 256 bit security level

We choose to give the estimation of the pairing computation for the curves such that log 2 (q k ) is not greater then 15 000 and of course to the curves that provide efficient pairing implementation at 128 and 192 bits security level. The curves providing log 2 (q k ) ≤ 15000, are curves without twist and/or expensive pairing computation. We found out that even if the extension field F q k is not very large, the estimation cost for the Miller loop (see Table 15) is much more expensive than curves admitting twists reported in Table 15. According to Table 15, the most efficient Miller's loop would be for the curves k = 28 construction 6.4 in [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF], BLS15 and k27method66. Those curves correspond to the families such that log(q) is smaller than 1 000 bits.

The Computation of the final exponentiation

The computation of Tate pairing and its variants, e.g. Ate, require two steps: Miller's loop (treated in Sections 4, 4.9, and 4.10) and the final exponentiation. None of the two steps is negligible: whereas in the earliest implementations of pairings Miller's loop was more expensive, the final exponentiation has become a significant component of the global computation. For example the family k27method66 which is the champion at 256 bits of security is an exception where the final exponentiation dominates. We do the first analysis of the final exponentiation as previous results in the literature [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF] only consider Miller's loop. Thanks to the cyclotomic polynomial, the final exponentiation can be broken down into two components as follows:

q k -1 r = q k -1 φ k (q) × φ k (q) r
where k is the embedding degree.

In this work, we are only interested in the computation of the second factor, called the hard part, which dominates the computations of the final exponentiation. The computation of the easy part, not treated, requires merely several Frobenius computations (2 if k is even), several multiplications and an inversion in F q k . In Section 4 we explained why we can make a short list of the complete computations based only on the analysis of Miller's loop. Hence we have a preliminary short list consistng only of pairings of embedding degree k = 9, 15, 12, 16; 20; 24 and 28 for the 128 bits security level.

For the security levels 192 and 256, we use the same method presented below, we have just to change the parameter u.

Throughout this section, d denotes the hard part of the final exponentiation, i.e, d = φ k (q) r and d denotes a multiple of d with r not dividing d . We keep the notations Mq, Sq, Iq for the cost of the multiplication, of the squaring and of the inversion in Fq and similarly M k , S k and I k for the operations in F q k as they were introduced in Section 2.3. When it is clear from the context we drop the k index and write M , S and I for M k , S k and I k . We add the notations Eu for an exponentiation by the parameter u and F k for the cost of a Frobenius map in F q k . As we said in the introduction of this work, we computed the final exponentiation (easy part+hard part) of the Optimal Ate pairing defined in several elliptic curves of different embedding degrees. Since we can not give all computation details in this paper version, we invite the reader to check the complete version available on Eprint [START_REF] Barbulescu | A taxonomy of pairings, their security, their complexity[END_REF].

In the current version, we chose to give the details about computing the final exponentiation of the Optimal Ate pairing on elliptic curves of embedding degree k = 12, 18, and 27

The case of k = 12

We showed in Section 4 that for computing Miller loops in the case of elliptic curves of embedding degree k = 12, it is better to consider BLS12 than BN curves. In this paragraph, we compare the cost of the final exponentiation of Optimal Ate pairing in both curves. Recall that q 12 -1 r = (q 6 -1) × (q 2 + 1) × q 4 + q 2 + 1 r .

The computation of the first part of the final exponentiation, i.e: the result of Miller loop raised to power (q 6 -1) × (q 2 + 1), has almost the same cost for the two families (2 q-Frobenius, 2 multiplications and one inversion in F q k a finite field of 5535 bits for BN curves and respectively 5532 bits for BLS curves).

We present now the cost of computing the second part.

BN curves. We briefly present the BN elliptic curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF] which is defined over Fq by E : y 2 =

x 3 + b, where b = 0 is neither a square nor a cube and by a parameter u such that r = 36u 4 + 36u 3 + 18u 2 + 6u + 1 and q = 36u 4 + 36u 3 + 24u 2 + 6u + 1.

The parameter u is chosen such that both q and r are prime numbers, we consider the parameter suggested in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]: u = 2 114 + 2 101 -2 14 -1.

From the given expressions of q and r, the hard part of the final exponentiation can be written as a function of u:

q 4 -q 2 + 1 r = Λ0 + Λ1q + Λ2q 2 + Λ3q 3 with        Λ0 = -36u 3 -30u 2 -18u -2, Λ1 = -36u 3 -18u 2 -12u + 1, Λ2 = 6u 2 + 1, Λ3 = 1.
There are many efficient methods for computing the hard part of the final exponentiation presented in [START_REF] Scott | On the final exponentiation for calculating pairings on ordinary elliptic curves[END_REF][START_REF] Jun Devegili | Implementing cryptographic pairings over Barreto-Naehrig curves[END_REF][START_REF] Fuentes Castañeda | Faster hashing to G2[END_REF] and in [START_REF] Duquesne | Memory-saving computation of the pairing final exponentiation on BN curves[END_REF]. In this paragraph we present our new developments of the multiple of this part presented by Fuentes et al. in [START_REF] Fuentes Castañeda | Faster hashing to G2[END_REF], which makes the computation of the part in question more efficient (we know that an exponent of a pairing is a pairing). So we give the following presentation: 2u 6u 2 + 3u + 1 q 4 (u) + q 2 (u) + 1 r(u) = 12u 2 (u + 1) -6u 2 + 4u -1)q 3 + (12u 2 (u + 1) -6u 2 + 6u q 2 + 12u 2 (u + 1) -6u 2 + 4u)q + (12u 2 (u + 1) + 6u + 1 ,

= Λ 3 q 3 + Λ 2 q 2 + Λ 1 q + Λ 0 , with,        Λ 0 = (12u 2 (u + 1) + 6u) + 1 = c + 1, Λ 1 = (α2 -2u), Λ 2 = c -6u 2 , Λ 3 = α1 -1.
Since the parameter u is odd, an exponentiation by u + 1 is more efficient than by u since HW (u + 1) < HW (u). Therefore, our algorithm for computing the hard part of the final exponentiation, is more efficient than the methods presented in [START_REF] Duquesne | Memory-saving computation of the pairing final exponentiation on BN curves[END_REF] and [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. Our algorithm requires 2Eu + Eu+1 + 9M12 + 3S12 + 3F12. The overall cost of the final exponentiation is 3Eu + 10M12 + 3S12 + 5F12. In term of complexity in Fq, our method for computing the final exponentiation requires 7381M + I when we use the cyclotomic squaring and 5598M + 4I in the case of considering the compressed squaring in the cyclotomic subgroup.

BLS12 curves. BLS12 [START_REF] Paulo | Constructing elliptic curves with prescribed embedding degrees[END_REF] are defined over Fq by E : y 2 = x 3 + b and by a parameter u ∈ Z such that:

   q = (u -1) 2 (u 4 -u 2 + 1)/3 + u, r = u 4 -u 2 + 1, t = u + 1.
For computing the hard part of the final exponentiation, we refer to the algorithm presented in [START_REF] Ghammam | Improving the computation of the optimal ate pairing for a high security level[END_REF]. For the 128 security level, we consider the parameter u = -2 77 + 2 50 + 2 33 . Then, in terms of complexity in Fq, the final exponentiation requires 8151M + I when we use the cyclotomic squaring and 6188M + 6I in the case of considering the compressed squaring in the cyclotomic subgroup.

For the 192 security level, we consider the parameter u = -2 207 +2 206 +2 105 +2 11 +2 7 +2 6 +2 2 +2. Then, in terms of complexity in Fq, the final exponentiation requires 21201M + I when we use the cyclotomic squaring and 15500M + 6I in the case of considering the compressed squaring in the cyclotomic subgroup.

The case of k = 18

In this paragraph, we give the cost of computing the final exponentiation of the Optimal Ate pairing on elliptic curves of embedding degree k = 18.

For the complexity of computing the final exponentiation for the 128-bit security level we consider the parameter u presented in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] u = 2 44 + 2 22 -2 9 + 2 6 requires 20141M+I when considering the cyclotomic squaring and 17831M+8I when considering the compressed squaring.

For the 192 security level, we consider also the parameter u proposed in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] u = 2 6 -2 26 -2 31 -2 85 . With this parameter, the computation of the final exponentiation requires 30473M+I when considering the cyclotomic squaring and 24719M+8I when considering the compressed squaring.

For the 256 security level, we consider the parameter u proposed in 4.10, u = 2 -2 3 -2 7 -2 12 + 2 15 + 2 16 + 2 20 + 2 174 . The complexity of the final exponentiation when using this parameter requires 55925M+I when considering the cyclotomic squaring and 42695M+8I when considering the compressed squaring (41687M+8I in the case of using the parameter u proposed in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] u = 2 186 + 2 75 -2 22 + 2 4 ).

The case of k = 24

BLS curves of embedding degree 24 are important candidates for computing Optimal Ate pairing for both of the 128 and 192 security levels [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. Recall that BLS24 curves are families of elliptic curves defined over Fq by the parametrization:

   q = (u -1) 2 (u 8 -u 4 + 1)/3 + u, r = u 8 -u 4 + 1, t = u + 1.
The final exponentiation for BLS24 curves is decomposed into two parts thanks to the cyclotomic polynomial q 24 -1 r = q 12 -1 q 4 + 1 q 8 -q 4 + 1 r .

The hard part of the final exponentiation can be decomposed in basis q [81] as:

q 8 -q 4 + 1 r = φ(24)-1 i=0 Λiq i = Λ0 + Λ1q + Λ2q 2 + • • • + Λ7q 7 ,
where

                       Λ0 = u 9 -2u 8 + u 7 -u 5 + 2u 4 -u 3 + 3, Λ1 = u 8 -2u 7 + u 6 -u 4 + 2u 3 -u 2 , Λ2 = u 7 -2u 6 + u 5 -u 3 + 2u 2 -u, Λ3 = u 6 -2u 5 + u 4 -u 2 + 2u -1, Λ4 = u 5 -2u 4 + u 3 , Λ5 = u 4 -2u 3 + u 2 , Λ6 = u 3 -2u 2 + u, Λ7 = u 2 -2u + 1.
The best result in the literature to our knowledge is the one presented in [START_REF] Ghammam | Improving the computation of the optimal ate pairing for a high security level[END_REF]. In their work, the hard part of the final exponentiation is presented as follows:

Λ0 = Λ1u + 3, Λ1 = Λ2u, Λ2 = Λ3u, Λ3 = Λ4u -Λ7, Λ4 = Λ5u, Λ5 = Λ6u, Λ6 = Λ7u, Λ7 = u 2 -2u + 1.
The overall cost of the hard part of the final exponentiation is then 8 exponentiations by u, one exponentiation by u/2 (since u is even), one squaring, 10 multiplications and 7-Frobenius operations in F q 24 . Then, we need to add two Frobenius operations, two multiplications and one inversion in F q 24 to compute the final exponentiation. For computing the Optimal ate pairing over BLS24 curves for the 128 bit security level, we consider the arithmetic presented in [START_REF] Aranha | Implementing pairings at the 192-bit security level[END_REF] and the parameter u = -2 32 + 2 28 + 2 12 proposed in Section 4 the final exponentiation requires 18732 multiplications and 10 Inversions in Fq when considering the compressed squaring and 23400 multiplications and one inversion when the cyclotomic squaring is considered.

For computing the Optimal ate pairing over BLS24 curves for the 192 bit security level, we consider the parameter u = -2 56 -2 43 + 2 9 -2 6 proposed in Section 4.9 the final exponentiation requires 27985 multiplications and 10 Inversions in Fq when considering the compressed squaring and 36573 multiplications and one inversion when the cyclotomic squaring is considered. For computing the Optimal ate pairing over BLS24 curves for the 256 bit security level, we consider the parameter u = 2 103 2 101 + 2 68 + 2 50 proposed in Section 4.9 the final exponentiation requires 43213 multiplications and 10 Inversions in Fq when considering the compressed squaring and 59415 multiplications and one inversion when the cyclotomic squaring is considered.

The case of k = 27

Elliptic curves of embedding degree k = 27 are suitable for computing Miller loop. In this paragraph, we give the computation of the final exponentiation on this category of curves which is defined by the parameter u as follow [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF]    q = 1/3(u -1) 2 (u 18 + u 9 + 1) + u, r = 1/3(u 18 + u 9 + 1), t = u + 1.

In this case, the final exponentiation consists on computing q 27 -1 r = (q 9 -1) q 18 + q 9 + 1 r .

Then, the representation of the hard part of the final exponentiation can be given as described in [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF] as follow.

(u -1) 2 × (q 9 + u 9 + 1) × (q 8 + uq 7 + u 2 q 6 + u 3 q 5 + • • • + u 7 q + u 8 ) + 3.

This decomposition requires one inversion in F q 27 , 17 exponentiations by u, 2 exponentiations by (u -1), 11 multiplications, 2 q 9 , q, q 2 , q 3 , q 4 , q5 , q6 , q 7 and q 8 Frobenius maps. When considering our parameter u = 2 3 + 2 4 + 2 11 + 2 15 given in Section 4 the overall cost of the final exponentiation for computing the final exponentiation for the 128-bit security level is then 76980 multiplications and one inversion in Fq.

For the 192-bit security level, we consider the parameter u = -2 5 + 2 8 + 2 12 + 2 16 + 2 21 + 2 22 proposed in Section 4.9, and then, the cost of computing the final exponentiation of the Optimal ate pairing is about 96626 multiplications and one inversion in Fq.

For the 256 bit security level, we consider the parameter u = -2 2 -2 4 + 2 10 -2 28 proposed in Section 4.9, and then, the cost of computing the final exponentiation of the Optimal ate pairing is about 112625 multiplications and one inversion in Fq.

In the following Tables, we summarize the cost of the final exponentiation of the Optimal Ate pairing in the target elliptic curves for each security level: 128, 192 and 256.

Conclusion and recommendations

In this article we update the key size for pairing-based cryptography according to the latest discrete logarithm attack. We unify the results according of the NFS attack and apply them to more than 150 pairing-friendly elliptic curves. Our motivation was that the NFS attack is more efficient on BN and BLS 12 elliptic curves which were the most popular for the implementation of pairing due to their efficient arithmetic. Once we obtain the security evaluation of the curves, we compare the efficiency of the optimal Ate computation on them. To do so, we first give an estimation for the Miller loop, and we evaluate the final exponentiation for the most promising curves. Indeed, the Miller loop alone is not sufficient to evaluate the complexity of the pairing computation as the final exponentiation represents the half of optimal Ate pairing computation. We evaluate the final exponentiation only for curves with a very efficient Miller loop, the criteria of efficiency being the complexity of the Miller loop for the BLS-12. Table 17 presents the cost of the optimal Ate pairing for our short list of candidates at the 128, 192, and 256-bits security level.

Some informal remarks

We deliberately avoided to use our insight to eliminate bad candidates because we wanted to be sure that we don't miss any good pairing. We can however make a list of a posteori informal remarks:

-At 128 bits of security, among the good candidates in Table 17, the bit size of the target field varies between 5281 and 7642 bits, which represents a 45% difference. A larger field means a larger cost of the arithmetic, but this remains less than the factor three which is the advantage of multiples of 6 when compared to degrees which are coprime to 6. All the good pairings at 128 bits of security in Table 17 are multiples of 6. -Fifteen is not the new twelve. 5 A simplified manner to choose k is to take kρ equal to the bit size of the target field, which is now about 5000 bits for 128 bits of security, divided by the lower bound on r which is 256. Hence one could have set kρ = 20 and, for many BLS pairings ρ = 1.33 so a possible guess of k is 15. But the above remark says that 12 and 24 are better candidates because they are multiples of 6. k = 27 at 256 bits is a compromise between good arithmetic and strength against the TNFS attack. 6 Indeed, 27 has a unique divisor between 2 and 8 so an NFS attack can be done in a restricted number of manners. At 256 bits of security, an ideal situation would be to have 5, 6 or 7 as a divisor, so 3 is a bad approximation of the optimal parameters. Hence k27method66 resists well to the TNFS attack albeit not as good as a pairing of prime degree. In the same time 27 is not coprime to 6 so it has a fast pairing. -BLS-24 is the new challenger of BLS-12 at the 128 bits security level. The detailed analysis of the security, the complexity of the Miller loop and the final exponentiation shows that the two pairings are relatively similar. A detail which attracts our attention is the cost of the arithmetic in a field F q 12 vs. F q 24 when the field has approximately 100 machine words.

The arithmetic in Fq is done using a schoolbook algorithm because q has few machine words, whereas the field extension arithmetic is done using Karatsuba tricks. This could help BLS-24 to be a good alternative to BLS-12. To conclude, if one wants an efficient pairing implementation using existing arithmetic that will support several security levels the BLS 24 curve is the one to be chosen, even if at the 256 security level k27method66 is twice more efficient according to our estimation. On another hand, if we are willing to find the most efficient pairing, further works are necessary to improve the final exponentiation for the k27method66 family. It is possible that with a more efficient final exponentiation, the k27method66 would provide the most efficient pairing at the 192 or 128-bits security level. Indeed, the Miller algorithm for k27method66 is very efficient at each security level, the overall cost of pairing is penalized by the final exponentiation. [START_REF] Boneh | Short signatures from the Weil pairing[END_REF][START_REF] Costello | Faster pairing computations on curves with high-degree twists[END_REF][START_REF] Jun Devegili | Implementing cryptographic pairings over Barreto-Naehrig curves[END_REF][START_REF] Mrabet | Guide to Pairing-Based Cryptography[END_REF][START_REF] Fotiadis | Optimal tnfs-secure pairings on elliptic curves with even embedding degree[END_REF][START_REF] Fouotsa | Optimal Ate Pairing on Elliptic Curves with Embedding Degree 9, 15 and 27[END_REF][START_REF] Grémy | Higher-dimensional sieving for the number field sieve algorithms[END_REF][START_REF] Guillevic | A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level[END_REF][START_REF] Hess | The Eta pairing revisited[END_REF][START_REF] Joux | The number field sieve in the medium prime case[END_REF][START_REF]Identity-Based Cryptography[END_REF][START_REF] Karabina | On prime-order elliptic curves with embedding degrees k = 3, 4, and 6[END_REF] no value for u below 2 12

Table 1 :

 1 Optimized complexities of the multiplication over extension fields

	17 22 46 49 53	75	94	105
	M k /Mq Lower bound 9 11 13 33 39 39	45	65	99

Table 2 :

 2 Complexity of Miller's steps using twists 3 Overview of the NFS attacks

  Let h(t) be a polynomial of degree η in Z[t] which is irreducible modulo q, and call ω a root of h(t) in Fq[t]/ h . Then select two polynomials f (t, x) and g(t, x) in Z[t, x] such that f (ω, x) and g(ω, x) have a common irreducible factor of degree κ in Fq(ω) = Fqη .

	This
	step, called polynomial selection, takes a negligible time but determines the cost of the whole
	algorithm.
	In the sieving stage, for a given parameter A, one considers the pairs (a(t), b(t)) ∈ Z[t] 2 of degree
	less than η such that max( a ∞, b ∞) ≤ A. We call norms of (a, b) the integers N f (a, b) =
	Rest(Resx(a(t) -xb(t), f (t, x)), h(t)) and Ng(a, b) = Rest(Resx(a(t) -xb(t), g(t, x)), h(t)). Given
	a parameter B, the sieving stage outputs the list of (almost) all pairs (a, b) such that N f (a, b)
	and Ng(a, b) are B-smooth, i.e. all their prime factors are less than B.

  on the other hand.

	model BD	normalized GS comment
	c filter log 2 B	20	BD is an upper bound based on [5, Conjecture 1], GS is easily obtained by

the CADO software when factoring 100 digit integers and one can hope to have at least this value in future NFS records csieve 1

1 4 log log B ≈ 1

The BD constant is a lower bound based on the records in the literature, the GS constant is based on the textbook description of NFS. For the security table values this is actually between 1 and 1.5. c lin.alg 128 50 |r|/64 ≈ 128 BD is an average of the records and could slowly increase with r, GS varies between 100 and 150 at 128 bits of security.

  Let us now do the optimization of the parameters for the BD and GS models. The linear algebra cost is proportional to bit size length of the prime in the linear algebra: r for discrete logarithm and 2 for factoring, so we divide c lin.alg by 32 for BD and by log 2 r for GS. We call BD and GS the models in the literature and we call hybrid the GS model where c filter equals its value in the BD model.

	model	c filter	csieve	c lin.alg log 2 A log 2 B log 2 cost
	BD model log 2 B	1	128/32 39.6 48.1	80.09
	GS model 20 log(log(B)) 200/32 40.0 49.2	82.93
	hybrid	log 2 B log(log(B)) 200/32 40.0 48.1	82.70
		NIST recommendations	80

15

• 2

16

pairs (a, b). It has the same cardinality and pairs (a, b) of the same size as if, in a context without special-q, one used log 2 A = 38.84. The large prime bound is taken B = log 2 B = 42.

  estimation of the norms. The BD key size is 6.6% larger than the lower bound fond with the GS model. Note that the GS keys are correct in the BD model but not vice-versa.

	model	c filter	csieve	c lin.alg log 2 A log 2 B log 2 q log 2 (q 6 )
	BD model log 2 B	1	128 31.25 70.90 700	4212
	GS model 20 log(log(B)) 200/32 32.0 73.6 666	3948
	hybrid	log 2 B log(log(B)) 200/32 32.0 73.6 674	4008

  and are much slower than the other families; we don't keep them in our results. To verify the results one has to use Equation 1 and compute the best values of log 2 A and log 2 B (we provide our results and scripts on demand and we will maintain an online taxonomy together with the files which determine the security results).

	k9method62 k27method66 7638. 175 exTNFS-Conj k=3 11840. 218 exTNFS-Conj k=3 15980. STNFS-G k=1 5940. 128 STNFS k=1 14450. 192 STNFS k=1 25340. STNFS k=1
	k9method66 k27method67 14360. 242 exTNFS-Conj k=3 18360. 275 exTNFS-Conj k=3 24770. exTNFS-Conj k=3 5890. 128 STNFS k=1 12730. 192 STNFS k=1 29320. STNFS k=1
	k9method67 k27methodBLS 7697. 175 exTNFS-Conj k=3 11540. 215 exTNFS-Conj k=3 16100. STNFS-G k=1 4764. 129 STNFS-G k=1 12570. 192 STNFS-G k=1 23260. STNFS-G k=1
	k9methodLZZW 5314. 128 STNFS k=1 k28method53 11200. 233 STNFS k=1 16580. 247 STNFS k=1 12800. 192 STNFS k=1 21950. STNFS k=1 21800. STNFS k=1
	k10method53 k28method64 14280. 207 SexTNFS k=2 5306. 128 SexTNFS k=2 14280. 207 SexTNFS k=2 12250. 192 SexTNFS k=2 25480. SexTNFS k=2 21450. SexTNFS k=2
	k10method624 4695. 128 SexTNFS k=2 k28method66 10140. 191 exTNFS-Conj k=4 15190. 230 exTNFS-Conj k=4 20260. exTNFS-Conj k=7 9825. 192 SexTNFS k=2 22120. SexTNFS k=5
	k10method63 k29method62 8292. 232 STNFS-G k=1 5720. 128 STNFS k=1 15960. 245 STNFS-G k=1 13630. 192 SexTNFS k=2 18580. STNFS-G k=1 23080. SexTNFS k=2
	k10method66 k29method66 18650. 268 STNFS-G k=1 5104. 142 STNFS k=1 18650. 268 STNFS-G k=1 14180. 192 STNFS k=1 18650. STNFS-G k=1 30380. STNFS k=1
	k11method62 k30method53 13260. 209 STNFS k=1 5412. 128 STNFS k=1 19500. 236 STNFS k=1 14990. 192 STNFS k=1 25740. STNFS k=1 24860. STNFS k=1
	k11method620 5258. 128 STNFS k=1 k30method63 16270. 241 STNFS-G k=1 24420. 258 STNFS k=1 10140. 192 STNFS k=1 32580. STNFS k=1 17400. STNFS k=1
	k11method66 k30method66 11470. 212 exTNFS-Conj k=3 17230. 237 exTNFS-Conj k=5 22990. exTNFS-Conj k=6 3896. 128 STNFS-G k=1 14630. 192 STNFS k=1 27700. STNFS k=1
	BN k30method67	5534. 128 SexTNFS k=2 16510. 231 exTNFS-Conj k=5 20900. 260 exTNFS-Conj k=5 27760. exTNFS-Conj k=6 13120. 192 SexTNFS k=3 25310. SexTNFS k=3
	k12method53 k31method62 18650. 266 STNFS-G k=1 5138. 130 SexTNFS k=2 18650. 266 STNFS-G k=1 9962. 193 STNFS k=1 18650. STNFS-G k=1 26590. SexTNFS k=2
	k12method64 k31method66 21780. 240 STNFS-G k=1 6120. 134 SexTNFS k=2 21780. 240 STNFS-G k=1 12550. 192 SexTNFS k=2 23900. STNFS-G k=1 24220. SexTNFS k=3
	k12method66 k32method613 14830. 227 exTNFS-Conj k=4 14870. 281 exTNFS-Conj k=4 19440. exTNFS-Conj k=4 5525. 128 SexTNFS k=2 14960. 192 SexTNFS k=2 26120. SexTNFS k=2
	k12method67 k32method66 13010. 210 exTNFS-Conj k=4 13010. 210 exTNFS-Conj k=4 19330. exTNFS-Conj k=4 5340. 128 STNFS k=1 14750. 192 SexTNFS k=2 20120. SexTNFS k=2
	k13method62 k48method66 13750. 290 STNFS k=1 4565. 128 STNFS-G k=1 20660. 304 STNFS k=1 13690. 192 STNFS k=1 27570. STNFS k=1 28830. STNFS-G k=1
	KSS54	k13method66 17060. 480 exTNFS-Conj k=2 23900. 360 STNFS-G k=1 4083. 154 STNFS-G k=1 8472. 192 STNFS-G k=1 31580. STNFS-G k=1 18940. STNFS-G k=1
	k3MNT	k14method63 4211. 128 SexTNFS k=3 5348. 128 STNFS k=1 9371. 192 SexTNFS k=3 13330. 192 STNFS k=1 16090. exTNFS-Conj k=3 21640. SexTNFS k=2
	k4MNT	k14method66 4344. 128 SexTNFS k=4 4906. 154 STNFS k=1 10520. 192 exTNFS-Conj k=4 19040. exTNFS-Conj k=4 11180. 192 STNFS-G k=1 27980. STNFS-G k=1
	k6MNT	k15method53 4140. 128 SexTNFS k=3 6495. 145 STNFS k=1 9792. 192 SexTNFS k=6 13520. 192 STNFS k=1 21010. SexTNFS k=6 27560. STNFS k=1
		k15method62	8131. 175 exTNFS-Conj k=5 12210. 201 exTNFS-Conj k=5 20050. exTNFS-Conj k=5
		k15method620 7650. 158 STNFS k=1	12270. 192 STNFS k=1	21330. STNFS k=1
		k15method66	5736. 138 STNFS k=1	14150. 192 STNFS k=1	26980. STNFS k=1
		k15method67	9104. 188 STNFS-G k=1	12030. 206 STNFS-G k=1	23040. STNFS-G k=1
		k15methodDCC 5745. 139 STNFS k=1	13940. 192 STNFS-G k=1	26980. STNFS-G k=1
		k16method66	5608. 146 exTNFS-Conj k=4 10090. 192 exTNFS-Conj k=4 18940. exTNFS-Conj k=4
		k16methodKSS 5281. 142 STNFS k=1	13360. 192 STNFS k=1	23760. SexTNFS-G k=2
		k17method62	5152. 183 STNFS k=1	11270. 193 STNFS-G k=1	20560. STNFS-G k=1
		k17method66	5914. 149 STNFS-G k=1	10110. 192 STNFS-G k=1	25600. STNFS-G k=1
		k18method624 7929. 152 SexTNFS k=2	13330. 192 SexTNFS k=2	23650. SexTNFS k=2
		k18method63	8412. 155 STNFS k=1	14620. 192 STNFS k=1	16990. SexTNFS k=2
		k18method67	7243. 156 STNFS-G k=1	11630. 193 STNFS-G k=1	21320. STNFS-G k=1
		k18methodKSS 6401. 156 STNFS k=1	12180. 192 STNFS k=1	26060. SexTNFS-G k=2
		k19method62	5754. 145 STNFS-G k=1	11290. 194 STNFS-G k=1	20800. STNFS-G k=1
		k19method66	6041. 233 STNFS-G k=1	8180. 241 STNFS-G k=1	12060. STNFS-G k=1
		k20method64	7640. 151 SexTNFS k=2	14660. 192 SexTNFS k=2	26960. SexTNFS k=2
		k20method66	7013. 161 exTNFS-Conj k=4 10970. 195 exTNFS-Conj k=5 19930. exTNFS-Conj k=5
		k21method62	10500. 206 exTNFS-Conj k=3 15420. 244 exTNFS-Conj k=7 20570. exTNFS-Conj k=7
		k21method66	7135. 171 exTNFS-Conj k=3 10720. 207 exTNFS-Conj k=3 25560. STNFS-G k=1
		k21method67	12560. 227 exTNFS-Conj k=3 15190. 235 exTNFS-Conj k=7 19910. exTNFS-Conj k=7
		k22method63	10940. 161 STNFS k=1	14600. 193 STNFS k=1	27410. STNFS-G k=1
		k22method66	7901. 197 STNFS-G k=1	11830. 223 STNFS-G k=1	18170. STNFS-G k=1
		k23method62	10250. 192 STNFS-G k=1	10250. 192 STNFS-G k=1	21650. STNFS-G k=1
		k23method66	9614. 202 STNFS-G k=1	9614. 205 STNFS-G k=1	19290. STNFS-G k=1
		k24method66	7642. 167 STNFS k=1	13340. 192 STNFS k=1	24440. STNFS-G k=1
		k24method67	9144. 173 STNFS k=1	13750. 200 STNFS k=1	26930. STNFS-G k=1
		k25method62	11820. 201 exTNFS-Conj k=5 13130. 210 exTNFS-Conj k=5 20880. STNFS-G k=1
		k25method66	12160. 180 STNFS-G k=1	15130. 192 STNFS-G k=1	29990. STNFS-G k=1
		k26method624 8340. 172 SexTNFS k=2	12180. 212 STNFS k=1	18850. STNFS k=1
		k26method63	8346. 184 STNFS-G k=1	12440. 203 SexTNFS-G k=2 23670. SexTNFS-G k=2
		k26method66	7758. 209 STNFS-G k=1	11610. 234 STNFS-G k=1	16040. STNFS-G k=1
		k27method62	14810. 251 exTNFS-Conj k=3 17200. 266 exTNFS-Conj k=3 22250. exTNFS-Conj k=3

Table 9 :

 9 Complexity of Miller's steps without twistWe use the estimation M k = S k and find that the doubling step in projective coordinates has a cost of 3kMq + 19M k . Compare this to that in Jacobian coordinates which is 3kMq + 18M k .

  +2 6 +2 9 -2 12 -2 15 -2 19 +2 22 +2 5 +2 7 +2 8 +2 10 +2 12 +2 13 +2 22 -2 7 + 2 10 + 2 11 + 2 14 746 + 2 5 + 2 6 + 2 8 + 2 10 + 2 14 + 2 24 525 + 2 4 + 2 7 + 2 9 + 2 10 + 2 12 + 2 14 950 56D+34M A+6M A+10M k +I k 85 050Mq + I k 21 7 1 + 2 + 2 4 + 2 7 -2 10 + 2 13 1100 52D+23M A+M A+M k +I k 97 135Mq + I k 27 4 1 -2 2 -2 7 + 2 10 + 2 11 1218 48D+16M A+M A+M k +I k 157 460Mq + I k 33, 39, 45 no value for u below 2 10

				Method 6.2
	k	min log 2 q	min log 2 u	u	log 2 q	Miller's cost	≈
	9		22	-1+2 3 +2 4 +2 5 +2 9 +2 10 +2 22	482	44D+20A+1D+M k +I k	31 155Mq + I k
	11		13	-1 + 2 8 + 2 14	363	28D+4M A+1D+M k +I k	65 316Mq + I k
	13		12	1+2+2 3 +2 4 +2 8 +2 10 +2 14 +2 20	599	20D+14A+1D+M k +I k	110 085Mq + I k
	15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35	complexity higher than 203 985Mq + I k
	37, 39, 43, 45	no value for u below 2 11
				Method 6.3
	10		40	1 + 2 3 + 2 4 + 2 8 + 2 39 + 2 40	432	79D+15M A+L+M k	23 816
	14		21	1-2 2 390	44D+14M A+L+M k	12 228
	18		21	1+2+2 3 482	44D+11M A+L+M k	23 458
	22		19	1 + 2 + 2 4 + 2 14 + 2 15	403	30D+9M A+L+M k	78 423
	26		11	1 + 2 8 + 2 12	360	24D+5M A+L+M k	81 248
	30		16	1 + 2 2 + 2 3 -2 10 + 2 14 + 2 16	552	32D+11M A+L+M k	26 687
	34		8	1 -2 4 + 2 10 + 2 14	533	28D+6M A+L+M k	165 138
	38		5	1 + 2 3 + 2 9 + 2 11 + 2 17	713	34D+11M A+L+M k	268 200
	42		11	1 + 2 4 + 2 7 + 2 8 + 2 10 + 2 11	539	24D+7M A+L+M k	225 150
	46		6	1 + 2 + 2 9 + 2 10 + 2 13	660	26D+9M A+L+M k	315 415
	50		9	1 + 2 4 28D+9M A+L+M k	50 603
	54		7	1 + 2 + 2 3 + 2 5 + 2 8 + 2 9 + 2 11	664	23D+9M A+L+M k	74 466
				Method 6.4
	12 63, 7	1 + 2 + 2 3 + 2 8 + 2 9 + 2 11 + 2 64	510	64D+6M A+L+M k	10 141
	20 31, 8	1 + 2 4 + 2 16 + 2 32	383	32D+3M A+L+M k	9 116
	28 21, 8	1 + 2 + 2 3 + 2 4 + 2 8 + 2 9 + 2 22	350	22D+6M A+L+M k	10 278
	36 21, 9	1 + 2 2 + 2 10 + 2 14 + 2 16 + 2 22	438	22D+5M A+L+M k	18 901
	44 12, 9	1 + 2 7 + 2 8 + 2 12 + 2 14	342	14D+4M A+L+M k	59480
	52 10, 9	1 -2 6 + 2 9 + 2 12 + 2 13	380	13D+4M A+L+M k	81134
				Method 6.7, degree 2 twist
	12		32	1 + 2 14 + 2 17 + 2 32	445	64D+9M A+L+M k	13 976
	24		4.4	1 + 2 2 + 2 8 + 2 9 + 2 32	381	32D+4M A+L+M k	20 192
	30		10	1 + 2 + 2 5 -2 7 + 2 12	691	48D+25M A+L+M k	56 133
	36		16	1 + 2 3 + 2 5 -2 8 + 2 11 + 2 13 + 2 16	547	32D+13M A+L+M k	56 963
	42		9	no value for u below 2 11
	48		24 1 + 2 3 24D+7M A+L+M k	72 348
				Method 6.7, without twists
	9		11	-1 + 2 4 + 2 5 + 2 9 + 2 11	520	48D+15M A+M A+M k +I k	31 369Mq + I k
	15		9	1 + 2 2

Table 10 :

 10 Methods 6.2, 6.3, 6.4 and 6.7 at 128 bits of security -1+2 6 +2 7 +2 9 +2 10 +2 13 +2 17 +2 22 352 +2 5 +2 6 -2 8 +2 11 -2 14 +2 17 369 66D+4M A+2L+3πq +3M k +I k 28 282Mq + I k 350, 65 16 +2 17 474 34D+2M A+2L+3πq +3M k +I k 64 426Mq + I k 306, 6 10, 9 2 2 +2 3 +2 5 +2 7 +2 13 +2 14 -2 2 +2 7 +2 8 +2 10 +2 14 478 28D+8M A+2L+3πq +3M k +I k 21 778Mq + I k 2+2 3 +2 5 +2 10 400 20D+3M A+2L+3πq +3M k +I k 102 102Mq + I k 356 8, 9 1+2 2 +2 4 +2 6 +2 7 +2 10 +2 7 +2 10 466 20D+3M A+2L+3πq +3M k +I k 28 984Mq + I k 44, 46, 50, 52 no value for u below 2 12 -2-2 7 +2 10 +2 16 +2 22 351 44D+11M A+ extra computation 19160Mq + I k 298, 5 15, 1 1+2 3 -2 10 +2 15 +2 7 +2 10 +2 11 +2 13 375 26D+9M A+ extra computation 145 000Mq + I k 351 11 1+2-2 3 +2 8 +2 10 +2 11 + 2 6 + 2 7 + 2 9 + 2 10 + 2 14 338

	Method 6.6
	Degree 6 twist

Table 11 :

 11 Method 6.6, 128 bits of security, twist of degree 6, 3, 2 and 1 (no twist) k log 32 (q) Miller's in m32 log 64 (q) Miller's in m64

	12	15	1 673 550	8	476 032
	24	10	938 100	5	234 525

Table 12 :

 12 Method 6.6, Comparison of the best candidates + 2 6 + 2 9 -2 12 -2 15 -2 19 + 2 22 + 2 9 + 2 11 + 2 12 + 2 16 + 2 61 + 2 6 + 2 7 + 2 11 + 2 105 + 2 206 + 2 207 1 244 14 928 28 831 43 851 951 11 532 400 6.6 15 1 -2 8 + 2 12 + 2 15 + 2 16 -2 72 + 2 75 897 13 442 13 320 11 202 120 2 997 000 6.6(ZL) 27 -2 5 + 2 8 + 2 12 + 2 16 + 2 21 + 2 22 438, 5 11 841 16 178 2 734 082 792 722 6.6 24 -2 56 -2 43 + 2 9 -2 6 559 13 403 16 368 4 730 352 1 325 808 6.7 24 -2 48 + 2 12 + 2 42 + 1 573 13 746 38 871 12 594 204 3 148 551 KSS 16 2 4 -2 6 + 2 12 + 2 13 + 2 15 + 2 16 + 2 25 + 2 81 + 2 83 834 13 332 24 795 6 347 520 1 586 880 KSS 18 2 -2 5 + 2 9 + 2 11 + 2 14 + 2 82 657 11 809 13 488 5 948 208 1 632 048 DCC 15 2 3 + 2 8 + 2 16 -2 18 + 2 21 + 2 77 + 2 4 + 2 6 + 2 8 -2 11 + 2 17 + 2 22 -2 5 -2 10 + 2 13 + 2 14 + 2 20 + 2 21 1+2 3 -2 6 +2 10 -2 12 +2 15 +2 77 +2 78 +2 79 +2 9 -2 12 +2 15 +2 119 1664 19 957 57 279 > 154.10 6 > 38.10 6 KSS 16 1-2 5 -2 8 -2 11 +2 13 +2 149 +2 150 +2 7 -2 12 -2 17 +2 19 +2 287

	128 bits

Table 15 :

 15 Miller loop: comparison of the best candidates for 128, 192 and 256 bits of security -1-2 4 +2 7 -2 11 +2 15 +2 22 12 228 17 702 + I 29 931 + I 5 058 508 1 466 668 6.4 1+2 4 +2 16 +2 32 9 116 29 250 + I 38 366 + I 5 524 848 1 381 212 6.6 -2 77 +2 50 +2 33 +2 4 +2 11 +2 15 6 401 76 980 + I 83 381 + I 8 338 200 2 084 550 KSS -2 34 +2 27 -2 23 +2 20 -2 11 +1 7 534 18 514 + I 26 048 + I 3 151 929 937 764 DCC 2+2 10 +2 16 +2 19 +2 32 6 836 19 190 + I 26 026 + I 3 747 885 936 972 BN 2 114 +2 101 -2 14 -1 + 2 9 + 2 11 + 2 12 + 2 16 + 2 61 16 735 57 762 + I 72 497 + I 38 351 442 9 587 872 -2 31 -2 13 -2 1 -1 13 250 121 550 + I 134 800 + I 34 508 800 8 627 200 6.6 2+2 2 +2 6 +2 7 +2 11 +2 105 +2 206 +2 207 28 831 15 500 + 6I 44 331 + 6I 67 436 577 16 859 145 1 -2 8 + 2 12 + 2 15 + 2 16 -2 72 + 2 75 13 320 42 707 + I 56 027 + I 47 119 548 11 779 887 -2 56 -2 43 + 2 9 -2 6 16 368 27 985 + 10I 44 353 + 10I 12 820 907 3 205 227 6.6[92] -2 5 + 2 8 + 2 12 + 2 16 + 2 21 + 2 22 16 178 96 626 + I 112 804 + I 22 109 780 5 527 445 KSS 2 4 -2 6 +2 12 +2 13 +2 15 +2 16 +2 25 +2 81 +2 83 24 795 36 000 + I 60 795 + I 15 564 032 3 891 008 2 -2 5 + 2 9 + 2 11 + 2 14 + 2 82 13 488 24 719 + 8I 38 207 + 8I 16 852 815 4 213 204 DCC 2 3 + 2 8 + 2 16 -2 18 + 2 21 + 2 77 13 507 41 942 + I 55 449 + I 49 905 900 12 476 475 1+2 3 -2 6 +2 10 -2 12 +2 15 +2 77 +2 78 +2 79 21 723 75 582 + I 97 305 + I 87 575 400 21 893 850 1+2+2 7 +2 8 -2 10 +2 15 +2 62 25 314 175 550 + I 200 864 + I 193 031 265 48 257 816 6.6 2 10 + 2 11 + 2 30 + 2 150 32 736 79 337 + I 112 073 + I 351 464 064 87 866 016 2 103 -2 101 +2 68 +2 50 37 126 43 213 + 10I 80 339 + 8I 82 276 352 20 569 088 -2 2 -2 4 + 2 10 -2 28 18 493 112 625 + I 132 272 + I 42 856 452 10 714 113 KSS 1-2 5 -2 8 -2 11 +2 13 +2 149 +2 150 38 904 43 128 + I 82 032 + I 144 706 212 36 176 553 DCC 1+2+2 3 +2 5 +2 6 -2 8 +2 15 +2 112 22 435 60 257 + I 82 692 + I 145 870 452 36 467 613

	128 bits

Table 17 :

 17 Overall cost of the optimal Ate pairing

We count

5Me in the evaluation of Le instead of 4Me as presented in[START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] because when we wrote down the equation we do not see how to save one more Me

In a personal communication Tanja Lange asked the first author if 15 is the new 12.

As a direct remark on the exTNFS attack, Pierrick Gaudry told the first author that a good candidate would be a compromise: a degree k which is not coprime to 6 but which has few small divisors, e.g. k = 2p with p ≥ 5 prime.

Operation

Complexity in projective coordinates Doubling step [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF] M 3b + kMq + 3Me + 9Se + M k + S k Mixed addition [START_REF] Zhang | Analysis of optimum pairing products at high security levels[END_REF] kMq + 12Me + 5Se + M k Final line evaluation (5k -4)Mq + Sq + S k/d + M k/d + 2M A