Upcoming conferences and recent announcements

  • The list of speakers for the ECC 2016 conference is at
    http://ecc2016.yasar.edu.tr/invited.html.

    Here are the speakers:

    • Benjamin Smith, “Fast, uniform, and compact scalar multiplication for elliptic curves and genus 2 Jacobians with applications to signature schemes” and “μKummer: efficient hyperelliptic signatures and key exchange on microcontrollers”
    • Cyril Hugounenq, “Explicit isogenies in quadratic time in any characteristic”
    • Daniel Genkin, “ECDH Key-Extraction via Low-Bandwidth Electromagnetic Attacks on PCs” and “ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels” and “CacheBleed: A Timing Attack on OpenSSL Constant Time RSA”
    • Jens Groth, “On the Size of Pairing-based Non-interactive Arguments”
    • Maike Massierer, “Computing L-series of geometrically hyperelliptic curves of genus three”
    • Mehmet Sabır Kiraz, “Pairings and Cloud Security”
    • Pascal Sasdrich, “Implementing Curve25519 for Side-Channel–Protected Elliptic Curve Cryptography”
    • Patrick Longa, “Efficient algorithms for supersingular isogeny Diffie-Hellman”
    • Razvan Barbulescu, “Extended Tower Number Field Sieve: A New Complexity for Medium Prime Case”
    • Sebastian Kochinke, “Computing discrete logarithms with special linear systems”
    • Shashank Singh, “A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm”
    • Shoukat Ali, “A new algorithm for residue multiplication modulo $2^{521}-1$”
    • Tung Chou, “The Simplest Protocol for Oblivious Transfer” and “Sandy2x: new Curve25519 speed records”

    The conference organisers wish to reassure conference attendees that it is safe to come to Turkey for the conference: “The life in Izmir is just as usual: sunny and slow-going. We are preparing for ECC and we would like to serve our guests in the best way we can.”

  • The schedule for the Algorithmic Number Theory conference (ANTS) is at
    http://www.mathematik.uni-kl.de/~thofmann/ants/schedule.html.

  • Aurore Guillevic, François Morain and Emmanuel Thomé recently announced a solution to an ECDLP instance on a 170-bit pairing-friendly curve with embedding degree 3.
    In other words, they solved a DLP in a finite field \mathbb{F}_{p^3}^* of size around 510 bits. You can read further details here and here.

  • Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata and Colin Stahlke have reported a new DLP computation using the number field sieve in a 768-bit field \mathbb{F}_{p}^*. The details are here.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Complete group laws for prime-order elliptic curves: a step towards safer implementations of standard curves

Eurocrypt 2016 didn’t feature many papers directly relevant to curve-based cryptography, but one presentation stood out: Joost Renes presented his work with Craig Costello and Lejla Batina on complete addition laws for prime-order elliptic curves.

From a cryptographic point of view, complete addition laws are important for designing and implementing uniform and constant-time algorithms on elliptic curves. The most well-known and successful example of this is the (twisted) Edwards model for elliptic curves, where a single formula can be used for doubling and adding, without any exceptions or special cases. In contrast, consider the traditional chord-and-tangent group law on the Weierstrass model of an elliptic curve.  This group law can’t be applied to compute P + P, for example; instead, we have a separate doubling formula using the tangent. And until now, nobody has written down a single efficient complete addition law for the points on prime-order elliptic curves – including the prime-order curves that were standardized by NIST, and their international counterparts like Brainpool and ANSSI. This means that implementing standardized curves in a safe way is a much more complicated business than it should be!

Over twenty years ago, Bosma and Lenstra studied the group laws on elliptic curves. They concentrated on the case where an elliptic curve E is embedded in the projective plane as a Weierstrass model, but Arene, Kohel, and Ritzenthaler have since generalized their results to any projective embedding of any elliptic curve, and also to abelian varieties of any dimensions. To make things more precise, suppose E is an elliptic curve in projective Weierstrass form, with coordinates X, Y, and Z.  A group law is a triple of polynomials (F_X,F_Y,F_Z) such that P + Q = (F_X(P,Q):F_Y(P,Q):F_Z(P,Q)) for the pairs (P,Q) of points in some open subset of E\times E (the cartesian product of E with itself). This means that the group law is allowed to “fail” on some subset of the pairs of points on E, provided that subset is defined by a nontrivial algebraic relation. Basically, the group law is allowed to fail on what I will call a failure curve of points in the surface E\times E (this curve may be reducible; strictly speaking, it’s an effective divisor on E\times E). For any fixed P, there is a bounded number of Q such that the group law fails to add Q to P, and that bound depends only on the group law, not P.

To make this notion of failure more precise, we can add another requirement to the definition of a group law: for any pair (P,Q) of input points on E\times E, either (F_X(P,Q):F_Y(P,Q):F_Z(P,Q)) = P + Q (ie, the group law holds) or (F_X(P,Q),F_Y(P,Q),F_Z(P,Q)) = (0,0,0). From a computational point of view this is very nice, because (0,0,0) does not correspond to a projective point; so if we evaluate the group law at a pair of points then either the result is correct, or it is not a projective point – and this case is extremely easy to identify. If the formula is ever wrong, it’s so obviously wrong that you see it immediately.

