Scaling security in pairing-based protocols

Michael Scott

School of Computing Dublin City University Ballymun, Dublin 9, Ireland. mike@computing.dcu.ie

Abstract. In number theoretic cryptography there is always the problem of scaling-up security to a higher level. This usually means increasing the size of the modulus, from, say 1024 bits to 2048 bits. In pairing-based cryptography however another option is available, keeping the modulus constant and increasing instead the embedding degree. This has a big potential advantage in smart-card and embedded applications – security can be scaled up while continuing to use the same sized calculations. For example a cryptographic co-processor which does 512-bit modular multiplications can be directly re-used in the higher security setting. Here we investigate the scaling-up issue in the context of prime characteristic non-supersingular elliptic curves. We also confirm that under certain circumstances at higher levels of security a slightly modified Weil pairing may become more efficient than the Tate pairing.

Keywords: Cryptographic key sizes, pairing-based cryptosystems.

1 Introduction

In the majority of number-theoretic cryptographic protocols, both over the finite field and on elliptic and higher genus curves, the problem of increased security implies only one obvious solution – increase the size of the modulus, traditionally by doubling its size. Interestingly in the case of the RSA scheme, based as it is not on the difficulty of a discrete logarithm problem, but rather on the problem of integer factorisation, there is an alternative solution. Multi-prime RSA has been frequently suggested by many people as an alternative to simply doubling the length of the prime factors of the public key. If n = pq, and p and q are originally 512 bits, then an increased security implementation might make p and q both 1024-bits. The multi-prime alternative is to use n = pqrs where p, q, r and s all remain 512-bit primes. This does not apparently introduce any serious new weaknesses [16], and represents a completely viable solution, with some significant performance advantages. And yet multi-prime RSA is not widely used, and has only relatively recently appeared in standardisation documents [19]. The reason for this may be that the optimal way of scaling RSA security was never properly addressed early on by the research community. And it is very simple to just double the bit length of p and q – for one thing it requires no further security analysis.

For a particular discrete logarithm based scheme, there is no such choice. For increased security, one must increase the size of the modulus. There is of course the possibility of switching to a different scheme for which the same-sized modulus provides more security – for example one can switch from a standard finite field setting to a scheme such as LUC [32], or XTR [20]. But as a way of scaling security this seems very clumsy. And there is something else to be considered – when attacking a discrete logarithm based system an attacker can choose to exploit the small size of the group (using the Pollard Lambda algorithm), or the small size of the field (using index calculus methods, if they apply, otherwise the Pollard Rho algorithm) [25]. For balanced security in a finite field one might choose a modulus of 1024-bits (to resist index calculus attacks) and a group size of 160-bits (to resist Pollard Lambda attacks).

The issue of how to scale up security in pairing-based cryptosystems has also been addressed by Koblitz and Menezes [18] and Granger, Page and Smart [15]. As will be seen our experimental evidence largely supports their conclusions.

In pairing based cryptography there are, as for RSA, two distinct strategies to obtain increased levels of security; double the size of the prime modulus, or double the embedding degree. In both cases the group size must also be increased as appropriate.

However field size is a particularly significant parameter for smart-card and embedded implementations that use co-processor support, as it is field size that determines the hardware requirement.

Here we analyse the approach of simply doubling the embedding degree. This has some immediate implications. Firstly supersinglar elliptic curves have a maximum embedding degree of 6. While it is true that higher embedding degrees can be obtained on hyper-elliptic curves [26], as a method of scaling security switching to a different characteristic or to a higher genus curve again seems very clumsy. Therefore we consider here only non-supersingular curves, while acknowledging that small characteristic supersingular elliptic and hyperelliptic curves can be a very efficient vehicle for pairing-based cryptography. See for example [3] for some recent results, in particular the discovery of the new η^T pairing.

The aim is to provide a simple mechanism for scaling security which requires minimal changes to an existing implementation, in terms of algorithm, software and hardware.

In most protocols it is the time taken to calculate the pairing that is most significant. However the time taken for field exponentiation and elliptic curve point multiplication must also be taken into account when evaluating in detail the performance of a particular protocol. In many cases precomputation can be exploited to eliminate much of the on-line computational cost, and this must also be taken into account. Such in-depth analysis must be done on a protocol by protocol basis, and is outside the scope of this paper, where we concentrate solely on the cost of the pairing.

Generating suitable non-supersingular elliptic curves can be quite difficult. Many algorithms have been suggested, but the current state-of-the-art has its own constraints. To summarise:-

