ASIACRYPT 2013, Bangalore

What do you mean when you say

“…assuming there exists no algorithm that can solve the ECDLP in fewer than O(N^{1/2}) steps…”?

A quick survey of the people around me during Dan Bernstein and Tanja Lange’s “Non-Uniform Cracks in the Concrete” talk at ASIACRYPT suggested that most people were sure they knew what they mean—and they’re pretty sure they knew what anyone else who writes this kind of thing means, too.  Maybe that’s the problem.  To give a ridiculously oversimplified sketch of the idea: Everyone knows (or should know) that there exist faster algorithms, but they take longer to write down/precompute.  For example, the statement above is strictly false: for any group G of prime order N, given O(N^{2/3}) steps of precomputation, you can compute an algorithm that will solve DLP instances in G in O(N^{1/3}) steps.  On one hand, this renders some theorems in the literature false, because they make careless assumptions (which could, presumably, be easily fixed).  But on the other hand, you might think you still know what you mean—it all depends on your model of computation.  If you want to check, there’s now a choice: the 53-page full version (free) or the 20-page conference version (paywalled).  This paper caused a bit of a stir back when it first appeared, but a year and a half later the controversy has mostly cooled down; it was nice to be able to have a few civilised chats about it at a well-organised conference (with rather good food).

The last twelve months has seen a curious new wave of papers about scalar multiplication on elliptic curves using efficiently computable endomorphisms, following on from the Gallant–Lambert–Vanstone and Galbraith–Lin–Scott constructions.  This year’s ASIACRYPT had two papers on the subject.  Sorina Ionica presented her joint work with Aurore Guillevic, which gave a generalization of Patrick Longa and Francesco Sica’s four-dimensional GLV+GLS construction presented at ASIACYRPT last year, viewed on both elliptic curves and genus 2 curves (via the Weil restriction).  The other paper was mine; it deals with the problem of constructing twist-secure elliptic curves with two-dimensional scalar decompositions over the fastest finite fields (this is basically just the minimal modification of GLS required to get twist-security). 

The rump session had a number of interesting results for curvists. Nadia Heninger presented joint work with Joppe Bos, Alex Halderman, Jonathan Moore, Michael Naehrig, and Eric Wustrow, which surveys how ECC is actually used in practice on the web today.  You’ll find a lot of interesting (and cute, and occasionally worrying) facts in the slides and the preprint.  We also saw some advertising for a range of projects involving Dan Bernstein and Tanja Lange: Elligator (encoding bitstrings into elliptic curve points, with Anna Krasnova and Mike Hamburg), MinimaLT (a fast replacement for TLS and TCP, with Michael Petullo, Xu Zhang, and Jon Solworth), and the safecurves page.

–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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s