Rémi Clarisse

Sylvain Duquesne

Olivier Sanders

Curves with fast computations in the first pairing group

Introduction

Pairings and cryptography have a long common history. Initially used as a way to shift the discrete logarithm problem from elliptic curves to finite fields [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF], it has first been used for constructive purpose by Joux [START_REF] Joux | A one round protocol for tripartite diffie-hellman[END_REF] in 2000. Following this seminal result, pairings have been massively used in cryptography. This is due in large part to the nice features of this mathematical tool but also to its apparent simplicity. Indeed, the features of pairings can easily be abstracted so as to be used even by non-specialists. Actually, almost all pairing-based cryptographic papers (e.g. [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF][START_REF] Pointcheval | Short randomizable signatures[END_REF][START_REF] Barki | Anonymous attestations made practical[END_REF]) consider so-called "bilinear groups" as some kind of black box given by a set of three groups G 1 , G 2 and G T (usually of prime order ) along with an efficiently-computable non-degenerate bilinear map between them

e : G 1 × G 2 -→ G T .
This way, cryptographers can design their protocols without being bothered by the technicalities of the concrete implementations of pairings. The only subtlety considered in cryptographic papers is the existence of efficiently computable morphisms between G 1 and G 2 , which has led to so called type-i pairings, for i ∈ {1, 2, 3}, according to the classification by Galbraith et al. [START_REF] Galbraith | Pairings for cryptographers[END_REF]. However, type-3 pairings are now preponderant in cryptography because they are the most efficient ones [START_REF] Galbraith | Pairings for cryptographers[END_REF] and because they are compatible with cryptographic assumptions, such as Decisional Diffie-Hellman in both G 1 and G 2 , that do not hold with the other types. Actually, some recent results [START_REF] Chatterjee | Type 2 structure-preserving signature schemes revisited[END_REF][START_REF] Abe | Design in type-i, run in type-iii: Fast and scalable bilinear-type conversion using integer programming[END_REF] cast some doubts on the real interest of type-1 and type-2 pairings for cryptography. For all these reasons, we only consider type-3 pairings in this paper.

In all cases, at some point, it becomes necessary to instantiate these bilinear groups. To date, the only secure instantiations are (to our knowledge) based on elliptic curves as the constructions based on lattices [START_REF] Garg | Candidate multilinear maps from ideal lattices[END_REF][START_REF] Coron | Practical multilinear maps over the integers[END_REF] have been proved insecure [START_REF] Hee Cheon | Cryptographic multilinear maps and their cryptanalysis[END_REF][START_REF] Hee Cheon | Cryptanalysis of the CLT13 multilinear map[END_REF]. More specifically, on one hand, G 1 and G 2 are usually defined as cyclic groups of prime order of some elliptic curve E over a finite field F q . On the other hand, G T is the group of -th roots of unity in F q k , where k is the order of q in Z/ Z, called the embedding degree of q.

