Isogeny crypto at PQCrypto 2018

The PQ Crypto conference took place in sunny Fort Lauderdale, Florida in April 2018. It was extremely well attended (around 350 participants).

The three plenary lectures were:

• Jean-Pierre Tillich, Attacks in code based cryptography: a survey, new results and open problems.

The talk surveyed code-based crypto (both within the NIST submissions, and over its entire history) and various types of attacks.

• Dave Wecker, Achieving practical quantum computing.

The talk gave a wide-ranging overview of the potential applications of quantum computing (especially in modelling for quantum chemistry), the engineering challenges of building a quantum computer (with focus on practical concerns such as cooling and the interface between classical computing control systems and the quantum system), and the work being done globally by Microsoft research. Dave predicts that Microsoft will have a quantum computer suitable for chemistry applications within 5 years and “something of interest to this crowd” in 10 years.

• Dustin Moody, Let’s Get Ready to Rumble: The NIST PQC `Competition’.

This was an overview of the NIST post-quantum standardisation process, including a discussion of the goals and evaluation criteria. The talk also presented a few graphs that give a rough comparison of submissions according to features like key size, computation time, etc.

The session on isogeny crypto had two papers:

• Joost Renes talked about a method to derive very nice formulae for writing isogenies as explicit rational functions.
• Geovandro Pereira presented his joint paper with Zanon, Simplicio, Doliskani and Barreto. This work is about efficient methods for compressed supersingular isogeny Diffie-Hellman (SIDH). The goal is to minimise the bandwidth in the SIDH protocol by compressing the protocol messages, and to minimise the cost of de-compressing these values to complete the protocol. The paper makes excellent use of a lot of really nice tricks, including techniques for efficient computation of pairings and Shoup’s optimised variant of the Pohlig-Hellman algorithm.

The contributed talks included sessions on code-based crypto, lattices, hash-based crypto, multivariate crypto. There were also papers on cryptanalysis of post-quantum cryptosystems and quantum algorithms.

The recent results session contained three talks on isogeny crypto:

• Sam Jaques explained that Tani’s claw finding quantum attack on SIDH might be slower than estimated in the SIKE NIST submission. He suggests that the security level of the NIST submission attains higher security levels than claimed.
Ray Perlner has also posted a comment on the NIST PQCrypto mailing list suggesting this. Ray references independent works by Dan Bernstein, Scott Fluhrer, and himself on hash collisions, that argue that storage costs cannot be neglected in the complexity estimates. He writes “the quantum algorithm for collision search is no better than the best classical algorithms in any physically plausible model of computation”.

• Lorenz Panny sketched a variant of SIDH based on the curves with j-invariant in ${\mathbb F}_p$. The idea is to implement the group action key exchange protocol due to Couveignes, and so to avoid having to send points. A preprint will be made public soon.
• Aaron Hutchinson discussed joint work on efficient implementation of SIDH by exploiting parallelism. They consider the de Feo, Jao, Plut optimised method to compute $\ell^e$-isogenies in a multi-core setting.

Not presented at this conference, but also relevant: Gora Adj, Daniel Cervantes-Vázquez, Jesús-Javier Chi-Domínguez, Alfred Menezes and Francisco Rodríguez-Henríquez have posted on eprint the paper On the cost of computing isogenies between supersingular elliptic curves. The paper is about classical algorithms and they show how the low-storage algorithm due to van Oorschot and Wiener can be applied to isogeny problems. Again, they argue that storage costs should not be neglected and suggest that the stated security levels have been under-estimated. They suggest using somewhat smaller primes for SIDH. This reinforces the claims made by Jaques/Perlner/et al.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.