Soliloquy, ideal lattices, and algorithms

This post is not about elliptic curve cryptography, but I think some readers will be interested in the issue. The topic is cryptosystems based on ideal lattices, and in particular the recent “Soliloquy” paper from GCHQ. Two recent blog posts are worth reading:

Dan Bernstein has written a blog post that fleshes-out some of the details. In the comments there is an extensive response by Chris Peikert and also some further discussion.

Chris Peikert’s response can also be accessed directly here.

My impression is that the ideas used by GCHQ do not threaten NTRU or Ring-LWE. But it is certainly good to see these algorithmic ideas documented. One of the drawbacks of our publication model is that “failed ideas” do not get written up and shared. Instead, the ideas become known to experts and considered as “folklore”. It is of value to the global research community to disseminate ideas more widely.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

EUROCRYPT 2015 accepted papers

The list of accepted papers to Eurocrypt is now up. There are several papers about discrete logarithms, as well as notable papers about multilinear maps and homomorphic encryption. There has never been a better time to visit Bulgaria!

— Steven Galbraith

Posted in Uncategorized | Leave a comment

New 113-bit ECDLP record

Erich Wenger and Paul Wolfger have just announced on NMBRTHRY a new ECDLP record computation.

The curve is over the field GF( 2^{113} ) and is not a Koblitz/subfield curve. So there is no speedup to Pollard rho from using equivalence classes under Frobenius. The number of points on the curve is 2 \cdot 5192296858534827689835882578830703 where the second number is a 112-bit prime.

No details of the computation are yet public, apart from the fact that 10 FPGAs were used. However, I presume the details will be similar to the SAC 2014 paper by the same authors. That paper was reporting on an ECDLP computation for a subfield curve, which was a significantly easier computation.

This result is not surprising, and does not change our opinions on the difficulty of the ECDLP, but it is always great to see computations of this type being performed.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Standardising specific elliptic curves

There is considerable ongoing discussion by standardisation committees about precisely which elliptic curves should be specified in crypto standards. One point of view on the merits of different choices is presented on the safe curves webpage, of Bernstein and Lange. These views are not unanimously held. The IETF discussions can be found here.

NIST will be holding a workshop in June 2015 to discuss these questions further.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Asiacrypt 2014, Kaohsiung, Taiwan

Asiacrypt 2014 was held in Kaohsiung, Taiwan on December 7-11 2014.  There were 55 accepted papers, a very high number indeed. A good number of these papers are of interest to researchers in curves.

The conference began with the best paper Solving LPN using covering codes, presented by Qian Guo and joint work with Thomas Johansson and Carl Londahl. Here “LPN” means the “learning parity with noise” problem, which is somewhat related to the problem of decoding a random linear code over GF(2). LPN is also related to learning with errors. The paper is about the Blum-Kalai-Wasserman algorithm, and introduces covering codes in the final stage of the algorithm to reduce the size of an “exhaustive search” operation.

The next talk was Algebraic attack against variants of McEliece with Goppa polynomial of a special form by Jean-Charles Faugere, Ludovic Perret and Frederic de Portzamparc. This paper is about a “structural attack” on special McEliece keys using Groebner basis algorithms.

The paper Bivariate polynomials modulo composites and their applications by Dan Boneh and Henry Corrigan-Gibbs uses some very nice mathematics. The paper proposes to use the function f(x,y) = x^7 + 3 y^7 \mod{N}, where N is an RSA modulus, as a commitment scheme in place of traditional Pedersen commitments C(m,r) = g^m h^r. The idea that f(x,y) is a collision-resistent hash function comes from a conjecture by Don Zagier that x^7 + 3 y^7 defines an injective function \mathbb{Q}^2 \to \mathbb{Q}. The paper refers to some nice mathematics from number theory and algebraic geometry, and Henry gave a very clear talk.

Mehdi Tibouchi presented the paper GLV/GLS decomposition, power analysis and attacks on ECDSA signatures with single-bit nonce bias, with too many co-authors for me to type. It is a very interesting paper with many contributions. First, the authors study a technique due to Bleichenbacher for learning the secret key by exploiting a bias in the random nonce in ECDSA signatures (it also applies to other signature schemes such as Schorrr, ElGamal etc). This technique uses the inverse Fast Fourier Transform. They show that these ideas do lead to an attack on ECDSA signatures, though the cost is too high to be demonstrated using current computing power. Next the paper considers GLV/GLS methods for computing [k]P = [k_1]P + [k_2]\psi(P) in ECDSA, where \psi is the GLV/GLS endomorphism satisfying \psi(P) = [\lambda]P for some large integer \lambda. The paper discusses three natural approaches to compute (k_1,k_2): (1) Choose uniform k and decompose; (2) Choose k_1,k_2 uniformly in [0, 2^m) for suitable m; (3) in the case when \lambda^2 + 1 \equiv 0 \mod{n}, where n is the order of the point P, to choose k_1, k_2 uniformly in [0, \sqrt{n}). One might naively assume that all three methods are fine. But there are surprises in store! The paper shows that: (1) is vulnerable to a side-channel attack; (2) is broken by Bleichenbacher’s attack (and this can be done in practice in reasonable time); (3) is provably secure.