Let F be the number of bits in the field modulus p, and G the size of the group order r in bits. The embedding degree is k. Then it is relatively easy to generate suitable curves with G < F/2 for any k. In some specific cases it is possible to generate curves with F/2 < G < F. For k = {3, 4, 6} it is possible to find curves with G = F. Recently Barreto and Naehrig [7] have discovered a remarkable formula for easily generating curves with G = F and k = 12, and Freeman [13] has also found a number of G = F solutions for the case k = 10.

In some applications, like a short signature scheme [10], it is very important that G = F, otherwise the signature will not be short. And at first glance this also appears to be most efficient. However in the majority of applications it is not so important, and so we will focus (mostly) to the condition G < F/2 where curves are plentiful and easy to find. An added advantage of choosing G < F/2 is that in this case the group order r can be chosen to have the lowest possibly Hamming weight, with some performance benefits [4].

For our purposes we define 3 levels of security, which are roughly within the limits laid down by Lenstra and Verheul [21]. These are referred to here as (1024/160) security, (2048/192) security, and (4096/224) security, where the first figure refers to the effective field size kF, and the second refers to the group size. Here we advocate fixing F = 512 and using k = 2, k = 4 and k = 8 to achieve the higher levels of security. Much greater granularity could be achieved by using intermediate values of k, and different values for F. And we acknowledge that an embedding degree of k = 2ⁿ may not in fact be optimal – in particular many nice tricks are known to exist for curves with k = 2ⁿ.3 ^m [7], [15].

However we justify our approach by pointing out that in practice the "algorithm" used by cryptographers is that if using an N bit "RSA equivalent" level of security, and cryptanalysts threaten at the N/2 level, then switch to 2N bit security, and we maintain that the convenience and scalability of k = 2ⁿ implementations will make them likely to be adopted in practise.

2 The Tate pairing

In this section we will review the Tate pairing algorithm on non-supersingular curves over fields of large prime characteristic p. We choose a prime r of size G which has a low Hamming weight. Next we find an elliptic curve over F^p where p is of size F and whose order is divisible by r, and where r|p ^k −1. Assuming that r does not divide p ⁱ − 1 for any value of i < k, then this is a curve suitable for use in pairing-based cryptography, and has an embedding degree of k. Observe the well-known fact that the cyclotomic polynomial

is irreducible, and

Since we know that r does not divide (p 2 n−1 −1), then it must divide Φ2ⁿ (p). The general Tate pairing is written as er(P, Q), where P is a point on E(Fp^k ) in a subgroup of order r and Q is also on E(Fp^k ), a representative of the coset of points which includes a member of a distinct subgroup, also of order r. The Tate pairing evaluates as a non-trivial element of the extension field Fp^k of order r.

The Tate pairing has the following relevant properties.

1.

for all a, b \in \mathbb{F}_r (Bilinearity) 2. e_r(P, P) = 1

The bilinearity property is the one that enables the implementation of many novel protocols.

In practise it is common for efficiency reasons to choose P ∈ E(Fp). It is also possible to manipulate Q as a point on the twisted curve defined over Fpk/² , before mapping it to a point on E(Fp^k ) prior to calculation of the pairing [6]. The coordinates of this point will exhibit some redundancy which can be exploited to speed up the calculation.

The Tate pairing algorithm consists of an application of Miller's algorithm followed by a final exponentiation. In Miller's algorithm the point P is implicitly multiplied by r using the standard double and add method, and at each iteration a distance relationship between the current point and the fixed point Q is calculated and accumulated in a Fp^k variable.

