10:00am - 12:00pmIsogenies in Cryptography
Chair(s): Tanja Lange (Eindhoven University of Technology, Netherlands, The), Chloe Martindale (Eindhoven University of Technology, Netherlands, The), Lorenz Panny (Eindhoven University of Technology, Netherlands, The)
The isogeny graph of elliptic curves over finite fields has long been a subject of study in algebraic geometry and number theory. During the past 10 years several authors have shown multiple applications in cryptology. One interesting feature is that systems built on isogenies seem to resist attacks by quantum computers, making them the most recent family of cryptosystems studied in post-quantum cryptography.
This mini-symposium brings together presentations on cryptosystems built on top of isogenies, their use in applications, and different approaches to the cryptanalysis, including quantum cryptanalysis.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Superspecial genus 2 curves in cryptography
Thomas Decru
KU Leuven
Isogenies can be defined between algebraic groups different from elliptic curves. In a joint work with Castryck and Smith, we construct a genus 2 version of the Charles-Goren-Lauter hash function based on isogenies. We will discuss the technical difficulties that arise from adapting the elliptic curve case.
Quantum algorithms for finding isogenies between supersingular elliptic curves.
Jean-François Biasse
University of South Florida
We will present joint work with Jao and Sankhar on a quantum algorithm for finding an isogeny between two given supersingular elliptic curves. In general, it runs in time O(p^1/4), but it has subexponential run time if both curves are defined over Fp. We will also discuss improvements to this method obtained in collaboration with Iezzi and Jacobson.
Our method consists in performing a quantum search within possible paths originating from the given curves to attain curves defined over Fp. Then we find an isogeny between curves defined over Fp by naturally exploiting the action of the class group of the endormorphism ring of these curves similarly to the work of Childs Jao and Soukharev. Further improvements to this method focus on the cost of the evaluation of the action of the class group.
Horizontal isogeny graphs
Benjamin Wesolowski
CWI
A horizontal isogeny graph is a graph whose vertices represent abelian varieties which all share the same endomorphism ring, and edges represent isogenies between them. They are an important tool to study the discrete logarithm problem on these abelian varieties, and allow to construct promising post-quantum public key cryptosystems. We discuss the analytic methods that allow to study the "mixing" properties of these graphs (a short random walk rapidly converges to a uniformly distributed vertex), with applications for cryptography.
Isogeny Graphs of Ordinary Abelian Surfaces and Endomorphism Rings
Dimitar Jetchev
EPFL
Building on some recent joint work with Brooks and Wesolowski, we recall a recent construction of certain l-power isogeny graphs of principally polarizable ordinary abelian varieties and study the structure of these graphs using the theory of Bruhat-Tits buildings for symplectic groups. Our results have implications in various problems from computational number theory and mathematical cryptology, most notably, the question of computing endomorphism rings as well as constructing hyperelliptic curves over finite fields whose Jacobians have a fixed characteristic polynomial of Frobenius and maximal endomorphism rings (the CM method in genus 2). This work is joint with Gaetan Bisson and Alexey Zykin (in memoriam).
