Eurocrypt 2018

This week Eurocrypt 2018 took place in Tel Aviv, in a hotel next to the marvellous beach. Despite the splendid weather and the tempting conference gift (a bath towel — that’s letting the fox into the hen house), there were many reasons to stay inside, thanks to the nice line up of speakers and the flawless organization. To name one highlight, Matthew Green’s invited talk on “Thirty years of digital currency: from DigiCash to Bitcoin” was particularly enjoyable. And so was the hummus, by the way!

Elliptic curves were a bit underrepresented though, with only one session talk explicitly devoted to them. Christophe Petit spoke about “Supersingular isogeny graphs and endomorphism rings: reductions and solutions”, which arose as a merge of a paper by him and Kristin Lauter and a paper by Kirsten Eisenträger, Sean Hallgren and Travis Morrison. In his talk, Christophe mainly focused on the security of the Charles-Goren-Lauter (CGL) hash function, which is based on the hardness of finding a cycle in the ell-isogeny graph (typically ell = 2) of supersingular elliptic curves over a large quadratic finite field \mathbb{F}_{p^2}. He related the security of the CGL hash function to the problem of computing the endomorphism ring of a given supersingular elliptic curve (while removing some ambiguity on what is meant by this) and to the problem of making Deuring’s correspondence effective. The most interesting outcome is a polynomial-time collision algorithm in case the initial curve is “special”, i.e., if it has a well-known endormorphism ring. This is worrisome, because it is an open problem how to generate a genuinely random “non-special” supersingular elliptic curve over \mathbb{F}_{p^2}, so this potentially opens the door to backdoored versions of the CGL hash function.

Other talks of relevance to ECC included:

  • Henry Corrigan-Gibbs gave a nice talk on the discrete logarithm problem (DLP) in general, reporting on a paper that he wrote together with Dmitry Kogan, which won the best young research award. He recalled that a massive preprocessing phase can reduce the hardness of the DLP in a generic group G of order N from O(N^{1/2}) to O(N^{1/3}). Their contribution is a Shoup-type result stating that this is optimal in the generic group model. Interestingly, they also reveal a dichotomy with the decisional Diffie-Hellman problem, in that they provide an O(N^{1/5}) algorithm for distinguishing triples of the form (g, g^x, g^{(x^2)}) from random triples in G^3, again using a very large amount of preprocessing.
  • Another interesting talk was given by Yilei Chen on joint work with Ran Canetti, Leonid Reyzin and Ron Rothblum, on the Fiat-Shamir transformation of a three-round public-coin identification scheme into a one-round digital signature scheme. He saw an analogy with transforming an elaborate USA-style conversation into a brief no-nonsense Israeli one. Chen and his coauthors constructed two families of so-called “correlation-intractable” hash functions, one of which uses elliptic curves. If you want to obtain a provably secure digital signature scheme from a hash function through Fiat-Shamir, then correlation intractability is the property you want.
  • In the rump session I gave a short talk about CSIDH, a compact non-interactive key exchange protocol designed together with Tanja Lange, Chloe Martindale, Lorenz Panny and Joost Renes. It is obtained by applying the Couveignes-Rostovtsev-Stolbunov scheme to the set of supersingular elliptic curves over a large prime field \mathbb{F}_p, rather than to ordinary elliptic curves. This choice was motivated by recent work of Luca De Feo, Jean Kieffer and Ben Smith on speeding up the ordinary Couveignes-Rostovtsev-Stolbunov scheme: one of their proposed speed-ups works particularly well in the supersingular setting.

All slides can (or will) be found on the conference web page, see

— Wouter Castryck

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