The next morning began with a session of three talks on elliptic and hyperelliptic curves.

Christophe Doche presented his paper On the enumeration of double-base chains with applications to elliptic curve cryptography. The idea of double-base chains is to exploit curves that have both efficient doubling and tripling operations, and to try to minimise the number of general additions. One can represent an integer k as a chain 2^{a_1} 3^{b_1} \pm 2^{a_2} 3^{b_2} \pm \cdots \pm 2^{a_l} 3^{b_l} where a_i \mid a_{i+1} and b_i \mid b_{i+1}. When this is done, the cost of computing [k]P is then a_l doubles, b_l triples, and (l-1) general additions. The fundamental problem is to find a double-base chain that gives the fastest computation of [k]P. It seems to be hard to find such a chain efficiently. Instead, one can generate a “random” integer k by generating a random double-base chain. The paper gives new methods to count the number of double-base chains for a given triple (l, a_l, b_l) and hence to get an idea of what values are required to cover all (or almost all) possible integers k. An interesting future question is to consider the issues discussed by Mehdi Tibouchi in this setting.

Chitchanok Chuengsatiansup presented joint work with Daniel J. Bernstein, Tanja Lange and Peter Schwabe on Kummer strikes back: new DH speed records. The goal is to study Kummer surface arithmetic for variable-base divisor multiplication. It turns out that the Montgomery ladder when using Kummer surface arithmetic is very suitable for 4-way vectorisation. Hence, an implementation can be done that breaks previous cycle-count records.

Huseyin Hisil presented the paper Jacobian coordinates on genus 2 curves. This joint work with Craig Costello presents beautiful new formula for divisor arithmetic on genus 2 curves. It is very surprising to me that these formulae had not been discovered before. The new formulae lead to significant speedups when performing arithmetic in the divisor class group of general curves. Of course, for many applications it is better to use Kummer surface formula (as in the previous talk), but I am sure there will be situations where the new formula are useful.

The next session, while not about curves, was of interest to this community. Rob Granger presented the paper Mersenne factorization factory, as none of the authors were able to attend. The paper is about factorising a collection of special integers of the form 2^m - 1 using the special number field sieve. The idea is to use the same sieving for one side of the algorithm, giving an overall speedup. More generally, the paper analyses situations where one could try to factor a collection of RSA moduli simultaneously. The other paper, presented by Cecile Pierrot, was joint work with Antoine Joux on finite field discrete logarithms. The paper gives some new techniques for computing discrete logs of low degree elements. The complexity of the first stage becomes O( q^6 ). The talk reported a new record-breaking computation of discrete logarithms in GF( 3^{5 \cdot 479}), which is reported in the full version of the paper here. That computation takes q = 3^5. For pairing applications one would take q = 3^6, which would give a DLP computation approximately 3^6 times slower than the record reported. This confirms that pairings using supersingular elliptic curves in characteristic 3 are not a good choice for pairing-based cryptography.

The first invited talk, by Kenny Paterson, was on Big bias hunting in Amazonia: Large-scale computation and exploitation of RC4 biases. The talk was extremely clear and well-presented. Kenny explained how RC4 biases can be exploited to obtain some realistic and significant attacks on real-world protocols. One theme of his talk was that cryptographers should try to pay more attention to what is going on in the real world, as they can make important contributions. Another was that it is difficult to bring change in the real world: “Things won’t change until you present an engineer with their password”. One can find a longer report on this lecture at the Bristol crypto blog.

Chrysanthi Mavromati presented the paper Multi-user collisions: Applications to discrete logarithms, Even-Mansour and PRINCE, which is joint work with Pierre-Alain Fouque and Antoine Joux. One of the results in the paper is a new approach to solve L discrete logarithm instances using Pollard rho in a group of size N in O( \sqrt{LN} ) group operations. Such a complexity has been previously obtained by Kuhn-Struik and Bernstein-Lange, but the new result achieves this is a slightly different way. The paper is mostly about applying similar ideas in the case of the Even-Mansour block cipher.

