ECC 2018, Osaka, Japan

As announced earlier on this blog, the 22nd Workshop on Elliptic Curve Cryptography took place at Osaka University, Japan, from November 19 to 21. This edition featured invited talks across a broad range of topics, from quantum information theory to homomorphic encryption to blockchains. As for elliptic curves specifically, the highlight was clearly isogeny-based crypto, explored in four different talks:

* David Jao discussed a number of techniques (from various authors) to achieve faster embedded implementations of SIDH, both in software using either vector instructions (like ARM NEON) or dedicated coprocessors, and on reconfigurable hardware. The talk was presented as a response to a recent paper by Koppermann et al. which had rather pessimistic conclusions regarding the usability of SIDH on smaller devices, mentioning 18 seconds as its headline timing for key exchange on 32-bit microcontrollers. David Jao argued that suitably optimized implementations could in fact do much better.

* Travis Morrison discussed some of his recent results (joint work with Eisenträger, Hallgren, Lauter and Petit) regarding the relationship between two computational problems connected to supersingular elliptic curves, namely pathfinding in the \ell-isogeny graph of supersingular elliptic curves over some \mathbb{F}_{p^2} (with \ell = O(\log p)) and the problem of computing the endomorphism ring of a supersingular elliptic curve. The main takeaway is that, assuming some heuristics, the two problems are polynomial-time equivalent.

* Chloe Martindale gave an excellent introduction to CSIDH (joint work with Wouter Castryck, Tanja Lange, Lorenz Panny and Joost Renes), which is a new instantiation of Couveignes-style hard homogeneous spaces using isogenies of supersingular elliptic curves over \mathbb{F}_p (as opposed to \mathbb{F}_{p^2}), which satisfy that the ring of rational endomorphisms is commutative. This provides a nice group action similar to the case of ordinary curves, but makes it possible to choose parameters in such a way that \ell-isogenies for many small primes \ell can be computed efficiently. This leads to a variant of the Couveignes-Rostovtsev-Stolbunov key exchange protocol that outperforms the original one by many orders of magnitude, achieving performance on the order of a few dozen milliseconds per key exchange.

* Finally, Katsuyuki Takashima discussed new isogeny-based authenticated key exchange protocols (joint work with Atsushi Fujioka and Kazuki Yoneyama). He showed how to obtain a one-round authenticated key exchange protocol using commutative group actions on isogeny graph. Assuming the existence of n-way cryptographic invariant maps, as suggested by Boneh et al., the protocol can be instantiated for an arbitrary number of parties. Unfortunately, it is not yet known how to construct such invariant maps (and as one of the culprits, I have to admit that the prospects of constructing them look rather remote). However, the two-party case only relies on Couveignes’s hard homogeneous spaces, and can thus be obtained from CRS or CSIDH.

There were many other excellent talks at the workshop, but some of them were not closely related to elliptic curves and so we don’t discuss them on this blog. Of particular notice besides isogenies was Pierrick Gaudry’s presentation on point counting in higher genus (joint work with Simon Abelard and Pierre-Jean Spaenlehauer). He showed how to compute the zeta function of a hyperelliptic curve of genus g over \mathbb{F}_q in time O_g((\log q)^{O(g)}), greatly improving upon the previous complexity, with an exponent quasi-quadratic in g. He also discussed concrete results for g=3, establishing that the correct complexity was (\log q)^{14} for general hyperelliptic curves, and (\log q)^{6} for Jacobians with real mutiplication. In the latter case, the complexity becomes tractable even for cryptographic sizes, and Pierrick was able to show us the whole zeta function for a curve over \mathbb{F}_p with p=2^{64} - 59.

— Mehdi Tibouchi

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