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

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s