It is thus important to understand that, despite being considered as similar objects by the cryptographic abstraction of bilinear groups, the groups G 1 , G 2 and G T are extremely different in practice. The main difficulty when it comes to instantiate these groups is to carefully select the different parameters (essentially , q and k) in order to ensure that security holds in each group while retaining the best efficiency. Here, by "security" we mean the hardness of the Discrete Logarithm Problem (DLP) although cryptographic schemes usually rely on easier problems. Actually, for a long time, the problem of selecting these parameters was thought to be rather easy. It was indeed thought that the hardness of the DLP problem in F q k only depended on the bitlength of this field (namely k log 2 (q)) and not on k and q themselves. Using this assumption, it was quite simple to derive concrete bounds on , q and k to achieve some specific security level λ. For example, in the standard case λ = 128, a simple look at [START_REF] Nigel | Algorithms, key size and protocols report[END_REF]Table 4.6] reveals that we must have log 2 ( ) 256 (and so log 2 (q) 256 because of the Hasse's bound) and k log 2 (q) 3072. In this case, parameters q ∼ ∼ 2 256 and k = 12 are optimal. Moreover the choice of an even k leads to very efficient implementations of pairings and of the arithmetic in F q k . This largely explains the success of the so-called Barretto-Naehrig curves (BN) [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF] (that perfectly match these parameters) which have become de facto the standard pairing curves in the literature.

Unfortunately, two recent papers [START_REF] Kim | Extended tower number field sieve: A new complexity for the medium prime case[END_REF][START_REF] Kim | Extended tower number field sieve with application to finite fields of arbitrary composite extension degree[END_REF] have shown that the assumption regarding F q k was wrong. We will discuss the details later but intuitively these results imply that the bitlength of the elements of F q k is no longer the good metric to estimate security in this group as it now depends on the shape of both integers q and k. We now face a somewhat chaotic situation where a 3000-bit finite field F q k may offer the same security level as a 5000-bit one provided that k and q have some specific properties. And G T is not the only group concerned by these considerations as the parameter q has a direct impact on G 1 and G 2 . Concretely, it is now sometimes necessary to significantly increase the parameter q (that becomes much larger than the advised minimal bound 2 256 ) to remain compatible with some values of k that enables efficient pairing computations. This is illustrated by the BLS12 curves promoted by Barbulescu and Duquesne's [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] for the standard 128-bits level of security. These curves lead to a 450-bit prime q, i.e. 75% higher than old BN curves.

These examples are representative of the current strategy to select pairing parameters [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. The goal is indeed to find a nice compromise between the complexity of the different groups/operations. More specifically, it aims at providing parameters that would not significantly penalize one particular operation. This strategy thus makes the implicit assumption that cryptographic protocols present some kind of symmetry, between the groups G 1 , G 2 and G T , but also between the entities that will perform the operations in these groups. This may be true in some specific scenarios but there are many others were this assumption is false.

As an example, let us consider the case of Enhanced Privacy ID (EPID) scheme introduced by Brickell and Li [START_REF] Brickell | Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities[END_REF] and now massively used to secure Intel SGX enclave [START_REF] Allee | EPID for IoT Identity[END_REF]. EPID is a variant of Direct Anonymous Attestation (DAA) [START_REF] Brickell | Direct anonymous attestation[END_REF] with enhanced revocation capabilities, meaning that it is possible to revoke a secret key sk by simply adding a signature generated using sk to a revocation list. The next signatures will then have to contain a proof that they were issued using a different secret key. This is a nice feature but it implies to perform a high number of exponentiations in G 1 [START_REF] Brickell | Enhanced privacy ID from bilinear pairing for hardware authentication and attestation[END_REF], linear in the number n of revoked signatures, as illustrated in Table 1. Actually, this table shows a clear imbalance between the different groups as soon as the revocation list contains dozens of elements, a threshold that should be quickly reached in most scenarios. In those cases, we note that trying to stick to the minimal bound for q (thus decreasing the complexity of operations in G 1 ), even if it significantly deteriorates the computational cost of a pairing, is a worthwhile goal as there is only one pairing to compute against roughly 6n expo-nentiations to generate or to verify the signature. This is all the more true since this pairing is only computed by the verifier, an entity that is assumed, in the context of DAA, to be much more powerful than the signer (usually a constrained device). To put it differently, we here need a curve that will optimize operations in G 1 even if it is at the cost of a much more expensive pairing.

This scenario illustrates the limits of the global strategy for selecting parameters. The mainstream curves do not seem suitable here and we can hope for dramatic performance improvements by using a tailored curve. And this is not an isolated case as we explain in section 3.

Our contribution. The contribution of our paper is twofold. First, we investigate a different approach for selecting curve parameters. We indeed believe that standard families of curves, like BLS12, do not fit all cryptographic protocols and in particular impose a tradeoff (between the complexities of the different groups and operations) that is irrelevant in many contexts. Realizing that the era of optimality using Barreto-Naehrig curves is over, we choose to focus on the family of cryptographic protocols whose practicality depends on the implementation of the group G 1 . This family is quite large because cryptographers usually try to avoid as much as possible the other groups (G 2 and G T ) as the latter are much less efficient and even incompatible with some constrained devices (see e.g. [START_REF] Barki | Anonymous attestations made practical[END_REF]). We then look for curves with minimal G 1 scalar multiplication complexity, which leads us to the case of prime embedding degree k, a setting that has been overlooked for a long time despite being immune to Kim's and Barbulescu's attacks [START_REF] Kim | Extended tower number field sieve: A new complexity for the medium prime case[END_REF][START_REF] Kim | Extended tower number field sieve with application to finite fields of arbitrary composite extension degree[END_REF] mentioned above. We provide a security assessment, some benchmarks and a complexity evaluation of some curves from this setting that we compare to the most known alternatives. Our results show that the computational complexity of the operations on the first pairing group is 65% higher for the standard curves (with composite embedding degrees) comparing to our proposal (with prime embedding degrees), while yielding elements in G 1 that are 20% larger. Of course, those composite-embedding-degree curves come at the cost of a less expensive pairing but our analysis shows that this overhead is acceptable in the context we consider.

Based on these results we investigate new curves that would match our need. We find a new one that goes one step further in the quest for optimizing the performance of G 1 . We call this new curve, which constitutes our second contribution, BW19-P286 as it was generated using the Brezing-Weng strategy [START_REF] Brezing | Elliptic curves suitable for pairing based cryptography[END_REF], has embedding degree 19 and is defined over a 286-bit field F q . The use of such a small q, which is close to the optimal bound 2 256 , is particularly interesting for constrained devices (more specifically those with 32 -or less-bits of architecture) as it reduces the number of machine-words compared to the state-of-the-art.

In the end, our results show that Kim's and Barbulescu's attacks do not necessarily imply a large increase of the complexity of pairing-based protocols that would in particular rule out the latter for constrained devices. On the contrary, we prove that we can retain the original efficiency for some parties. Of course, this is done to the detriment of the other parties but we argue that there are few use-cases where all entities are equally powerful. We nevertheless do not claim that our curves fit all contexts and in particular we do believe that standard curves still remain relevant, in particular when a large number of pairings is to be computed.

Roadmap.

In section 3 we describe some examples that justify our strategy for selecting curves. In section 4 we outline the strategy to assess the cost of the Discrete Logarithm Problem and the security of our curves and provide two tailored curves in section 5. Finally, we compared an implementation of the proposed curves with other curves in section 6.

Preliminaries

Let q > 3 be a prime number. The field having q elements is noted F q and, for n > 1, the extension field having q n elements is noted F q n . When we compute discrete logarithms in F q n , we mean solving the Discrete Logarithm Problem in the group (F q n \{0}, ×).

Elliptic Curves

An elliptic curve E is the set of points (x, y) satisfying y 2 = x 3 + ax + b, where a, b ∈ F q and 4a 3 + 27b 2 = 0, enlarged with another point ∞, called point at infinity. This equation is called the Short Weierstrass Model of the curve. For n 1, the set of point (x, y)

∈ (F q n ) 2 on E is noted E(F q n ).
The set E(F q n ) can be equipped with a commutative internal law, with ∞ as identity element. We follow the convention of cryptographic literature and denote this group multiplicatively. For an integer coprime to q, we note E(F q n )[ ] the subgroup of E(F q n ) formed by points of order dividing , i.e. all points g such that g = ∞. The group

E(F q n )[ ] is called the -torsion over F q n . When we compute discrete logarithms in E(F q n )[ ],
we mean solving the Discrete Logarithm Problem in the group (E(F

q n )[ ], •), i.e. if h is a power of g, find x such that h = g x . There is a minimal k 1 such that E(F q k )[ ] is isomorphic to (Z/ Z) 2
, this integer is called the embedding degree of q (with respect to ), it is the order of q (mod ). The Frobenius endomorphism is defined as (x, y) → (x q , y q ) ∈ End(E). Its minimal polynomial is X 2 -tX + q, where t is aptly called the trace of the Frobenius, and the number of F q rational points is q -t + 1. The discriminant ∆ of that polynomial is ∆ = t 2 -4q. We can always write

∆ = Df 2 , where D < 0 is square-free. D is called the Complex Multipli- cation discriminant.
When the CM discriminant is small enough, there exists an endomorphism φ easily computable and an integer λ > 0 such that φ(g) = g λ for all g ∈ E(F q )[ ]. The main advantage of using the endomorphism φ is to roughly halve the computational cost of an exponentiation in E(F q )[ ] as evaluating φ is much more efficient than directly raising to the power λ. This is called the GLV method [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphisms[END_REF]. Suppose we want to compute g a for a point g ∈ E(F q )[ ] and a random scalar a (mod ). We proceed as follow: compute a 0 and a 1 such that a = a 0 + a 1 λ (e.g. the Euclidean division of a by λ) and compute g a 0 • φ(g) a 1 . The result is g a :

g a 0 • φ(g) a 1 = g a 0 • g a 1 λ = g a 0 +a 1 λ = g a .
The size of a 0 and a 1 is expected to be half the size of as λ is a root of a degree 2 polynomial. The point φ(P ) can be precomputed (if needed) and g a 0 • φ(g) a 1 can be computed with any multi-exponentiation algorithm.

Bilinear Groups

Pairing-based cryptographic protocols consider a setting defined by three cyclic groups, G 1 , G 2 , and G T , of prime order (with respective identity element 1 G 1 , 1 G 2 and 1 G T ), along with a bilinear map e : G 1 × G 2 → G T with the following properties:

1. for all g ∈ G 1 , g ∈ G 2 and a, b ∈ Z/ Z, e(g a , gb ) = e(g, g) a•b ; 2. for any g = 1 G 1 and g = 1 G 2 , e(g, g) = 1 G T ; 3.
the map e is efficiently computable.

As all these groups are of the same prime order, we know that there exist non-trivial homomorphisms ϕ 1 : G 1 → G 2 and ϕ 2 : G 2 → G 1 . However, the latter may not be efficiently computable, which has a strong impact on cryptographic protocols and more specifically on the underlying computational assumptions. Following Galbraith, Paterson and Smart [START_REF] Galbraith | Pairings for cryptographers[END_REF], this has led cryptographers to distinguish types of pairings: type-1, where both ϕ 1 and ϕ 2 are efficiently computable; type-2, where only ϕ 2 is efficiently computable; and type-3, where no efficiently computable homomorphism exists between G 1 and G 2 , in either direction. All these types can be instantiated with elliptic curves but type-3 pairings are preferred in practice both for their efficiency and their ability to support some useful cryptographic assumptions, e.g. decisional Diffie-Hellman in groups G 1 and G 2 .

We also note that it is possible to consider bilinear groups of composite order. However, prime order bilinear groups are much more efficient [START_REF] Guillevic | Comparing the pairing efficiency over composite-order and prime-order elliptic curves[END_REF] and can actually emulate most features of their composite-order counterparts [START_REF] Mandell | Converting pairing-based cryptosystems from compositeorder groups to prime-order groups[END_REF].

Usually, when bilinear groups are instantiated over an elliptic curve,

q -t+1 is a multiple of but not of 2 , G 1 = E(F q )[ ], G 2 ⊂ E(F q k )[ ]\G 1 and G T ⊂ F q k .
And that will be our case here.

Schemes with numerous computations in G 1

Before providing details on the way we select elliptic curve parameters, we elaborate on the motivation of our work, namely the benefits of selecting such parameters based on the characteristics of the cryptographic protocols. We are more specifically interested in the family of cryptographic protocols whose complexity essentially depends on the efficiency of G 1 . This family may include protocols requiring to perform many exponentiations in G 1 , as is the case with the EPID scheme we discuss in the introduction, but also schemes where the most constrained entity only has to compute operations in G 1 , as in Direct Anonymous Attestation. These two primitives are today massively used in industrial products [START_REF] Tcg | [END_REF][START_REF] Allee | EPID for IoT Identity[END_REF] and are thus meaningful examples of this family of cryptographic protocols. To illustrate that the latter is not restricted to authentication algorithms we will also consider the case of two cryptographic accumulators that would benefit from the tailored curves we propose in our paper.

Table 1 highlights the specific need of two anonymous authentication schemes [START_REF] Barki | Anonymous attestations made practical[END_REF][START_REF] Brickell | Enhanced privacy ID from bilinear pairing for hardware authentication and attestation[END_REF] that are, to our knowledge, the most efficient of their kind. For [START_REF] Brickell | Enhanced privacy ID from bilinear pairing for hardware authentication and attestation[END_REF], we use the proof of non-revocation described by the same authors in [START_REF] Brickell | Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities[END_REF]. We note that most alternatives and variants (e.g. [START_REF] Pointcheval | Short randomizable signatures[END_REF] for group signature) present similar features so our conclusions also apply to them. Table 1 shows that the size of the signature only depends on the one of G 1 elements (and on ) and that the signer only has to perform operations in G 1 . There are few pairings and operations in G 2 to compute and only on the verifier side, which is usually considered as more powerful than the signer in those contexts. Cryptographic protocols with such features are thus a good incentive for designing curves with efficient computations/elements in G 1 . In Table 2, we consider two pairing-based accumulator schemes [START_REF] Camenisch | An accumulator based on bilinear maps and efficient revocation for anonymous credentials[END_REF][START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]. We recall that the point of an accumulator system is to project a large number of elements into a single short value, called the accumulator. Additionally, for each of these elements, it is possible to generate a short evidence, called witness, that the element has indeed been accumulated. In practice, there are essentially two kinds of entities, the one that needs to prove that an element has been accumulated (by computing the corresponding witness) and the one that checks this proof. We will then divide the public parameters of such systems between the ones (pk) necessary for the proof and the ones (vk) necessary for the verification. Here again, Table 2 shows a clear asymmetry between the prover and the verifier. The former is only impacted by the performance of G 1 and so would clearly benefit from a curve tailored to optimize this group. This is all the more true that in the applications considered in [START_REF] Camenisch | An accumulator based on bilinear maps and efficient revocation for anonymous credentials[END_REF] and [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF], the prover is usually a user's device whereas the verifier is some service provider that can reasonably be considered as more powerful.

Attacks solving the DLP

Most cryptographic schemes using bilinear groups rely on problems that are easier than the Discrete Logarithm Problem (DLP). Unfortunately, the concrete hardness of these problems is not known so the common approach to generate bilinear groups is to select parameters that yield three groups G 1 , G 2 and G T where the DLP is believed to be hard. The latter problem has indeed been extensively studied over the last 40 years and several algorithms were proposed to solve it. The DLP on elliptic curves is called ECDLP (EC stands for Elliptic Curve) and is considered the hardest discrete logarithm problem to solve as only generic algorithms [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] are known and used [START_REF] Pollard | Monte carlo methods for index computation[END_REF][START_REF] Shanks | Class number, a theory of factorization, and genera[END_REF]. Moreover, the Pohlig-Hellman method [START_REF] Pohlig | An improved algorithm for computing logarithms over gf(p) and its cryptographic significance[END_REF] reduces an instance of the DLP in a cyclic group of composite order n to several easier instances of the DLP in cyclic groups of order strictly dividing n. Hence, for efficiency and security reasons, the groups G 1 and G 2 must be of prime order, i.e. is a prime number. And since the best variant of Pollard-rho [START_REF] Daniel | On the correct use of the negation map in the pollard rho method[END_REF] compute a discrete logarithm in at most π /4 ≈ 0.886 √ steps, of 2λ bits is enough for a security of λ bits.

A well-known value, called ρ-value, is used to describe the efficiency of the representation of elements of G 1 . It is computed as ρ = log(q)/ log( ) or as ρ = deg(q)/ deg( ) when q and are polynomial in Q[X]. When ρ = 1, the curve is of prime order , this is the best case for the arithmetic efficiency on the curve (and so for G 1 ).

While determining the size of G 1 and G 2 over the elliptic curve is pretty straightforward, doing the same for G T over the finite field F q k is much harder! Indeed, discrete logarithms in F q k are computed in subexponential time (and sometimes even in quasi-polynomial time) by Number Field Sieve (NFS) algorithms. In the general case, it is difficult to evaluate the complexity of the NFS algorithm, and of its variants (see [START_REF] Guillevic | Discrete Logarithms. In Guide to pairingbased cryptography[END_REF] for more details). To give an idea of the time-complexity of NFS algorithms, we need to introduce the L-notation, which is defined by:

L q k [α, c] = exp (c + o(1))(ln q k ) α (ln ln q k ) 1-α with α ∈ [0, 1] and c > 0. Intuitively, if α = 1 then L q k [α, c] is exponential in log 2 (q k )
whereas it is polynomial in log 2 (q k ) if α = 0. NFS-type algorithms (of our concern) all have time-complexity L q k [1/3, c] for c ranging from 3 32/9 to 3 96/9. The constant c plays an important role in the concrete (i.e. not asymptotic) world, as between 20 and 30 bits of security can be lost for the same size of F q k depending on the choices of q and k [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. Two criteria determine which NFS-variant to use: whether q is special, i.e. if q is computed as the image of a polynomial of degree at least 3, and whether k is composite. Until recently, only curves with special q and composite k were consider as they offer the best performance for pairing computations. Barbulescu and Duquesne updated key size estimations in [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. For a 128-bit security level, they urge to use a finite field of size at least k log 2 (q) = 2930 (respectively 3618, 5004) if NFS (respectively exTNFS, SexTNFS) is the best algorithm for computing discrete logarithms in F q k (the common practice was k log 2 (q) = 3072 [START_REF] Nigel | Algorithms, key size and protocols report[END_REF]). To access curves' security, we will use the algorithm provided by Guillevic at https://gitlab.inria.fr/tnfs-alpha/alpha.

The only known methods for constructing curves with ρ close to 1 give the characteristic of the finite field as a polynomial (thus q is special), like Brezing-Weng constructions [START_REF] Brezing | Elliptic curves suitable for pairing based cryptography[END_REF]; other general methods having ρ close to 2, like Cocks-Pinch constructions (see [START_REF] Guillevic | Cocks-pinch curves of embedding degrees five to eight and optimal ate pairing computation[END_REF]). In this context, we will consider the recent bounds [3072, 5376] on the finite field size provided by Guillevic [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF] to achieve 128 bits of security.

If we have log 2 ( ) = 256 to satisfy 128 bits of security on the curve side, we then know that log 2 (q) = 256ρ and the finite field F q k has size 256ρk. Guillevic's bounds then give us: 3072 256ρk 5376, which, together with the inequalities 1 ρ 2, allows us to derive the set of potential values for k : 6 k 21. Concretely, this means that there is no point in considering values k < 6 as they are incompatible with the targeted 128-bit security level (for the range of ρ-values we consider) and selecting a value k > 21 would be an overkill.

So far, we have just managed to derive some bounds on the different parameters of the curves. Unfortunately, as we explain above, there is no simple choice within these bounds as security and efficiency of the resulting bilinear groups may significantly differ from one set of parameters to another. In particular, there is no linearity in the security evaluation as, for instance, the security of F q k is significantly higher in the "prime" cases k ∈ {11, 13} than in the case k = 12. This means that we can select smaller q values (which improves performance of G 1 ) in the former case. Unfortunately, a similar issue arises regarding efficiency of F q k , but with opposite conclusions, as non-prime k (especially even ones) yield more efficient pairings and group operations. It is thus necessary to make a choice between these different parameters, in particular in the case of cryptographic protocols with unbalanced complexities, such as the ones we consider in section 3. As the latter would benefit of fast G 1 computations and short representations of its elements, we dedicate the next section to the selection of parameters that will optimize the performance of this group.

Curves optimizing operation in G 1

The first group of the pairing G 1 is defined as E(F q )[ ]. We have an incentive to reduce the size of q as computations in G 1 would be faster. To ensure security on the elliptic curve, we need log 2 (q) log 2 ( ) 256. Thus q is at least a 5-machine-word on a 64-bit computer. Indeed, q has more than 257 bits, because a 256-bit field would imply ρ = 1 and, the biggest known k ∈ [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF][START_REF] Galbraith | Pairings for cryptographers[END_REF] for that ρ-value is 12, which does not ensure a 128-bit security in G T [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF].

We would like to be able to use the GLV method [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphisms[END_REF], that is, our curves should have a small Complex Multiplication discriminant. When curves are chosen either in the form y 2 = x 3 + ax with a primitive fourth root of unity in F q and CM discriminant -1, or in the form y 2 = x 3 +b with a primitive third root of unity in F q and CM discriminant -3, the GLVendomorphism is easy to write down and relatively cheap to compute.

As explained above, we cannot hope for better than 5 machine-words for q on 64-bit architecture. A 5-machine-word q means that 1 < ρ 1.25. Searching in the Taxonomy by Freeman, Scott and Teske [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF], the curve we are looking for has embedding degree k ∈ {8, 11, 13, 16, 17, 19}. The embedding degree 8 does not provide a secure finite field F q k , as it is of at most 8×1.25×256 = 2560 bits, and so is discarded. The embedding degree 16 corresponds to the well-known KSS family of pairing-friendly curves [START_REF] Ezekiel | Constructing brezingweng pairing-friendly elliptic curves using elements in the cyclotomic field[END_REF]. Barbulescu and Duquesne [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] state that q must be at least a 330-bit prime, i.e. a 6-machine-word prime, and they give such primes.

Thus we focus our search for curves from [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] having embedding degree k ∈ {11, 13, 17, 19}. All those curves correspond to Freeman, Scott and Teske Construction 6.6, which is a generalization of the Brezing and Weng construction [START_REF] Brezing | Elliptic curves suitable for pairing based cryptography[END_REF]. It defines the prime q, the Frobenius trace t and the order as polynomials in Q[X], where (X) is a cyclotomic polynomial dividing both q(X) -t(X) + 1 and q(X) k -1.

Curves over a five-64-bit-machine-word prime field

Construction 6.6 from [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] is different given the residue k (mod 6). Since we have 13 ≡ 19 ≡ 1 (mod 6) and 11 ≡ 17 ≡ 5 (mod 6), we only give the relevant cases of Construction 6.6.

In the case k ≡ 1 (mod 6), the prime q(X), the Frobenius trace t(X) and the order (X) are given as:

q(X) = 1 3 (X + 1) 2 (X 2k -X k + 1) -X 2k+1 , t(X) = -X k+1 + X + 1 and (X) = Φ 6k (X),
and in the case k ≡ 5 (mod 6), they are given as:

q(X) = 1 3 (X 2 -X + 1)(X 2k -X k + 1) + X k+1 , t(X) = X k+1 + 1 and (X) = Φ 6k (X),
Plugging in the different values of k gives Table 3. Note that to find a curve, we need to find a x 0 ∈ Z such that (x 0 ) and q(x 0 ) are prime integers. We choose x 0 satisfying x 0 ≡ 2 (mod 3) so q(x 0 ) is an integer. The last column of Table 3 is the search range of log 2 (|x 0 |) in [256/ deg( ), 320/ deg(q)[ so that q(x 0 ) is a 5-machine-word integer and (x 0 ) is at least a 256-bit integer (for readability, the interval is given with rounded integer values). After a computer search, we have found no solution for k ∈ {11, 17}. For k = 13, we found x 0 = -2224 and for k = 19, we found x 0 = -145. Inferring the naming convention used in relic-toolkit [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF], the first curve is named BW13-P310 and the second one BW19-P286. As Construction 6.6 curves have CM discriminant -3, both curves are of the form y 2 = x 3 + b.

Curve BW13-P310 Setting k = 13 into Construction 6.6 [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] gives:

q(X) = 1 3 (X + 1) 2 (X 26 -X 13 + 1) -X 27 , t(X) = -X 14 + X + 1 and (X) = Φ 78 (X).
Plugging in x 0 = -2224 yields a q(x 0 ) of 310 bits and a (x 0 ) of 267 bits, thus ρ = 1.161. The corresponding F q 13 is a 4027-bit finite field.

To look for a b, we increase the value of |b|, check that the number of points on the curve y 2 = x 3 + b is equal to q(x 0 ) -t(x 0 ) + 1. We found b = -17. So we defined the curve BW13-P310 by the equation y 2 = x 3 -17.

We also point out that the exact same curve has been given by Aurore Guillevic in [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF]. She made a thorough security analysis and estimated that the cost of the DLP in the finite field F q 13 is 140 bits. Hence, the curve BW13-P310 has a security of at least 128 bits.

Curve BW19-P286 Setting k = 19 into Construction 6.6 [START_REF] Freeman | A taxonomy of pairing-friendly elliptic curves[END_REF] gives:

q(X) = 1 3 (X + 1) 2 (X 38 -X 19 + 1) -X 39 , t(X) = -X 20 + X + 1 and (X) = Φ 114 (X).
Plugging in x 0 = -145 yields a q(x 0 ) of 286 bits and a (x 0 ) of 259 bits, thus ρ = 1.105. The corresponding F q 19 is a 5427-bit finite field.

To look for a b, we do the same as before. The smallest |b| is b = 31. So we defined the curve BW19-P286 by the equation y 2 = x 3 + 31. To our knowledge, this curve has never been proposed in the literature.

To evaluate the cost of the DLP in F q 19 , we follow the work of Guillevic [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF], the same she did for the previous curve BW13-P310. To find the curve BW19-P286 using Guillevic's Algorithm 3.1 [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF], we plugged in the parameters k = 19, D = 3, e 0 = 13 and use the substitution X → -X.

Before running the estimating program on our parameters, we applied Variant 4 [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF] to the polynomial q(-X), yielding a polynomial Q(X) such that Q(u 3 ) = 3q(-u), for u = -x 0 = 145 and

Q(X) = (u + 1)X 13 + u 2 X 12 + X 7 + u(1 -2u)X 6 + u 2 -2u + 1.
Then we obtain that the cost of the DLP in F q 19 is 160 bits, thus providing BW19-P286 with a security of at least 128 bits.

GLV endomorphism on BW13-P310 and BW19-P286

As stated in the preliminaries, the discriminant of the minimal polynomial of the Frobenius endomorphism can be written as Df 2 = t 2 -4q, where D < 0 is the CM discriminant and t is the trace of the Frobenius. The endomorphism φ : (x, y) → (ωx, y), with ω a primitive third root of unity, corresponds to an exponentiation (ωx, y) = (x, y) λ in G 1 = E(F q )[ ] for q and distinct primes.

For both our curves, the CM discriminant is D = -3, thus we have 4q = t 2 + 3f 2 . Since ω ∈ F q is a primitive third root of unity, ω satisfies ω 2 + ω + 1. We can take ω = ( √ -3 -1)/2, where √ -3 ≡ t/f (mod q). Thus ω ≡ (t -f )/(2f ) (mod q).

Similarly, since φ 3 = id E in End(E), we know that λ ∈ Z/ Z satisfies the equation λ 2 + λ + 1, i.e. it can also be taken as ( √ -3 -1)/2. However, here, √ -3 ≡ (t -2)/f (mod ). Indeed, divides the number of points on the curve, so q ≡ t -1 (mod ) and 4(t -1) ≡ t 2 + 3f 2 (mod ). Thus λ ≡ (t -f -2)/(2f ) (mod ).

Note that in practice, adjustments may be needed as (ωx, y) = (x, y) ±λ or (ω 2 x, y) = (x, y) ±λ .

In the case of BW13-P310, λ has bit-length 146, whereas it is only 137 in the case of BW19-P286.

Comments on BW13-P310 and BW19-286. We provide in the next section several benchmarks to compare our new curve with BW13-P310 but also with other curves from popular families. However, we can already note that BW13-P310 and BW19-P286 clearly match our strategy of optimizing the group G 1 to the detriment of the other groups. In this respect, our new curve BW19-P286 goes one step further than BW13-P310 by reducing the size of q by roughly 25 bits. This difference is significantly amplified in the context of constrained devices as it results in less machine words. Indeed, even for 32-bit architecture, BW19-P286 yields a prime q with one less machine-word than BW13-P310, which clearly impacts performance, as illustrated below.

Implementation and comparison

We implemented the G 1 arithmetic of both curves using relic-toolkit [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF], and made some comparison with other curves already implemented in relic-toolkit and aiming the 128-bit security.

The curves selected from the framework are BN-P446, a Barreto-Naehrig curve [START_REF] Paulo | Pairing-friendly elliptic curves of prime order[END_REF] over a 446-bit prime field; K16-P339, a Kachisa-Schaefer-Scott curve of embedding degree 16 over a 339-bit field; B12-P446, a Barreto-Lynn-Scott curve of embedding degree 12 over a 446-bit field; and CP8-P544, a Cocks-Pinch curve [START_REF] Guillevic | Cocks-pinch curves of embedding degrees five to eight and optimal ate pairing computation[END_REF] of embedding degree 8 over a 544 prime field. We chose the last curve as it is coming from recent works [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] that promote them for the 128-bit security level. We included a BN, BLS and KSS curves in our table as those families of curves are well-known and were updated by Barbulescu and Duquesne [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF]. Also note that, setting aside our curves, only the curve K16-P339 was implemented by us in the framework.

All curves enjoy a speedup using GLV endomorphisms.

Operation in G 1

In Table 4 we compare the cost of one exponentiation in the group G 1 by compiling the relic-toolkit either for x64 architecture or for x86 architecture with a word size of 32 bits. Times are given in microseconds (the number of iterations was 10 6 ) and computations were done on a laptop equipped with a Intel Core i7-6600u CPU at 2.60 GHz. This table shows a clear relation, almost quadratic, between complexity and the number of words necessary to represent q. It also highlights the downside of Barreto-Naehrig curves that generate elliptic curves of prime order ∼ q. Indeed, what was considered as an advantage (prime order curves make group membership tests trivial) turns out to be a strong limitation as it forces to grow unnecessarily. This negatively impacts both exponentiation (as the exponents are roughly 75% greater than those of the other curves) and the size of scalars.

In all cases, this table shows that our curve BW19-P286 offers the best performance for G 1 , in particular for architecture smaller than 64 bits. It at least halves the complexity of exponentiations in G 1 compared to mainstream curves such as B12-P446 and also significantly decreases the size of group elements, which clearly fits the needs of some cryptographic protocols such as the ones we presented in section 3.

Operation in G 2

The operations in G 2 are unfortunately the ones that are the most impacted by our choice of prime embedding degree. Indeed, BW13-P310 and BW19-P286 have G 2 defined over F q 13 and F q 19 respectively, whereas B12-P446, BN-P446 and CP8-P544 all have G 2 defined over F q 2 thanks to quartic or sextic twists, and K16-P339 has G 2 defined over F q 4 thanks to a quartic twist. As all curves are usually expressed with the same model using the same system of coordinates, only the cost of the multiplication in the extension impacts the cost of the operations in G 2 . Using a Karatsuba-like implementation, the multiplication in F q k is roughly k log 3 2 times as expensive as the one in F q .

Pairing computation

The computation of the pairing is usually split between two parts: the evaluation of the Miller loop and the final exponentiation. Here we give computation for a multiple of the Optimal Ate Pairing [START_REF] Vercauteren | Optimal pairings[END_REF], since we picked the final exponentiation from Kim, Kim and Cheon [START_REF] Kim | On the final exponentiation in tate pairing computations[END_REF]. The values in Table 5 are from [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF][START_REF] Guillevic | Cocks-pinch curves of embedding degrees five to eight and optimal ate pairing computation[END_REF], completed with the ones from below.

Let m k , s k , i k , f k respectively denote a multiplication, a square, an inversion, a Frobenius map (i.e. the q-th power map) over F q k . We drop the index when the operation is over F q (i.e. m = m 1 ). As k ∈ {13, 19} is prime, we estimate m k = s k = k log 2 3 m with a Karatsuba-like implementation and f k = (k -1)m as in [START_REF] Guillevic | Cocks-pinch curves of embedding degrees five to eight and optimal ate pairing computation[END_REF].

Miller loop Using Equation ( 7) from [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF], Guillevic gives a lower bound on the cost of the Miller loop. For both BW13-P310 and BW19-P286, the optimal ate Miller loop has length u 2 +up+p 2 , as it is a multiple of [START_REF] Vercauteren | Optimal pairings[END_REF].

For BW13-P310, the length of the Miller loop is u 2 + up + p 2 , where u = 2224 is a 12-bit integer with Hamming weight 4 and p is a 310-bit prime. From her Equation (7) [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF], Guillevic obtains 949m + 313m 13 + 177s 13 + 5f 13 + 2i 13 . Substituting m 13 = s 13 = 59m and f 13 = 12m in that formula yields a lower bound on the cost of the optimal ate Miller loop, i.e. 29919m + 2i 13 .

For BW19-P286, the length of the Miller loop is u 2 + up + p 2 , where u = 145 is a 8-bit integer with Hamming weight 3 and p is a 286-bit prime. From the same equation as Guillevic [START_REF] Guillevic | A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level[END_REF], we obtain 912m + 212m Final exponentiation As usual, the final exponentiation (q k -1)/ of the Optimal Ate Pairing is split between an easy part (q k -1)/Φ k (q) and a hard part Φ k (q)/ . Since k ∈ {13, 19} is prime, the easy part is simply q -1, costing f k + i k . For the hard part, Kim, Kim and Cheon [START_REF] Kim | On the final exponentiation in tate pairing computations[END_REF] noticed that Φ k (q)/ can be decompose in base q to make use of the Frobenius and the coefficients can be reduced by looking for a short vector in a specifically designed lattice. However, instead of raising to the power Φ k (q)/ , this method [START_REF] Kim | On the final exponentiation in tate pairing computations[END_REF] raises to a multiple power mΦ k (q)/ .

More precisely, they write

m Φ k (q) = k-2 i=0 a i q i
and find the k -1 coefficients (a i ) 0 i k-2 as the shortest vector in the dim-(k -1) lattice spanned by the lines of the following matrix:

        Φ k (q) 0 0 • • • 0 -q 1 0 • • • 0 -q 2 0 1 • • • 0 . . . . . . -q k-2 0 • • • 0 1        
.

Then, they compute the Frobenius of the element they want to exponent, up to the (k -1)-th q-power, costing (k -2)f k .

If the exponents a i 's were longer, we would have needed (2 k-1 -k)m k to compute all combinations of (k -1) Frobenius powers. However, we do not use all of these combinations, only roughly O(log 2 q) of them. Finally the length of the multi-exponent is max i { log 2 a i }, resulting in an average final exponentiation costing (k -1)f k + (O(log 2 q) + max i { log 2 a i })m k + max i { log 2 a i }s k + i k , omitting some inversion due to the sign of some a i 's.

For BW13-P310, the value of max i { log 2 a i } is 287 and 8 of the 12 a i 's are negative. Only 191 different combinations of Frobenius powers are used and it costs 341m 13 to compute them. Also, there are 5 positions (in the binary expansion) where all the a i 's have their bit set to 0, resulting in no multiplication at those positions for the multi-exponentiation, that thus requires 282m 13 + 287s 13 . Combining everything yields an final exponentiation cost of 12f 13 + 623m 13 + 287s 13 + 9i 13 , i.e. 53 834m + 9i 13 .

For BW19-P286, the value of max i { log 2 a i } is 271 and 12 of the 18 a i 's are negative. Only 222 different combinations of Frobenius powers are used and it costs 1028m 19 to compute them. The multi-exponentiation From Table 5, the cost of the pairing for BW19-P286 is roughly 12 times higher than the one for B12-P446. However, doing the benchmark on both finite field gives a multiplication twice faster on the 286-bit finite field (90 ns) than the 446-bit one (190 ns). Hence, we estimate that the pairing over BW19-P286 is 6 times slower than the pairing over B12-P446.

Conclusion

In this paper, we have given an incentive to change the way pairingfriendly elliptic curve are constructed by shifting the optimization away from the balance between all operations (group exponentiation and pairing) towards only some operations (that might be used by constrained entities involved in cryptographic protocols).

Thus, we focused on elliptic curves with a fast exponentiation in the first pairing group upon noticing that the instantiation of some cryptographic protocols, e.g. Group Signature-like schemes, would benefit from such curves.

Along the way, we have described a new curve that is particularly relevant for cryptographic protocols extensively using exponentiation in the first pairing group. That curve is twice faster in that group and its pairing computation is reasonably six times slower compared to a BLS curve over a 446-bit field.

We leave to future work the investigation of other protocol-curve dependencies.

Table 1 .

 1 Complexity of some anonymous authentication schemes. ei refers to an exponentiation in Gi and P to a pairing computation, n is the number of revoked signatures.

	Operation Counts

Table 2 .

 2 Complexity of some accumulators schemes. The latter are called set commitment schemes in[START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]. Here m1 refers to a group operation in G1, n is a bound on the number of values to be accumulated and j is the number of values currently accumulated. The other notations are those from the previous table.

	Public Parameters Operation Counts
	Ref. pk	vk	Sign	Verify
	[13] 2nG1	nG2	jm1	2P
	[20] nG1	nG2	(j -1)e1 1e2 + 2P

Table 3 .

 3 Parameters and search range for curves with k ∈ {11,13, 17, 19}

	k deg(q) deg( ) ρ log 2 (|x0|)
	11 24	20 1.20 [12, 14[
	13 28	24 1.167 [10, 12[
	17 36	32 1.125 [8, 9[
	19 40	36 1.111 [7, 8[

Table 4 .

 4 Benchmark for one exponentiation in G1.

		Curve BW19-P286 BW13-P310 K16-P339	B12-P446	BN-P446	CP8-P544
	prime q bit size	286	310(+8%) 339(+19%) 446(+56%) 446(+56%) 544(+90%)
	64-bit	words	5	5	6	7	7	9
		time (µs)	293	304(+4%) 482(+65%) 611(+109%) 855(+192%) 1058(+261%)
	32-bit	words	9	10	11	14	14	17
		time (µs)	1010	1220(+21%) 1664(+65%) 2510(+149%) 3600(+256%) 4180(+314%)

  19 + 115s 19 + 5f 19 + 2i 19 . Substituting m 19 = s 19 = 107m and f 19 = 18m in that formula yields a lower bound on the cost of the optimal ate Miller loop, i.e. 35991m + 2i 19 .

Table 5 .

 5 Operation count for Miller loop, final Exponentiation and Total pairing 19 + s 19 ). Combining everything yields an final exponentiation cost of 18f 19 + 1299m 19 + 271s 19 + 13i 19 , i.e. 160 824m + 13i 19 .

	BW19-P286	BW13-P310	K16-P339 B12-P446 BN-P446 CP8-P544
	M. 35991m + 2i19	29919m + 2i13	7691m	7805m 11620m 4502m
	E. 160824m + 13i19	53834m + 9i13	18235m 7723m	5349m	7056m
	T. 196815m + 15i19 83753m + 11i13 25926m 15528m 16969m 11558m
	requires 271(m

Acknowledgements

The authors are grateful for the support of the ANR through projects ANR-19-CE39-0011-04 PRESTO and ANR-18-CE-39-0019-02 MobiS5.


Julien Fontchastagner

Thierry Lubin

Frédéric Messine

Smail Mezani

Smaïl Mezani

Efficient Design Using Successive Analytical Subproblems Method: Application to Axial Magnetic Couplings

Keywords: Design, Axial magnetic coupling, Global optimization, Successive analytical subproblems

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

It is usual to see design problems as optimization ones, generally defined as MINLP (mixed integer non-linear programs) [START_REF] Fontchastagner | Some Co-axial Magnetic Couplings Designed Using an Analytical Model and an Exact Global Optimization Code[END_REF]. However some criteria or constraints are often defined thanks to a numerical model and the resulting problems become hard to solve. The authors present in this paper a simple but efficient technique to solve this kind of design problems when an analytical approximation exists.

II. AXIAL MAGNETIC COUPLINGS

A basic structure of axial magnetic coupling is considered as shown in Fig. 1.(a). In [START_REF] Lubin | Simple Analytical Expressions for the Force and Torque of Axial Magnetic Couplings[END_REF], the authors develop, test and use a complete analytical explicit model of such a structure. So it is possible to compute the electromagnetic torque very quickly. If this model is compared to experimental values, it appears that it gives the right tendencies but overestimates significantly interesting quantities such as the torque as it appears on Fig. 1.(b). A 3D FEM model is much closer to the measurements. This model is based on a scalar potential formulation solved using a general commercial finite element solver (FlexPDE), and encapsulated in a dedicated black-box.

III. SUCCESSIVE ANALYTICAL SUBPROBLEMS METHOD

The idea is to use both advantages of the two modeling tools: swiftness of the analytical and accuracy of the numerical one. A corrected analytical model is defined by multiplying the initial model by a corrective factor β k . The associated optimization (S k ) is solved using a global deterministic optimization code (IBBA) [START_REF] Fontchastagner | Some Co-axial Magnetic Couplings Designed Using an Analytical Model and an Exact Global Optimization Code[END_REF]. A comparison with 3D FEM for the found minimum is performed, the corrective factor is updated and the procedure iterated until the difference between the two models is less than a fixed tolerance ε tol .

In order to show the interest of the developed technique, a small numerical example is performed. The considered problem deals with the minimization of the volume of the magnets (V m ) with a maximum torque (Γ) greater than 100 N•m. It has 5 variables (with 1 integer: the pole pair number) and 2 additional geometric constraints. The overall procedure corresponding to SAS is given by Algorithm 1.

Algorithm 1 SAS: Successive Analytical Subproblems ε = ∞; β 1 = 1; k = 0 while (ε > ε tol ) do k = k + 1 Solve exactly: (S k )    min x V m (x) s.t. β k • Γ ana (x) ≥ Γ fixed g i (x) ≤ 0, i ∈ [[1, n g ]] ∼ x k = argmin(S k ); Γ num = Γ 3D ( ∼ x k ) β k+1 = Γ num Γ ana ( ∼ x k ) ; ε = β k+1 • Γ ana ( ∼ x k ) -Γ num Γ num end while ∼ x = ∼ x k {Found solution}
The proposed method is compared with a classical genetic algorithm (GA) provided by the MATLAB Global Optimization Toolbox with 20 individuals evolving during 30 generations. Results are given in Table I which clearly show the efficiency of the proposed methodology.

Fig. 1 .

 1 Fig. 1. (a): Geometry of the studied structure (only 2 poles); and (b): Models vs. Experimental Values Comparison

TABLE I PRELIMINARY

 I RESULTS : SAS VS. GA (min Vm, Γ fixed = 100 N•M).

		SAS	GA *
	Vm (cm 3 )	44.76	58.89
	Γ 3D (N•m)	100.11	100.04
	n o of 3D FEM Comput.	3	623
	CPU Time	< 3 min 212 min

* best run over 10