The purpose of the final exponentiation is to yield a unique result of order r. Now the field Fp^k has p ^k −1 elements in it, and by definition r|p ^k −1. Assuming that k = 2ⁿ the final exponentiation is to the power of (p 2 n − 1)/r. This can be written as (p 2 n−1 − 1)(Φ2ⁿ (p)/r. The exponentiation by (p 2 n−1 − 1) is cheap, using the Frobenius action and a single extension field inversion. The hard work here is the exponentiation to the power of Φ2ⁿ (p)/r.

As demonstrated in [30] the output of the Tate pairing can easily be compressed to half its size for even k. The compressed pairing returns an element of Fk/2.

2.1 Non-supersingular Vs Supersingular

There is a view (unsupported by any hard evidence) that non-supersingular curves are intrinsically "more secure" than supersingular curves. We will not comment on this. There is also a view that it is faster to use a supersingular curve, perhaps as a form of compensation for its perceived weakness. For prime field characteristic one is restricted to the case k = 2. Counterintuitively it has been demonstrated in [29] that the optimal pairing algorithm for certain nonsupersingular curves is in fact faster than that for the equivalent supersingular curve. It has also been suggested [18] that the ease of domain generation for supersingular curves makes it easier to generate a modulus p with a low Hamming weight, which in turn leads to faster implementation. But as they also point out a low Hamming weight p raises genuine security concerns. See section 5 below for more details on curve generation.

Nevertheless the vast majority of pairing based protocols have been described in the context of super-singular curves. Most can be transferred directly onto a non-supersingular curve and will work fine under the so-called co-Bilinear Diffie-Hellman assumption, co-BDH, rather than under the original (and arguably more intuitive) BDH assumption [9]. However there are subtle differences. Recall that when using supersingular curves a distortion map exists, and so ˆe(P, Q) = er(P, φ(Q)), where P, Q ∈ E(Fp). Then this distorted Tate pairing has the properties

``` 1. ˆer(aP, bQ) = ˆer(P, Q) ab for all a, b ∈ Fr (Bilinearity) 2. ˆer(P, P) 6= 1 3. ˆer(P, Q) = ˆer(Q, P) ```

Note that property 2 is different and property 3 is new. However the two pairings do share the important property of bilinearity which is the property required for the new pairing-based protocols. Sometimes these different properties can affect the behaviour of a protocol in interesting ways. However the main implication is that when working on non-supersingular curves we need to remember to treat the two parameters P ∈ E(Fp) and Q ∈ E(Fp^k ) quite differently. They cannot be interchanged or moved from side to side of the pairing calculation. Another potentially significant difference is that manipulation of the Q parameter prior to the pairing calculation is much simpler using super-singular curves, as Q will be a point on the base curve rather than on the curve taken over a larger extension field when k > 2, even using the "twist" idea (see below). Finally as pointed out in [28] it is possible to do useful precomputation on the first parameter if it should be a constant, but not on the second. Since the parameters can be switched from side to side with supersingular curves (using property 2 above) then this feature is easier to exploit in this setting than in the non-supersingular case.

We will require a scalable implementation of finite field arithmetic over the field Fp2ⁿ . The simplest way to do this will be to use a tower of extensions [24]. That is an element of Fp2ⁿ will be represented as a pair of elements from Fp2n−¹ , and so on recursively, starting with an efficient implementation of Fp.

For a suitable extension field arithmetic representation we first need an irreducible polynomial. For example if p = 3 mod 4, then x ² + 1 is a suitable irreducible polynomial for representation of the extension field Fp² . Elements of the field can be represented as a polynomial ax+b where a, b ∈ Fp. Alternatively "solve" the irreducible polynomial and set x = √ −1, and use as a representation ^{a +} b.^√ −1. Numbers in this form can be manipulated directly without explicit reference to an irreducible polynomial. Note that −1 is a quadratic non-residue with respect to p, iff p = 3 mod 4. Unfortunately this representation does not permit a simple tower of extensions to be built on top of it.

An alternative is to choose p = 1 mod 4. In this case the irreducible polynomial x ² + 2 can be chosen, and it does support an infinite tower of similar extensions. In practise we choose p = 5 mod 8, as it is important to have a simple formula for modular square roots, which does exist for this case, but not in general for p = 1 mod 8 (the calculation of square roots is required to generate points on the elliptic curve). So –

An element of Fp² is a + b.(−2)¹/² , or [a, b] a pair of elements from Fp. An element of Fp⁴ is c + d.(−2)¹/⁴ , or [c, d] a pair of elements from Fp² . An element of Fp⁸ is e + f.(−2)¹/⁸ , or [e, f] a pair of elements from Fp⁴ .

Now the implementation of each new layer of the tower can be built in an identical fashion on top of the previous layer. In the terminology of the programming language C++, a templated class which supports the operations of field addition, subtraction, multiplication and division (plus square rooting and Lucas powering/multi-exponentiation) can be written just once which will support all these instantiations. We omit implementation details as they are quite straightforward.

There is now an extra constraint on the curve generation process, that p = 5 mod 8. However we found that in most cases it was still easy to find suitable curves.

3.1 The Twist Idea

Let i be the k-th root of −2. Then if the point ([x, 0], [0, y]) is a point on the curve E : y ² = x ³ + Ax + B over the field Fp^k , then it is easy to verify by simple substitution that the point (i ²x, i⁴y) is a point on the twisted curve E0 : y ² = x ³ + i ⁴Ax + i ⁶B over the smaller field Fpk/² . It is also a simple matter to map points back from the twisted representation to the original curve [6].

3.2 Frobenius action

In the field Fp^k the Frobenius action is defined as the well-known identity

This means that exponentiation by p is almost for free. Using the Tower of extensions this formula can be applied recursively to x ^p and y p (and finally x ^p = x over F^p by Fermat's little theorem). However the term i ^p needs to be handled carefully. For example if i = (−2)¹/⁸ , and p = 5 mod 8, then i ^p = (−2)(p−5)/⁸ i 5 , where the term (−2)(p−5)/⁸ can be precalculated.

3.3 The final exponentiation of the Tate pairing

The hard part of the final exponentiation can be computed by precalculating Φ2ⁿ (p)/r and performing the exponentiation using compression of the pairing value, followed by Lucas exponentiation [30]. The exponent in this case will be approximately (k/2).lg(p) − lg(r) bits in length. This is quite efficient for small values of k, as we are dealing with elements over the compressed half-sized field Fpk/² . However for larger values of k, as pointed out by Granger, Page and Smart [15], it is more efficient to exploit multi-exponentiation [1]. Briefly Φ2ⁿ (p)/r is precalculated and stored as a number to the base p, and the Frobenius again exploited to allow a multi-exponentiation, with all exponents of length less than or equal to lg(p). Alternatively the whole of the final exponentiation to the power of (p 2 n − 1)/r could be included in the multi-exponentiation for a reasonably efficient and totally inverse-free pairing algorithm. Following the multi-exponentiation the output of the pairing can again be compressed if desired.

In our experience for the cases considered here the Lucas method is superior for k ≤ 4, while the multi-exponentiation method is superior for k ≥ 8.

4 The Algorithm

In this section we describe the BKLS version of the Tate Pairing algorithm (which in turn is based on the original Miller algorithm), closely following the treatment in [28], which is based on earlier work by Barreto et al [4] and Galraith et al. [14]. For efficiency we use a standard projective coordinate system, as described in [17], for the implicit point multiplication on E(Fp). First we need a function to execute a point addition, obtaining the line slope and finally calculating the contribution of the current iteration of the algorithm. Capital letters denote curve points, lower case letters and symbols represent elements of F^p or simple integers, and boldface letters represent elements of Fpk/² .

``` g(R, P, xq, yq) 1. x, y, z ← R 2. λn, λd = R.add(P) 3. return yλd − λn(xz − xqz 3 ) − yqz 3λd · i ```

The function A.add(B) performs the standard projective point addition, but also returns the line slope as the rational λn/λd. Note that the line slope is needed anyway to perform the point addition, so no extra work is involved. Assume that the point P is of prime order r.

``` Tate(r, p, P, Q) 1. m = 1 2. R = P 3. n = r − 1 4. xq, yq ← untwist(Q) ```

``` 5. for i ← blg(r)c − 2 downto 0 do 6. m = m2 · g(R, R, xq, yq) 7. if ni = 1 then m = m · g(R, P, xq, yq) 8. end for 9. m = m(p k/2−1) 10. return E(pk/2+1)/r(m) ```

The variable m is the Miller variable, and is the only variable that is an element of the full extension field Fp^k . The notation nⁱ refers to the i-th bit of n. Note that the choice of a low Hamming weight r means that this bit may be 1 only once in the entire calculation. The function untwist converts the point Q on the twisted curve to the point ([xq, 0], [0, yq]) on the original curve over the full extension field Fp^k , as described in section 3.1. The function E represents the "difficult" part of the final exponentiation, as described above.

In certain circumstances the first parameter to the pairing algorithm, the point P, may be a constant. If it is, then we can benefit significantly from a precomputation. All the points and slopes in the implicit multiplication of P by r can be precomputed and stored, and a much simpler affine version of the function g(.) can be used [28].

Using a tower of extensions this same algorithm can be used for any positive value of n, where the extension degree is k = 2ⁿ. Although implementation details might vary slightly (in particular in the untwist function and in the Frobenius action), by and large it is fair to say that the same basic algorithm works for any n. But how do we find suitable non-supersingular curves for k = 2, k = 4, k = 8 etc?

5 Curve Generation

It was long known that non-supersingular curves might exhibit a low embeddeding degree – hence the famous MOV condition [22] that was recommended to avoid the use of such curves in classic elliptic curve cryptography. Since they were generally regarded as a "bad thing", there was not much interest in deliberately generating them. Fortunately at around the time that pairings became cryptographically interesting Miyaji et al. published their paper on the construction of so-called MNT curves [23]. The original paper described constructions for nonsupersingular elliptic curves over fields of prime characteristic with embedding degrees of 3, 4 and 6 with G = F (Recall that F is the number of bits in the prime modulus p, and that G is the number of bits in the prime group order r). The condition G = F implies that the curve E(Fp) is of prime order, and such pairing-friendly curves are very rare, although subsequent developments extended the idea to produce many more curves where the curve order was hr, for small values of h [31]. The term MNT curve is now commonly (and sometimes confusingly) used to refer to any non-singular curve with a useful embedding degree.

A major development was an algorithm of Cocks and Pinch (unfortunately unpublished, but essentially the same algorithm is described in [8]). This method makes it quite easy to find a curve with any desired embedding degree, but with the restriction G < F/2.

Subsequently a series of papers [5], [11], [12], [31] discovered alternative strategies which in special cases could find curves with F/2 < G < F. Although at first glance it appears preferable to choose curves with G = F, unfortunately until very recently there was no known method for doing so with k > 6. This situation changed with the surprising discovery by Barreto and Naehrig [7] that solutions with G = F for the particular case of k = 12 were indeed possible, followed by the discovery by Freeman [13] of G = F solutions for k = 10. However it seems to be generally true that for G > F/2 the number of possible curves starts to become constrained, and in particular one no longer has control of the choice of r. This is a pity because it is clearly more efficient if r is chosen to have a low Hamming weight.

Since it is our ideal to develop a method which can be scaled without limit, the Cocks and Pinch algorithm seems ideal, although we will also consider candidate curves generated using alternative methods, such as that described by Brezing and Weng [11].

These algorithms give us enough information to know that a suitable curve exists, with the desired embedding degree and with a curve order divisible by the chosen r. However to find the actual curve parameters we must use the method of Complex Multiplication as described in [17], and implemented in, for example, [27].

The actual elliptic curves E_n(\mathbb{F}_p) that we used are described using the standard Weierstrass representation [17] for curves of prime characteristic, y^2 = x^3 + Ax + B .

``` \begin{split} \mathbf{E_{160}} \\ F &= 512, G = 160, k = 2 \\ p &= 8d19a10497f9cc35bc026c6a7651da9ce4d794d4d67a4ab6e77d3b322e462b899 \\ &\quad 1a31e8fbfcb60b411f0e5afd85977d7eee3dd09cd197dafe4f377c3e23af2af \\ A &= -3 \\ B &= 4d438977ff9360a5df4294efe4bd7465351b7d19e99c17463f3c7f72ab95ca3c95 \\ &\quad c82339f2c8b9f8801bc29328ae2d73969493d719fbbe3d34f689778ebd85ae \\ r &= 800000000000000000000000000000000000 ```

``` \begin{aligned} \mathbf{E_{160e}} \\ F &= 512, G = 160, k = 2 \\ p &= dac2f97cdd22ac93ccc12106f6541b748c9d8f71c806b1023b95d69281eb5f739 \\ f9a3efc931882113ca321a0ac348d825249b44e45c180726ec6e896e6de568b \\ A &= 0 \\ B &= 5 \\ r &= 100000000000000000000000000000000000 ```

``` E_{160s} F = 256, G \ge 160, k = 4 p = 555555d61555a64609707b5f09cb9d19c8c8fe1d68029a58dcc79a17ddd9acab A = 0 B - 2 r = 40000040601018484216141e16c9452503153868301 F = 512, G = 192, k = 4 p = b7fd9899de545d9d6b3644da15e9b662fd08ca211da537978b5556299c6b02f77 d5e776d48c14b14c65e905646de2318391b0ac3820ab2be9eb54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70927ee9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70926e9b54b70966e9b54b70966e9b54b70966e9b54b70966e9b54b70966e9b54b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b70966e9b64b7096666e9b64b70966e9b64b70966e9b64b709666e9b64b709666e9b64b709666e9b64b709666e9b64b709666e9b64b709666e9b64b7096666e9b64b709666666666696666666666666666666666666 B = 865b15c872e80609aC5a6b397438a020d9c1cfbccd2d7e57480b1c80f6325461f b1bf32b28d689412c6875e267676d926dd0232dbcc049efa670cfe2cb971a65 r = 800000000000000000000000000000000000 E_{192bw} F = 256, G = 192, k = 8 p = cc485d26177a1a5fcc9d53ba93da298fd7f2f23d8fc02a8123bf24f9548a5f15 A = 0 B = 2 r = 9d0261dd89cf83d5d20198162c22c942ef68622a6df25621 \mathbf{E_{224}} F = 512, G = 224, k = 8 p = bc1e1bf222c03dfd1bd55f2f220cf3b3f7f185834d6db68cdcc11d413e77ea4ee cf8ffa5038e46c303a407da24b15aa57cc8bd6df69c5d9806742fca59f8604d A = -3 B = 62dc6331021838f1b0557dd1b016b4898fc16c084b8f2a4b9368d0ce1c4e744c6 e4319e1bbdd27ad060439ba50f0eb6cbc79e74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371263f024aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c74404cd371264aecabfa9c744404cd371264aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c744404cd371264aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c744404cd371264aecabfa9c7464aecabfa9c744404cd371264aecabfa9c744404cd371264aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c7464aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c7664aecabfa9c764aecabfa9c764aecabfa9c764aecabfa9c7664aecabfa9c766666aecabfa9c76666aecabfa9c766666aecabfa9c766666aecabfa9c7666666ae r = 800000000000000000000000000000000000 ```

The curves E_{160} , E_{192} and E_{224} have a field size of 512 bits, and embedding degrees of 2, 4 and 8 respectively. Observe the low Hamming weight group orders r, which are of sizes 160, 192 and 224 bits respectively. These were all generated using variations of the Cocks and Pinch algorithm. For the E_{160} curves, p=3mod 4 and we can use the irreducible polynomial x^2 + 1 . This will be a little faster. For all the other curves p = 5 \mod 8 to facilitate the building of the tower of extensions using the irreducible polynomial x^2 + 2 as described above. It was particularly easy to find curves using the Cocks and Pinch algorithm, and we would expect that it would be as easy to find curves with higher embedding degrees k > 8. The curve E_{192bw} was generated using the Brezing-Weng algorithm [11], and has a field size of 256 bits, a group size of 192 bits (of hamming weight 86), and an embedding degree of 8. Therefore in terms of security it should be similar to E_{192} . The Brezing and Weng curve was much harder to find, given the constraints imposed. The curve E_{160s} was found using an unpublished method of our own, and has a field size of 256 bits and a group size a little greater than 160 bits, with an embedding degree of 4. This curve was selected to have a lower than average hamming weight of just 47. The curve E_{160e} is similar to E_{160} but uses an elliptic curve with an efficient endomorphism, as described in [29].

Timings were carried out on a 3GHz Pentium IV processor, and are shown in Table 1. In particular we compare the scaling approach advocated here, with fixed size prime modulus and doubling k, with the alternative scaling method of simply doubling the size of the prime modulus, and keeping k = 2 fixed, using curves E192^a and E224a. We also compare curves generated using the Cocks and Pinch algorithm with curves generated using alternative approaches such as [11] for which G > F/2.

Table 1. Timings – Pentium IV 3GHz – Tate Pairing

Observe that the curve generated using the simple Cocks and Pinch algorithm E¹⁹² is in practice a little faster than the Brezing and Weng curve E192bw for the same security level. (Note that for the Brezing and Weng curve we do not use the algorithm as described above, but rather a standard windowing algorithm, which is more suitable in this case where the Hamming weight of r is not insignificant.) The method of doubling the prime modulus as a method of scaling suffers, as point multiplication on an elliptic curve over a large prime field is very expensive. Precomputation (if it applies) solves this problem to an extent, but only at the cost of large precomputed tables.

For comparison purposes, it is interesting to observe that an optimized implementation of the Tate pairing on a k = 4 supersingular curve over F^{2 379} using the η^T approach [3] takes just 3.8 milliseconds on the same platform. The eta^T algorithm does not benefit from precomputation.

7 The Weil Pairing

Originally it was thought that the Tate pairing would always be a better choice than the Weil pairing, a view articulated for example in [8].

It has been suggested recently that at higher levels of security the Weil pairing may in fact be more efficient than the Tate pairing [2], [18]. This is supported by the observation that the final exponentiation of the Tate pairing makes a significant contribution to the overall timing. On the other hand the Weil pairing requires two invocations of Miller's algorithm, but no final exponentiation.

Here we will try to determine experimentally if there is a cross-over point at which the Weil pairing becomes superior. We observe that rather than using the standard Weil pairing directly it will be advantageous to consider the Weil pairing raised to the power of p k/² − 1 (using the fast Frobenius action) as this permits various optimizations similar to the denominator elimination optimization described by Barreto et al [4]. This observation was also made independently by Koblitz and Menezes [18].

The parameters P and Q are as above, although this time it is a requirement that Q should also be of order r.

The function g(.) is more complex for the Weil pairing, as a pair of point additions are required as we implement two invocations of the Miller algorithm. As before we use projective coordinates for the implicit point multiplication of the point P on E(Fp), but affine coordinates for the much more expensive point multiplication of Q on the twisted curve E⁰ (Fpk/² ). The untwisting required of the points is merged into the formulae, whose derivation is left as an exercise for the reader. Note that the function g(.) formally computes a numerator and a denominator. However the denominator can be replaced by its conjugate, and the implied division replaced by a multiplication, exploiting the exponentiation of the final result to the power of p k/² − 1.

``` g(R, P, S, Q, xp, yp, xq, yq) 1. x, y, z ← R 2. λn, λd = R.add(P) 3. n = yλd − λn(xz − xqz 3 ) − yqz 3λd · i 4. x, y ← S 5. λ = S.add(Q) 6. d = i 4yp + (y − λ(x − i 2xp)) · i 7. return (n · d) ```

The full Weil pairing algorithm can now be given. Note the absence of the final exponentiation. Otherwise the structure is very similar to that of the Tate pairing.

``` Weil(r, p, P, Q) 1. m = 1 2. R = P 3. S = Q 4. n = r − 1 5. xp, yp ← P 6. xq, yq ← untwist(Q) 7. for i ← blg(r)c − 2 downto 0 do 8. m = m2 · g(R, R, S, S, xp, yp, xq, yq) 9. if ni = 1 then m = m · g(R, P, S, Q, xp, yp, xq, yq) 10. end for ```

11.

12. return m

Using the same curves as above, we proceeded to obtain timings for the Weil pairing, for the curves using F = 512 and k = 2, 4, 8. For the Weil pairing precomputation for a constant second parameter Q is particularly rewarding, as the point multiplication on the twisted curve (for k = 4, 8) is very expensive – so we include timings for this case as well.

Curve (kF/G) k F (bits) G (bits) Time (ms) with precomp. E¹⁶⁰ (1024/160) 2 512 160 20 16 E¹⁹² (2048/192) 4 512 192 37 18 E192bw (2048/192) 8 256 192 40 23 E²²⁴ (4096/224) 8 512 224 90 55

Table 2. Timings – Pentium IV 3GHz – Weil Pairing

Observe that the Weil pairing is significantly more efficient at the security level (4096/224), but only if precomputation is possible.

8 Conclusions

We have demonstrated that using non-supersingular MNT curves we can easily scale the security of pairing based cryptosystems, effectively without limit. The basic algorithm remains the same at all levels of security. The proposed method of doubling the embedding degree to reach the next level of security seems to compare well with the alternative approach of simple doubling the size of the modulus.

Finally we provide experimental evidence to support the view that at higher levels of security the Weil pairing can become more efficient than the Tate pairing, but only if precomputation is possible, that is if one of the pairing parameters is a constant.

References

• 1. R. M. Avanzi. On multi-exponentiation in cryptography. Cryptology ePrint Archive, Report 2002/154, 2002. http://eprint.iacr.org/2002/154.
• 2. Paulo Barreto. Private communication.
• 3. Paulo S. L. M. Barreto, Steven Galbraith, Colm O hEigeartaigh, and Michael Scott. Efficient pairing computation on supersingular abelian varieties. Cryptology ePrint Archive, Report 2004/375, 2004. http://eprint.iacr.org/2004/375.
• 4. P.S.L.M. Barreto, H.Y. Kim, B. Lynn, and M. Scott. Efficient algorithms for pairing-based cryptosystems. In Advances in Cryptology – Crypto'2002, volume 2442 of Lecture Notes in Computer Science, pages 354–68. Springer-Verlag, 2002.

• 5. P.S.L.M. Barreto, B. Lynn, and M. Scott. Constructing elliptic curves with prescribed embedding degrees. In Security in Communication Networks – SCN'2002, volume 2576 of Lecture Notes in Computer Science, pages 263–273. Springer-Verlag, 2002.
• 6. P.S.L.M. Barreto, B. Lynn, and M. Scott. On the selection of pairing-friendly groups. In Selected Areas in Cryptography – SAC 2003, volume 3006 of Lecture Notes in Computer Science, pages 17–25. Springer-Verlag, 2003.
• 7. P.S.L.M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order. Cryptology ePrint Archive, Report 2005/133, 2005. http://eprint.iacr.org/ 2005/133.
• 8. I. F. Blake, G. Seroussi, and N. P. Smart, editors. Advances in Elliptic Curve Cryptography, Volume 2. Cambridge University Press, 2005.
• 9. D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. SIAM Journal of Computing, 32(3):586–615, 2003.
• 10. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In Advances in Cryptology – Asiacrypt'2001, volume 2248 of Lecture Notes in Computer Science, pages 514–532. Springer-Verlag, 2002.
• 11. F. Brezing and A. Weng. Elliptic curves suitable for pairing based cryptography. Cryptology ePrint Archive, Report 2003/143, 2003. Available from http://eprint.iacr.org/2003/143.
• 12. R. Dupont, A. Enge, and F. Morain. Building curves with arbitrary small MOV degree over finite prime fields. Cryptology ePrint Archive, Report 2002/094, 2002. http://eprint.iacr.org/2002/094.
• 13. R. Dutta, R. Barua, and P. Sarkar. Constructing pairing-friendly elliptic curves with embedding degree 10. Cryptology ePrint Archive, Report 2006/026, 2006. http://eprint.iacr.org/2006/026.
• 14. S. Galbraith, K. Harrison, and D. Soldera. Implementing the Tate pairing. In Algorithm Number Theory Symposium – ANTS V, volume 2369 of Lecture Notes in Computer Science, pages 324–337. Springer-Verlag, 2002.
• 15. R. Granger, D. Page, and N. P. Smart. Cryptology ePrint Archive, Report 2006/059, 2006. http://eprint.iacr.org/2006/059.
• 16. M. J. Hinek, M. K. Low, and E. Teske. On some attacks on multi-prime RSA. In Selected Areas in Cryptography, volume 2595 of Lecture Notes in Computer Science, pages 385–404. Springer-Verlag, 2002.
• 17. IEEE Std 1363-2000. Standard specifications for public-key cryptography. IEEE P1363 Working Group, 2000.
• 18. Neal Koblitz and Alfred Menezes. Pairing-based cryptography at high security levels. Cryptology ePrint Archive, Report 2005/076, 2005. http://eprint.iacr. org/2005/076.
• 19. RSA Laboratories. PKCS # 1 v2.0 Amendment 1 Multi-prime RSA, 2000.
• 20. A. K. Lenstra and E. R. Verheul. The XTR public key system. In Advances in Cryptology – Crypto'2000, volume 1880 of Lecture Notes in Computer Science, pages 1–19, Santa Barbara, USA, 2000. Springer-Verlag.
• 21. Arjen K. Lenstra and Eric R. Verheul. Selecting cryptographic key sizes. Journal of Cryptology, 14(4):255–293, 2001.
• 22. A. Menezes, T. Okamoto, and S. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 39:1639– 1646, 1993.
• 23. A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals, E84-A(5):1234– 1243, 2001.

• 24. Y. Nogami and Y. Morikawa. A fast implementation of elliptic curve cryptosystem with prime order defined over fp⁸ , 1998. http://www.trans.cne.okayama-u.ac. jp/nogami-group/papers/kiyou(2).pdf.
• 25. J. M. Pollard. Monte carlo methods for index computation (mod p). Mathematics of Computation, 32:918–924, 1978.
• 26. K. Rubin and A. Silverberg. Supersingular abelian varieties in cryptology. In Advances in Cryptology – Crypto 2002, volume 2442 of Lecture Notes in Computer Science, pages 336–353. Springer-Verlag, 2002.
• 27. M. Scott, 2002. ftp://ftp.computing.dcu.ie/pub/crypto/cm.exe.
• 28. M. Scott. Computing the Tate pairing. In CT-RSA, volume 3376 of Lecture Notes in Computer Science, pages 293–304. Springer-Verlag, 2005.
• 29. M. Scott. Faster pairings using an elliptic curve with an efficient endomorphism. In Progress in Cryptology – Indocrypt 2005, volume 3797 of Lecture Notes in Computer Science, pages 258–269. Springer-Verlag, 2005. Also available from http://eprint. iacr.org/2005/252.
• 30. M. Scott and P. Barreto. Compressed pairings. In Advances in Cryptology Crypto' 2004, volume 3152 of Lecture Notes in Computer Science, pages 140–156. Springer-Verlag, 2004. Also available from http://eprint.iacr.org/2004/032/.
• 31. M. Scott and P. Barreto. Generating more MNT elliptic curves. Cryptology ePrint Archive, Report 2004/058, 2004. Available from http://eprint.iacr.org/2004/ 058/.
• 32. P. J. Smith and M. J. Lennon. LUC : A new public key system. In Proceedings of the Ninth IFIP International Symposium on Computer Security '93, pages 97–111. Elsevier Science Publications, 1994.