A complete system of group laws is a collection of group laws that covers all of the pairs of points on E: that is, the common intersection of all of the failure curves is empty. Bosma and Lenstra showed that for an elliptic curve, any complete system must contain at least 2 group laws. However, this result only holds over the algebraic closure; and in cryptography, we don’t work over the algebraic closure, we work over a fixed finite field \mathbb{F}_q. And this is the crucial point: we can get away with just one group law, so long as none of the pairs of points on its failure curve are defined over \mathbb{F}_q! If they’re all defined over some extension, then they will never be inputs to our cryptographic algorithm, and we can simply ignore their existence.  Arene, Kohel, and Ritzenthaler take this to its logical conclusion, showing that this can always be done for any elliptic curve or abelian variety (apart from some pathological cases over extremely small fields, which are irrelevant to cryptography).

The particularly nice thing about Bosma and Lenstra’s paper is that they give a clear description of what the failure curves look like for the simplest nontrivial class of group laws, which is where all of the polynomials are biquadratic (that is, each F_X, F_Y, and F_Z is homogeneous of degree 2 in the coordinates of P, and also in the coordinates of Q). In this case, the failure curves all correspond to lines: for each group law (F_X,F_Y,F_Z), there is a line L in the projective plane such that the group law fails on (P,Q) if and only if P-Q is in the intersection of E with L.

At Eurocrypt, Joost Renes explained that there is an obvious way to apply this to prime-order elliptic curves: for a complete group law on such a curve E/\mathbb{F}_p, we can take the biquadratic group law whose failure line is the x-axis. This works because the intersection with E consists of the nonzero 2-torsion points – and since E(\mathbb{F}_p) has prime order, none of those are defined over \mathbb{F}_p, so they can’t be the difference of any pair of \mathbb{F}_p-points, and therefore the group law can’t fail on any pair of points in E(\mathbb{F}_p).  So far so good.  But Bosma and Lenstra actually wrote down that group law as an example in their paper, and the formulae take up a whole page and a half!  I’m sure that plenty of cryptographers had seen it, and thought “that’s all very nice in theory, but…”

So now we come to the main contribution of the paper: Joost, Craig, and Lejla show that this “it’ll never work” intuition is completely wrong.  They simplify the formulae (following Arene, Kohel, and Ritzenthaler); they derive efficient straight-line algorithms to evaluate the polynomials; and they show that not only can this group law be computed efficiently, it’s actually competitive with the best known (non-complete) formulae for projective Weierstrass curves.  So if you find yourself implementing the group law on a prime-order curve (for whatever reason, be it scientific or political), then you should definitely consider doing it the way their paper suggests.  You won’t lose much speed, and you’ll gain a lot of safety and simplicity.

–Ben Smith

Posted in Uncategorized | Leave a comment

Kim–Barbulescu variant of the Number Field Sieve to compute discrete logarithms in finite fields

In February 2016, Kim and Barbulescu posted on eprint a merged version of two earlier pre-prints ([eprint:Kim15] and [eprint:Barbulescu15]). This preprint is about computing discrete logarithms (DL) in finite fields and presents a new variant of the Number Field Sieve algorithm (NFS) for finite fields \mathbb{F}_{p^n}. The Number Field Sieve algorithm can be applied to compute discrete logarithms in any finite field of medium to large characteristic \mathbb{F}_{p^n}. Kim and Barbulescu improve its asymptotic complexity for finite fields where n is composite, and one of the factors is of an appropriate size. The paper restricts to non-prime-power extension degree (e.g. n=9 or n=16 is not targeted) but a generalization to any non-prime n is quite easy to obtain. Typical finite fields that are target groups in pairing-based cryptography are affected, such as \mathbb{F}_{p^6} and \mathbb{F}_{p^{12}}.

Pairing-based cryptography

A pairing is a bilinear map defined over an elliptic curve. It outputs a value in a finite field. This is commonly expressed as e : ~ \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T where \mathbb{G}_1 and \mathbb{G}_2 are two (distinct) prime order subgroups of an elliptic curve, and \mathbb{G}_T is the target group, of same prime order. More precisely, we have

\begin{array}{lccccc}    e: & \mathbb{G}_1 & \times & \mathbb{G}_2 & \to & \mathbb{G}_T \\   & \cap &        & \cap &     & \cap  \\  & E(\mathbb{F}_p)[\ell] &  & E(\mathbb{F}_{p^n})[\ell] & & \boldsymbol{\mu}_{\ell}  \subset \mathbb{F}_{p^n}^{*}\\  \end{array}

where \boldsymbol{\mu}_{\ell} is the cyclotomic subgroup of \mathbb{F}_{p^n}^{*}, i.e. the subgroup of \ell-th roots of unity: \boldsymbol{\mu}_{\ell} = \left\{  z \in \mathbb{F}_{p^n}^{*}, ~ z ^ \ell = 1   \right\}~.

The use of pairings as a constructive tool in cryptography had some premices in 1999 and started to be used in 2000. Its security relies on the intractability of the discrete logarithm problem on the elliptic curve (i.e. in \mathbb{G}_1 and \mathbb{G}_2) and in the finite field \mathbb{F}_{p^n} (i.e. in \mathbb{G}_T).

The expected running-time of a discrete logarithm computation on an elliptic curve and in a finite field is not the same: this is O(\sqrt{\ell}) in the group of points E(\mathbb{F}_p)[\ell], and this is L_{p^n}[1/3, c] in a finite field \mathbb{F}_{p^n}, where L is the notation L_{p^n}[1/3, c] = \exp\left( (c+o(1)) (\log p^n)^{1/3} (\log \log   p^n)^{2/3} \right) ~. The asymptotic complexity in the finite field depends on the total size p^n of the finite field. It means that we can do cryptography in an order \ell subgroup of \mathbb{F}_{p^n}, whenever p^n is large enough.