Nils Fleischhacker presented a paper On tight security proofs for Schnorr signatures, which continues a line of work on meta-reductions. The fundamental problem is that the security of Schnorr signatures (and many other signature schemes) is proved using the forking lemma, and so proofs are not tight. Results based on meta-reductions are intended to explain why one cannot get around this problem. Luckily it is known that there are signature schemes with tight security reductions, but they are based on other computational problems like CDH or DDH.

The rump session lacked talks on ECC, and beer.

The second invited talk was by Helaine Leggat, who is an information security lawyer in Australia. Her talk was The legal infrastructure around information security in Asia and she discussed, among other things, the processes by which nation states develop their own national laws on information security. She highlighted several different issues surrounding surveillance, including governments spying on their citizens and companies spying on their employees/contractors. She predicts “There will be a fight between states and what technology can provide”. For more thoughts on her talk see the Bristol crypto blog. Her notes and references for this talk will eventually appear on the conference webpage.

At the elaborate and extensive Chinese banquet, awards were given for the best paper and Antoine Joux was inducted as an IACR fellow.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

ECC 2014, Chennai

The 14th Elliptic Curve Cryptography workshop was held last week at the Institute of Mathematical Sciences in Chennai, India. Of the five ECC workshops I’ve attended, this one had by far the best food (sorry, France). But it also had some good talks:

Razvan Barbulescu gave a nice talk on his now-famous quasi-polynomial algorithm for discrete logarithms in small-characteristic finite fields (his Eurocrypt 2014 paper with Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé). Razvan does a very good job of making this stuff accessible, and it’s always nice to hear the word GIPS-year in a talk (try saying it aloud to yourself).

Jens Zumbrägel spoke about computing discrete logarithms in the sorts of fields associated with pairings on supersingular binary curves, at what was formerly supposed to be the 128-bit security level (this was a Crypto 2014 paper with Thorsten Kleinjung and Rob Granger). Their project computed one discrete logarithm, and gives an estimated time for completing another one; this is another substantial nail in the coffin of small characteristic curves and pairings.

Ruben Niederhagen gave a really nice talk about the history (and practical exploitation of) the standardized backdoor in the DualEC random number generator, which was detailed in his USENIX 2014 paper with Stephen Checkaway, Matthew Fredrikson, Matthew Green, Tanja Lange, Thomas Ristenpart, Daniel J. Bernstein, Jake Maskiewicz, and Hovav Shacham.

Guénaël Renault gave a nicely detailed presentation on a technique which exploits torsion points and torsion structures to speed up index calculus on elliptic curves. The details are in a joint paper with Jean-Charles Faugère, Louise Huot, and Pierrick Gaudry.

Huseyin Hisil spoke about a fast implementation of endomorphism-accelerated scalar multiplication designed to implement Diffie-Hellman at the 128-bit security level (this is the subject of a joint paper with Craig Costello and myself, which was presented at Eurocrypt 2014). He also gave some tips for incomplete reduction techniques (in Intel assembly) for arithmetic modulo (pseudo-)Mersenne primes.

Elisa Gorla explained her joint work with Maike Massierer on index calculus in trace-zero subvarieties of elliptic curves defined over subfields. If you have a curve E over \mathbb{F}_p, then for every extension \mathbb{F}_{p^n}/\mathbb{F}_p you have a trace map E(\mathbb{F}_{p^n}) \to E(\mathbb{F}_p), mapping P to the sum of its p-power conjugates, and this map has a kernel T_n. This talk was about solving DLP instances via index calculus in that subgroup. The trace zero variety has been out of fashion in cryptography for some time now, but it’s still fun (for a certain value of fun) and instructive to play with; there is a lot more detail on this in Maike Massierer’s thesis.

Emmanuel Thomé spoke about his Igusa class polynomial computations (with Andreas Enge). Their results, using complex approximations and Borcherds means, essentially complete the approach set out in Regis Dupont’s thesis.

Yuval Yarom spoke about his CHES 2014 paper with Naomi Benger (who’s now a meteorologist!), Joop van der Pol, and Nigel Smart: they got some really nice side channel results using the Flush+Load attack on OpenSSL ECDSA signatures on the bitcoin curve.

Craig Costello spoke about curve parameter standardization in general, covering curve arithmetic and the huge number of choices to be made, and Microsoft’s NUMS curves in particular (which are described in his joint work with Joppe Bos, Patrick Longa , and Michael Naehrig). The NUMS curves are Microsoft’s contribution to the current debate on new, post-BULLRUN curve standards for ECC; you can download their library implementing these curves here.