Small, medium and large characteristic.

The finite fields are commonly divided into three cases, depending on the size of the prime p (the finite field characteristic) compared to the extension degree n. Each of the three cases has its own index calculus variant, and the most appropriate variant that applies qualifies the characteristic (as small, large or medium):

  • small characteristic: one uses the function field sieve (FFS) algorithm, and the quasi-polynomial-time algorithm when the extension degree is suitable for that (i.e. smooth enough);
  • medium characteristic: one uses the NFS-HD algorithm. This is the High Degree variant of the Number Field Sieve (NFS) algorithm. The elements involved in the relation collection are of higher degree compared to the regular NFS algorithm.
  • large characteristic: one uses the Number Field Sieve algorithm.

Each variant (QPA, FFS, NFS-HD and NFS) has a different asymptotic complexity.

Quasi Polynomial Time algorithm for small characteristic finite fields

Small characteristic finite fields such as \mathbb{F}_{2^n} and \mathbb{F}_{3^n} where n is composite are broken for pairing-based cryptography with the QPA algorithm (see this blog post).
It does not mean that supersingular curves are broken but it means that the pairing-friendly curves in small characteristic are broken, and only supersingular pairing-friendly curves were available in small characteristic. There exist supersingular pairing-friendly curves in large characteristic which are still safe, if the finite field \mathbb{F}_{p^n} is chosen of large enough size.

How it affects pairing-based cryptography.

It was assumed in order to set up the key-sizes of pairing-based cryptography that computing a discrete logarithm in any finite field \mathbb{F}_{p^n} of medium to large characteristic is of same difficulty at least as computing a discrete logarithm in a prime field of the same total size. The key-size were chosen according to the complexity formula L_{p^n}[1/3, (64/9)^{1/3} = 1.923].

The finite fields targeted by this new variant are of the form \mathbb{F}_{p^n}, where n is composite (e.g. n=6, n=12) and there exists a small factor d of n (e.g. 2 or 3 for 6 and 12). In that case, this is possible to consider both the finite field \mathbb{F}_{p^n} and the two number fields involved in the NFS algorithm as a tower of an extension of degree n/d on top of an extension of degree d. With this representation, combined with previously known polynomial selection methods, the norm of the elements involved in the relation collection step (second step of the NFS algorithm) is much smaller. This provides an important speed-up of all the algorithm and decreases the asymptotic complexity below the assumed L_{p^n}[1/3, 1.92] complexity. That is why in certain cases, the key sizes should be enlarged.

Outline

It start with a brief summary on the previous state of the art in DL computation in \mathbb{F}_{p^n}, then the Kim–Barbulescu variant is sketched, and a possible key-size update in pairing-based cryptography is discussed. This is not reasonnable at the time of writting to propose practical key-size update, but we can discuss about an estimate, based on the new asymptotic complexities.

The Number Field Sieve algorithm (NFS)

The NFS algorithm to compute discrete logarithms applies to finite fields \mathbb{F}_{p^n} = \mathbb{F}_q where p (the characteristic) is of medium to large size compared to the total size p^n of the finite field. This is measured asymptotically as p \geq L_{p^n}[\alpha, c] where \alpha > 1/3 and the L notation is defined as L_{p^n}[1/3, c] = \exp\left( (c+o(1)) (\log p^n)^{1/3} (\log \log p^n)^{2/3} \right) ~.

Since in pairing-based cryptography, small characteristic is restricted to \mathbb{F}_{2^n} and \mathbb{F}_{3^n}, we can simplify the situation and say that the NFS algorithm and its variants apply to all the non-small-characteristic finite fields used in pairing-based cryptography. The Kim–Barbulescu pre-print contains two new asymptotic complexities for computing discrete logarithms in such finite fields. Prime fields \mathbb{F}_p are not affected by this new algorithm. The finite fields used in pairing-based cryptography that are affected are \mathbb{F}_{p^6} and \mathbb{F}_{p^{12}} for example.

The NFS algorithm is made of four steps:

  1. polynomial selection,
  2. relation colection,
  3. linear algebra,
  4. individual discrete logarithm.

The Kim–Barbulescu improvement presents a new polynomial selection that combines the Tower-NFS construction (TNFS) [AC:BarGauKle15] with the Conjugation technique [EC:BGGM15]. This leads to a better asymptotic complexity of the algorithm. The polynomial selection determines the expected running time of the algorithm. The idea of NFS is to work in a number field instead of a finite field, so that a notion of small elements exists as well as a factorization of the elements into prime ideals. This is not possible in a finite field \mathbb{F}_{p^n}.

Take as an example the prime p = 3141592653589793238462643383589 = \lfloor 10^{30}\pi \rfloor + 310 as in Kim Barbulescu eprint and consider \mathbb{F}_{p^6}. The order of the cyclotomic subgroup is p^2 - p + 1 = 7\cdot 103 \cdot \ell and the 194-bit prime \ell = 13688771707474838583681679614171480268081711303057164980773 is the largest prime divisor of p^2 - p + 1 = \Phi_6(p). Since p\equiv 1 \bmod 6, one can construct a Kummer extension \mathbb{F}_p[x]/(x^6+2), where f(x) = x^6+2 is irreducible modulo p. Then to run NFS, the idea of Joux, Lercier, Smart and Vercauteren in 2006 [JLSV06] was to use \mathbb{Z}[x]/(f(x)) as the first ring, and \mathbb{Z}[x]/(g(x) where g(x)=f(x)+p as the second one to collect relations in NFS. Take the element 971015 \alpha_f^2 + 958931 \alpha_f + 795246. Its norm in \mathbb{Z}[\alpha_f] = \mathbb{Z}[x]/(f(x)) is 122-bit long. Its norm in \mathbb{Z}[\alpha_g] = \mathbb{Z}[x]/(g(x)) is 322-bit long, the total is 444 bits.

Why do we need two sides (the two rings \mathbb{Z}[x]/(f(x)) and \mathbb{Z}[x]/(g(x)))? Because when mapping these two elements from \mathbb{Z}[x]/(f(x)) and \mathbb{Z}[x]/(g(x)) to \mathbb{F}_{p^n}, one maps x \mapsto z since f \equiv g \bmod p, so that 971015 \alpha_f^2 + 958931 \alpha_f + 795246 \mapsto 971015 z^2 + 958931 z + 795246 and at the same time, 971015 \alpha_g^2 + 958931 \alpha_g + 795246 is mapped to the same element. What is the purpose of all of this? We will obtain a different factorization into prime ideals in each ring, so that we will get a non-trivial relation when mapping each side to \mathbb{F}_{p^n}. Now the game is to define polynomials f and g such that the norm is as low as possible, so that the probability that an element will factor into small prime ideals is high.

A few new polynomial selection methods were proposed since 2006, to reduce this norm, hence improving the asymptotic complexity of the NFS algorithm. In practice, each finite field is a case study, and the method with the best asymptotic running-time will not obviously gives the smallest norms in practice. That is why cryptanalysts compare the norm bounds in addition to comparing the asymptotic complexity. This is done in Table 5 and Fig. 2 of the Kim–Barbulescu pre-print.

What is the key-idea of the Kim–Barbulescu method? It combines two previous techniques: the Tower-NFS variant [AC:BarGauKle15] and the Conjugation polynomial selection method [EC:BGGM15]. Moreover, it exploits the fact that n is composite. Sarkar and Sigh started in this direction in [EC:SarSin16] and obtained a smaller norm estimate (the asymptotic complexity was not affected significatively). We mention that few days ago, Sarkar and Singh combined the Kim–Barbulescu technique with their polynomial selection method [EPRINT:SarSin16].

Here is a list of the various polynomial selection methods for finite fields \mathbb{F}_{p^n}.

  • the Joux–Lercier–Smart–Vercauteren method that applies to medium-characteristic finite fields, a.k.a. JLSV1, whose asymptotic complexity is L_{p^n}[1/3, (128/9)^{1/3} = 2.42].
  • the Conjugation method that applies to medium-characteristic finite fields, whose asymptotic complexity is L_{p^n}[1/3, (32/3)^{1/3} = 2.201].
  • the JLSV2 method that applies to large-characteristic finite fields, whose asymptotic complexity is L_{p^n}[1/3, (64/9)^{1/3} = 1.923].
  • the generalized Joux–Lercier (GJL) method that applies to large-characteristic finite fields, whose asymptotic complexity is L_{p^n}[1/3, (64/9)^{1/3} = 1.923].
  • the Sarkar–Singh method that allows a trade-off between the GJL and the Conjugation method when n is composite.

Back to our \mathbb{F}_{p^6} example, the Kim–Barbulescu technique would define polynomials such as
\begin{array}{rcl}    h &=& x^3 + 2 \\    Py &=& y^2 + 1 \\    f &=& \mbox{Resultant}_y(x^2 + y, P_y) = x^4 + 1 \\    \varphi &=& x^2 + 920864572697168183284238230027 \\    g &=& 499692811133242\ x^2 - 1700558657645055 \\  \end{array}
In this case, the elements involved in the relation collection step are of the form (a_{0}+a_{1}\alpha_h+a_2\alpha_h^2) + (b_0+b_1\alpha_h + b_2\alpha_h)\alpha_f. They have six coefficients. in order to enumerate a set of same global size E^2 where E = 2^{30}, one takes \|a_i\|, \|b_i\| \leq E^{2/(t \deg h)} = 2^{10}. The norm of c = ({1018} + {1019} \alpha_h + {1020} \alpha_h^2) + ({1021} + {1022} \alpha_h + {1023} \alpha_h^2) \alpha_f is 135.6 bit long, the norm of d = ({1018} + {1019} \alpha_h + {1020} \alpha_h^2) + ({1021} + {1022} \alpha_h + {1023} \alpha_h^2) \alpha_g is 216.6 bit long, for a total of 352.2 bits. This is 92 bits less than the 444 bits obtained with the former JLSV technique.

Why the norm is smaller.

The norm computed in the number fields depends on the coefficient size and the degree of the polynomials defining the number fields, and on the degree and coefficient size of the element whose norm is computed.

With the Kim–Barbulescu technique, the norm is computed recursively from K_f to K_h then from K_h to \mathbb{Q}. The norm formula depends on the degree of the element and since this element is of degree 1 in K_f, its norm will be as low as possible. Then in K_h, the element is of degree (at most) \deg h -1 but this does not increase its norm since the coefficients of h are tiny (a norm bound is A^{\deg h} \|h\|_\infty^{\deg h -1}, and \|h\|_\infty^{\deg h -1} will be very small).

Why it changes the asymptotic complexity.

The asymptotic complexity is reduced (contrary to the Sarkar–Singh method) because the norm formula is reduced not only in practice but also in the asymptotic formula. To do so, the parameters should be tuned very tightly. In the large characteristic case, \kappa = n/\deg h should stay quite small: \kappa \leq \left(\frac{8}{3}\right)^{-1/3} \left( \frac{\log p^n}{\log\log p^n} \right)^{1/3}~. For p^n of 608 bits as in the \mathbb{F}_{p^6} example, the numerical value is \kappa \leq 2.967. Kim and Barbulescu took \kappa = 2. In fact, \kappa should be as small as possible, so that one can collect relations over elements of any degree in \alpha_h, but always degree 1 in \alpha_f. The smallest possible value is \kappa = 2 when n is even.

For the classical BN curve example where p^{12} is a 3072-bit prime power, the bound is \kappa \leq 4.705.

Special-NFS variant when p is given by a polynomial.

For prime fields where p has a special form, the Special-NFS algorithm may apply. Its complexity is L_{p}[1/3, (32/9)^{1/3} = 1.526]. For extension fields \mathbb{F}_{p^n}, where p is obtained by evaluating a polynomial of degree d at a given value, e.g. d=4 for BN curves, Joux and Pierrot [PAIRING:JouPie13] proposed a dedicated polynomial selection method such that the NFS algorithm has an exptected running-time of

  • L_{p^n}\left[1/3, \left(\frac{d+1}{d}\frac{64}{9}\right)^{1/3}\right] in medium characteristic, where p = L_{p^n}[\alpha_p, c_p] and 1/3 < \alpha_p < 2/3;
  • L_{p^n}\left[1/3, \left(\frac{32}{9}\right)^{1/3}\right] in large characteristic, where p = L_{p^n}[\alpha_p, c_p] and 2/3 < \alpha_p < 1 and moreover d satisfies d = \frac{1}{n} \left(\frac{2 \log p^n}{3 \log \log p^n} \right)^{1/3};
  • L_{p^n}\left[1/3, \left(\frac{32}{9}\right)^{1/3}\right] in prime fields and tiny extension degree fields, where p = L_{p^n}[1, c_p] and moreover d satisfies d = \frac{1}{n} \left(\frac{2 \log p^n}{3 \log \log p^n} \right)^{1/3}.

The Kim–barbulescu method combines the TNFS method and the Joux–Pierrot method to obtain a L_{p^n}[1/3, (32/9)^{1/3} = 1.526] asymptotic complexity in the medium-characteristic case.

Discussion on key-size update

This new attack reduces the asymptotic complexity of the NFS algorithm to compute DL in \mathbb{F}_{p^n}, which contains the target group of pairings. The recommended sizes of \mathbb{F}_{p^n} were computed assuming that the asymptotic complexity is L_{p^n}[1/3, 1.923]. Since the new complexity is below this bound, the key sizes should be enlarged. The smallest asymptotic complexity that Kim and Barbulescu obtain is for a combination of Extended-TNFS and Special-NFS. They obtain L_{p^n}[1/3, (32/9)^{1/3} = 1.526] when the prime p is given by a polynomial of degree d and when n is composite, n=\kappa \eta, and \eta satisfies an appropriate bound. In that case, it means that the size of \mathbb{F}_{p^n} should be roughly doubled asymptotically.

Comparison with NFS in prime fields \mathbb{F}_{p_1}.

In order to provide a first comparison of the expected running-time of the NFS algorithm in finite fields \mathbb{F}_{p^n} and prime fields \mathbb{F}_{p_1} of same total size, one can compare the size of the norms involved in the relation collection. We took the \mathbb{F}_{p^6} example of 608 bits (183 decimal digits), and consider a prime field of 608 bits for comparison. The Joux–Lercier method [MathComp:JouLer03] generates two polynomials f and g of degree d+1 and d and coefficient size \| f \|_\infty = O(1), \| g \|_\infty = O(p^{1/(d+1)}). We take d \approx \delta \left( \frac{\log p}{\log \log p} \right)^{1/3} , where \delta = 3^{1/3}/2. We obtain d = 2.95. We take d=2. The choice d=3 would end to slightly larger norms (5 to 10 bit larger).
The polynomials f and g would be of degree 3 and 2, and the coefficient size of g would be p^{1/3} of 203 bits. The bound E in the relation collection would be approximately \log_2 E \approx 1.1 (\log q)^{1/3} (\log \log q)^{2/3} (in theory L_p[1/3, \beta=(8/9)^{1/3}]) of 27.36 bits (cado-nfs) up to 30 bits (Kim–Barbulescu estimate). The norms of the elements would be d^2 E^{2d+1} p^{1/(d+1)} of 341 bits (\log_2 E = 27.36) to 354 bits (\log_2 E = 30). Kim and Barbulescu obtain a norm of 330 bits for \mathbb{F}_{p^6} [Example 1]. It means that computing a discrete logarithm in \mathbb{F}_{p^6} compared to \mathbb{F}_{p_1} both of 608 bits would be easier in \mathbb{F}_{p^6}.

We can do the same analysis for \mathbb{F}_{p^{12}} of 3072 bits and this starts to be a complete mess. The Joux–Lercier method for a prime field \mathbb{F}_{p1} of 3072 bits would take polynomials of degree d=4 and the norms would be of 1243 bits. The Kim–Barbulescu technique (ExTNFS) with Conjugation in \mathbb{F}_{p^{12}} of 3072 bits would involve norms of 696 bits in average. If moreover we consider a BN-prime given by a polynomial of degree 4, and take \eta=3 and \kappa = 4, the norms would be of 713 bits in average. This is also what [Fig. 3] shows: the cross-over point betweeen ExTNFS-Conj (of asymptotic complexity L_{p^n}[1/3, 1.92]) and Special ExTNFS (of asymptotic complexity L_{p^n}[1/3, 1.52]) is above 4250 bits.

Security level estimates and key-sizes.

[Edited May 3 thanks to P.S.L.M. B. comments]
What would be the actual security level of a BN curve with p of 256 bits and \mathbb{F}_{p^{12}} of 3072 bits? At the moment, the best attack would use a combination of Extended TNFS with the Joux–Pierrot polynomial selection for special primes, or the ExTNFS with Conjugation. We give in the following table a rough estimate of the improvement. Evaluating the asymptotic complexity L_{p^n}[1/3, c] for a given finite field size does no provide the number of bits of security but could give a (theoretical) hint on the improvements of the Kim–Barbulescu technique. This table can only say that the former 256-bit prime p BN curve should be changed into a 448 up to 512-bit prime p BN-curve.
This is a rough and theoretical estimate. This can only says that a new low bound on the size of BN-like \mathbb{F}_{p^{12}} to achieve a 128-bit security level would be at least 5376 bits (p of 448 bits).

[edited June 8th thanks to T. Kim comments. In the medium prime case, the best complexity of Extended TNFS is L_{p^n}[1/3, 1.74] when n is composite. ]
\begin{array}{|c|c|c|c|c|c|c|}  \hline \log_2 p &  n  & \log_2 q  & \begin{array}{@{}c@{}} \mbox{Joux--Pierrot NFS}\\ d=4, L_{p^n}[1/3, 2.07] \end{array}    & \begin{array}{@{}c@{}} \\ L_{p^n}[1/3, 1.92]  \end{array}    & \begin{array}{@{}c@{}} \mbox{Extended TNFS}\\ L_{p^n}[1/3, 1.74]  \end{array}     & \begin{array}{@{}c@{}} \mbox{Special Extended TNFS}\\ L_{p^n}[1/3, 1.53] \end{array} \\   \hline   256   &  12 &  3072   & \approx 2^{149-\delta_1} &  \approx 2^{139-\delta_2} & \approx 2^{126-\delta_3} & \approx 2^{110-\delta_4} \\  \hline   384   &  12 &  4608   & \approx 2^{177-\delta_1} &  \approx 2^{164-\delta_2} & \approx 2^{149-\delta_3} & \approx 2^{130-\delta_4} \\  \hline   448   &  12 &  5376   & \approx 2^{189-\delta_1} &  \approx 2^{175-\delta_2} & \approx 2^{159-\delta_3} & \approx 2^{139-\delta_4} \\  \hline   512   &  12 &  6144   & \approx 2^{199-\delta_1} &  \approx 2^{185-\delta_2} & \approx 2^{168-\delta_3} & \approx 2^{147-\delta_4} \\  \hline  \end{array}

To obtain a key size according to a security level, a value \delta_i is required, which is not known. The order of magnitude of this \delta_i is usually of a dozen. A 4608-bit field (corresponding for Barreto-Naehrig curves to p of 384 bits) might not be large enough to achieve a 128-bit security level.

Alternative choices of pairing-friendly curves.

Few days ago, Chatterjee, Menezes and Rodriguez-Henriquez proposed to use embedding degree one curves as a safe alternative for pairing-based cryptography. However in these constructions, the prime p is given by a polynomial of degree 2. It is not known what is the most secure: a prime field with p given by a polynomial of degree 2 or a supersingular curve with k=2 (or even a MNT curve with k=3).

Another way would be to use generic curves of embedding degree n=2 or n=3, generated with the Cocks-Pinch method, so that no one of the recent attacks can apply. In any case the pairing computation would be much less efficient than previously with the BN curves and p of 256 bits. Such low embedding degree curves were used at the beginning of pairing implementation, e.g. [CT-RSA:Scott05], [ICISC:ChaSarBar04].

Aurore Guillevic.

Posted in Uncategorized | 5 Comments

ECDLP in less than square-root time

As an apology for my “April Fool’s” blog post, I thought I would present a summary of what is known about algorithms for ECDLP that run in asymptotic time less than the square-root time of Pollard rho.

Let q = p^n and let E be an elliptic curve over \mathbb{F}_q. One can solve the ECDLP in E( \mathbb{F}_q ) in O( \sqrt{q} ) = O( p^{n/2} ) group operations. With large storage this is deterministic and rigorous (baby-step-giant-step algorithm), but requires O( \sqrt{q} ) = O( p^{n/2} ) group elements of storage. With Pollard rho the algorithm is randomised and the running time claim is heuristic and average-case, but the storage is low.

Can we do better?

The rest of this article lists some approaches that give ECDLP algorithms with running time better than O( \sqrt{q} ) group operations. None of these results are new, and most of them are very well known. None of them have any impact on currently used elliptic curve cryptosystems, so please do not panic. Full details and references can be found in a recent survey paper I wrote with Pierrick Gaudry.

  1. One can always “unbalance” the baby-step-giant-step algorithm. By using O(M) precomputation and storage one can solve an instance of the ECDLP in an “online” time of O( q/M ) group operations. For example, taking M = q^{2/3} we have an algorithm that solves each individual instance of the ECDLP in O( q^{1/3} ) group operations.

    This approach is usually completely impractical, especially due to the storage requirement. But the concept can make sense if one is going to be solving a very large number of instances of the ECDLP in the same (relatively small) group, and it demonstrates that the O( \sqrt{q} ) bound is not absolute.

  2. A similar idea can be done for Pollard rho. The precomputation is still enormous, but at least the storage stays small. Bernstein and Lange have analysed this approach (see the papers Computing small discrete logarithms faster and Non-uniform cracks in the concrete). Bernstein and Lange explain that with O( q^{2/3} ) precomputation one has can solve individual ECDLP instances in O( q^{1/3} ) group operations.

    Again, for practical applications this is not necessarily a serious concern. But in systems where many users work in the same group one should be careful to set security levels that take into account such a scenario (for example, recall the Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice paper, which has too many authors to write down here).

  3. Brown-Gallant and Cheon have considered variants of the ECDLP where one is given P, aP, a^dP where P is a point of order r and d \mid (r-1). (I assume that r \approx q.) They show one can solve this variant of the ECDLP (i.e., compute a) in O( \max\{ \sqrt{r/d}, \sqrt{d} \} ) group operations. Taking d \approx \sqrt{r} gives an algorithm with O( r^{1/4} ) group operations. There are also algorithms for the case when d \mid (r+1), but they need more intermediate group elements.

    These methods require that r \pm 1 has a factor of the appropriate size and that auxiliary points such as a^d P are available. Hence, these methods are not a threat to elliptic curve cryptosystems as presently used.

  4. Semaev introduced summation polynomials in 2004. Gaudry and Diem were quick to realise that they could be combined with Weil descent. Gaudry focussed on the case of E( \mathbb{F}_{p^n} ) where n is fixed and p goes to infinity. His approach, combined with a “double-large-prime” strategy leads to an algorithm with running time O( p^{2 - 2/n} ) operations (ignoring log terms). The constant in the running time depends exponentially (at least) in n.

    Taking n = 3 we have an algorithm with running time O( p^{1.333} ) operations, which is better than the O( p^{1.5} ) operations of Pollard rho, and the gap grows as n grows. Hence, it is well known that one can beat Pollard rho for curves over such fields, at least asymptotically. Due to this algorithm, elliptic curves E( \mathbb{F}_{p^n} ) for “intermediate” values of n are no longer used for elliptic curve cryptography.

    Returning to my recent hoax: Is there a O( q^{1/24} ) ECDLP algorithm? Yes indeed: When n \ge 47 then the running time of Gaudry’s algorithm on E( \mathbb{F}_{p^n} ) is asymptotically better than O( p^{n/24} ). But the constants are terrible and I am confident that no-one is ever going to perform an experiment of Gaudry’s algorithm in E( \mathbb{F}_{p^{47}} ) that beats Pollard rho. I also remark that such curves have never been suggested for ECC in practice.

    Diem showed an even stronger result: that there are families of finite fields \mathbb{F}_{p^n} for which the ECDLP is subexponential time. But there are no practical implications of this method to elliptic curve cryptosystems.

  5. Several recent papers have suggested improved results for ECDLP on elliptic curves over extension fields. These methods are all based on summation polynomials.

    The papers about ECDLP in characteristic two have been discussed in these two blog posts. These ideas potentially give some speedups to the summation polynomial algorithms, but there is currently little theoretical or experimental evidence to support these claims. The methods do not apply to elliptic curves over prime fields.

    Most recently, the paper Algebraic approaches for the Elliptic Curve Discrete Logarithm Problem over prime fields by Christophe Petit, Michiel Kosters and Ange Messeng was published at PKC 2016. This paper has some interesting and original ideas, and it does apply to elliptic curves over prime fields. But there seem to be no serious implications at present for the use of elliptic curves in practice. From a theoretical point of view, the method is unlikely to perform as well as the methods for characterstic 2 fields (of prime degree), and those methods have not been established yet to beat Pollard rho, so there is currently no evidence that the method in the PKC 2016 paper can beat Pollard rho either. Table 4 of the Petit-Kosters-Messeng paper reports on experiments: the new algorithm solves the ECDLP over a 22-bit finite field in around 5000 seconds, compared with Magma’s implementation of baby-step-giant-step which solves the same problem in 0.01 seconds.

— Steven Galbraith

Posted in Uncategorized | 1 Comment

ECDLP is not broken in 24-th root time

In case anyone has not figured it out, yesterday’s blog post was an April fool’s day hoax. The mathematical arguments written in the blog post make absolutely no sense at all.

Normal service is now resumed. Ellipticnews will continue to be the most reliable news source on the internet for information about new results on the ECDLP.

— Steven Galbraith, April 2 (New Zealand time)

Posted in Uncategorized | 1 Comment

ECDLP can be solved in 24-th root time

We report breaking news of an O( q^{1/24} ) time algorithm for the ECDLP in any elliptic curve E( F_q ). While still exponential complexity, this result will require a major increase in parameter for elliptic curve cryptosystems.

Full details are yet to be released, but the main idea is to exploit recent work by
Maryna Viazovska on sphere packings.

Her work on the 8-dimensional packing seems to lead to an O( q^{1/8} ) algorithm, which would already require a major change in elliptic curve key sizes. But her new joint work with Cohn, Kumar, Miller and Radchenko on sphere packings in dimension 24 gives a much stronger result. As a result we recommend increasing elliptic curve key sizes from 256 bits to 3072 bits.

The method is an index calculus approach. The factor base is chosen by combining two standard results:

  1. The connection between the elliptic curve discrete logarithm problem and the minimal distance of an elliptic codes, and sphere packings (see for example
    this blog post.

  2. The connection between minimal distances of codes and sphere packings.

The decomposition algorithm for the factor base therefore gets translated to a sphere packing problem in 24 dimensions, now solved by Viazovska and her collaborators.

More details to follow. Watch this space.

— Steven Galbraith, April 1, 2016.

Posted in Uncategorized | 2 Comments

eprint 2016/003 by Nicolas Courtois

Nicolas Courtois has posted the paper On Splitting a Point with Summation Polynomials in Binary Elliptic Curves on eprint. The original paper is from January 3rd, but it was updated on January 4 and again on January 5. Probably there will be further updates in the future.

The paper ends with the strong statement “Our conjecture is however that there exists an algorithm for solving the full DL problem on binary elliptic curves with running time of order of 2^{n/3}.”

The context of the paper is index calculus algorithms for the ECDLP. The basic problem in these algorithms is writing an arbitrary point R as a sum P_1 + \cdots + P_k of points that all lie in some “factor base”. This is sometimes called “splitting” a point or “decomposing” a point. The recent work in this area, as summarised in these blog posts, is based on Semaev’s summation polynomials, Weil descent, and Groebner basis algorithms. A problem with this approach is that it is very hard to determine the asymptotic running time of the Groebner basis algorithms, in part because the memory costs are enormous.

This idea does not apply to elliptic curves over prime fields \mathbb{F}_p, and the security of these curves is not affected by any work in this area. For elliptic curves over extension fields \mathbb{F}_{p^n}, for certain values of n, this approach can definitely lead to a faster algorithm than Pollard rho.
However one particularly awkward case is elliptic curves over \mathbb{F}_{2^n} where n is prime, and it is still an open question whether the ECDLP can be solved faster than Pollard rho for such curves. The situation was recently surveyed by Pierrick Gaudry and myself.

Rather than using Groebner basis methods, Nicolas Courtois considers a different approach to solving the point decomposition problem. His approach combines exhaustive search with solving linear equations. To demonstrate the applicability of this idea he gives methods to decompose points as a sum of 2 or 3 points. I have not had time to check the technical parts of the paper in detail yet, but the methods seem to be practical and do not require very large amounts of memory. This work gives insight into the potential for such techniques as part of an index calculus algorithm, and it will be very interesting to see how these ideas develop for decompositions into sums of 4 or more points.

The proposed decomposition algorithms all run in exponential time (e.g., 2^{n/3} steps). It is not immediately clear (to me anyway) that the problem of decomposing a point into a sum of 2 or 3 points should be hard. There is not a direct relationship between point decomposition and ECDLP. For example, if one is given an ECDLP oracle then I don’t see how to use it to solve point decomposition efficiently. So ECDLP could be easy and yet point decomposition hard. On the other hand, decomposing a point as a sum of two points in a factor base of size 2^{n/2} could be polynomial-time and yet, due to the size of the factor base and the cost of the linear algebra stage, the index calculus algorithm would still be slower than Pollard rho.

The paper makes two claims as a consequence of the decomposition algorithms:

  1. Violation of the ideal group model for binary curves.

    The author suggests that his results already show that elliptic curves do not behave like “ideal groups”. In my opinion, it is unclear how to formalise the point decomposition problem in terms of generic algorithms. I tend to think of the generic group model as a “representation independent” model. A generic algorithm has access to group operations and nothing more. A factor base is not a “generic” object, as it depends on the representation. So I am not sure that this comment really has any meaning.

  2. Conjecture of a cube-root-time algorithm for ECDLP on binary elliptic curves.

    It would be very interesting if this claim is true, and I look forward to the future research on this topic. It is certainly an important and interesting problem to consider new approaches to the point decomposition problem.

    At the moment however, there is no evidence to support the claim. The January 5 version of the paper has three decomposition methods.
    The first decomposes to points in a factor base of size 2^{n/2} and so an index calculus algorithm based on this method would have storage cost proportional to 2^{n/2} and be slower than baby-step-giant-step and Pollard rho.
    The second method decomposes in time O( 2^{n/3} ) into a sum of three points in a factor base of size 2^{n/3}. Since we need O( 2^{n/3} ) relations we need to perform the decomposition method O( 2^{n/3} ) times, giving a total complexity of O( 2^{2n/3} ) to solve an instance of the ECDLP, which is worse than Pollard rho.
    The final proposal is an algorithm to decompose a point as a sum of two points in a factor base of size 2^{n/3} and again the decomposition takes time O( 2^{n/3} ), giving an algorithm to solve ECDLP with time O( 2^{2n/3} ).

I conclude by re-stating that it is an important and interesting problem to consider algorithms for the point decomposition problem that are not based on Groebner basis method. The new ideas by Courtois are to be welcomed, and I look forward to future work on this problem.

— Steven Galbraith

Posted in Uncategorized | 1 Comment