The disembodied voice of Eric Wustrow presented a nice empirical survey of how ECC is currently deployed on the internet (his body, which had had visa problems, was asleep on another continent). This was a summary of his Financial Crypto 2014 work with Nadia Heninger, Joppe Bos, Alex Halderman, and Jonathan Moore.

Damien Robert reported on his recent joint work with David Lubicz, on computing pairings on abelian varieties. This talk was relatively technical, even by Damien’s standards (at one point he said it was time to move away from the abstract and get on to some concrete stuff: “Let A be a principally polarized abelian variety…”) But if you’re not afraid of duality, then you’ll find some good stuff in their paper that really could be used in concrete, fast implementations.

Erich Wenger spoke about his new record ECDLP computation (with Paul Wolfger, presented at SAC 2014): a 113-bit binary koblitz curve DLP instance. They have actually done it. They used basic parallelized Pollard rho, without negation maps and other frills, on a cluster of borrowed FPGAs (apparently with a lo-fi cooling system consisting of a couple of desk fans). If they had had access to all 18 of the FPGAs all of the time, then the computation would have taken 24 days—but then buying 18 of your own FPGAs to dedicate to the same kind of project amounts to about 45KUSD (the desk fans are much cheaper, I suppose). The actual budget for their project was 20USD worth of chocolate. Erich gave a series of estimations in terms of dollar and day costs, etc., for bigger challenge curves: he thinks think that if they had a billion USD and 190K days, then they could solve ECC2-163. Though I think that if they had a billion USD then they would probably do something else first. Possibly buying a lot more chocolate.

As is traditional at ECC workshops, there were some talks on cryptographic results from outside the domain. This time around, Mridul Nandi gave a survey talk on authenticated encryption, and Palash Sarkar gave a talk on symmetric broadcast encryption techniques.

Next year’s ECC workshop will be held in Bordeaux, France. I think most people expect that they will have by far the best wine for an ECC; let’s hope they can keep up the good talks, too.

–Ben Smith

Posted in Uncategorized | Leave a comment

Day Two of ANTS 2014

The Eleventh Algorithmic Number Theory Symposium took place in rainy GyeongJu, Korea on August 6-11, 2014. The proceedings are available online in the open access LMS Journal of Computation and Mathematics.

The first day contained a number of excellent lectures, but none direct relevant to elliptic curve cryptography. Unfortunately one talk was not given (and another talk was given by a substitute speaker).

Day two of the conference contained all the papers about the discrete logarithm problem.

The morning began with Antoine Joux‘s invited lecture “The discrete logarithm problem in small characteristic finite fields”. The talk began with a general survey of generic DLP algorithms and index calculus methods. He then moved on to discuss the recent work for the DLP in \mathbb{F}_{p^k} for small p and large k. First he explained the general approach, going back to Joux-Lercier (EUROCRYPT 2006) for the “medium-prime case”, of choosing two polynomials f_1(X) and f_2(X) in \mathbb{F}_p[X] of degrees d_1, d_2 respectively, such that f_1( f_2(X)) - X has an irreducible factor of degree k. One then uses a certain diagram of rings to develop an algorithm relying on some heuristics. Antoine explained a case where the heuristics badly fail, and noted that this leads to the greatly improved algorithms in small characteristic.

He then introduced a new and simplified approach to the algorithm, which avoids extending the field (previous approaches took a quadratic or cubic extension for the coefficients of the “homographies”). We explain this approach now.

We are interested in the DLP in \mathbb{F}_{q^k}^*. Let I(X) \in \mathbb{F}_q[X] be an irreducible polynomial of degree k that divides h_1(X^q)X - h_0(X^q), where \deg( h_1(X)), \deg( h_0(X) ) \leq H. Write \mathbb{F}_{q^k} = \mathbb{F}_q[\theta] where \theta is a roots of I(X). The key equation is (1) X^q - X = \prod_{\alpha \in \mathbb{F}_q} (X - \alpha). Choose integer D and set factor base to be polynomials over \mathbb{F}_q in variable \theta of degree \leq D. Let A, B also be polynomials over \mathbb{F}_q in variable \theta of degree \leq D. Substituting A(\theta)/B(\theta) into equation (1) (this is the alternative to using homographies) and doing standard algebra gives B(\theta) \prod_{\alpha \in \mathbb{F}_q} (A(\theta) - \alpha B(\theta) ) = B(\theta) A( h_0(\theta)/h_1(\theta) ) - A(\theta) B(  h_0(\theta)/h_1(\theta) ). The LHS of the equation splits over the factor base. Antoine introduces new notation [ A, B]_D so that the RHS of the equation is [A, B]_D(\theta)/ h_1(\theta)^D. If the numerator of the RHS splits over the factor base then we have a relation. He gives several properties of the polynomial/symbol [ A, B]_D. He then argues that D = 3 is the smallest choice for D for which one can expect to compute enough relations this way. He concludes that the running time of the first stage of the algorithm (to compute the discrete logarithm of everything in the factor base with respect to some single element in the factor base) is O( q^7 ) field operations in \mathbb{F}_q.
The remainder of his talk surveyed four descent strategies and explained how they are all combined to give the full algorithm.

The next talk was “The discrete logarithm problem for exponents of bounded height” presented by Sam Scott (joint work with Simon Blackburn). The paper is about the DLP instance: Given (g,h,n) to find integers 1 \leq a, b < n such that g^a = h^b, when n is much smaller than the order of g. This problem arises when one tries to trace transactions made using a proposed protocol by EMV (Mastercard/Visa) for card payments. (The standard attempts to make such transactions un-traceable in the sense that it is hard for an eavesdropper to "link" two different transactions made using the same card). The algorithmic content is to use the Gaudry-Schost algorithm for this problem, to get a low-storage algorithm that performs O( n ) group operations. The EMV standard proposed n=32, but this has been increased in response to the attack in this paper. Nevertheless, it is interesting that next-generation card payments will be protected by 256-bit elliptic curve cryptography.

Third talk of the session was "Constructing Abelian Surfaces for Cryptography via Rosenhain Invariants" by Kristin Lauter (joint work with Craig Costello, Alyson Deines-Schartz and Tonghai Yang). The paper is about constructing genus 2 curves using the CM method. Almost all previous work has used Igusa invariants and hence Mestre’s algorithm. The paper notes that using Rosenhain invariants is much simpler, and that the penalty that the class polynomials have higher degree is not necessarily a major problem in practice. Kristin also talked about how this method can give Kummer surface equations with relatively small constants, and expressed her philosophy that number theorists should be more engaged in applied subjects like cryptography, not only because the applications are important but also that these subjects can be a rich source of interesting theoretical questions.

Next was “Hyper-and-elliptic-curve cryptography” by Dan Bernstein. Dan, the sweet gentle soul that he is, gave an emotional appeal on behalf of a polar bear named “Fluffy” that we should try to use less energy by using more efficient crypto. This led to a discussion of Kummer surfaces and Edwards curves. The mathematical content was an explanation of a construction due to Scholten of genus 2 curves whose Jacobians are isogenous to the Weil restriction of Edwards curves. Dan explained how one can construct examples where the Kummer surface of the genus 2 Jacobian has an equation with small coefficients, and how one can efficiently pass between Edwards curve and Kummer surface representations of the same group. He was warmly thanked (globally) on behalf of Fluffy.

After lunch, Christophe Petit spoke about “Finding Roots in \mathbb{F}_{p^n} with the Successive Resultants Algorithm”. This is a new approach to factoring polynomials over finite fields of small characteristic. It does not provide a major speed-up for present applications, but is being suggested in the hope that it can lead to a new approach to finding solutions of a special form to multivariate polynomial equations.

Next Qi Cheng spoke on “Traps to the BGJT-Algorithm for Discrete Logarithms” (joint work with Daqing Wan and Jincheng Zhuang). The paper aims to reduce the number of heuristics in the quasi-polynomial-time algorithm for the DLP in finite fields of small characteristic. Note that there are several avenues to approach these isses, for example as discussed in Rob Granger’s talk at the Ascona DLP workshop.

Cecile Pierrot presented “The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields” (joint work with Razvan Barbulescu). This takes ideas of Coppersmith and Matyukhin for the number field sieve and applies them to a more general class of finite fields. These ideas lead to complexity improvements for the DLP in finite fields.

In the evening there was a poster session, followed by a “business meeting” that decided that ANTS 2016 should take place in (Bordeaux or Kaiserslautern) but failed to give a full solution to the problem.

The conference continues, but the talks are mainly on topics unrelated to elliptic curve cryptography. On Monday there will be a talk by David Kohel on the paper “On the quaternion l-isogeny path problem” with Kristin Lauter, Christophe Petit and Jean-Pierre Tignol. This paper is relevant to isogenies on supersingular elliptic curves and the Charles-Goren-Lauter hash function.

— Steven Galbraith

Posted in Uncategorized | Leave a comment