Mini-symposium on class groups and isogeny graphs
on the occasion of Marc Houben's defense of his PhD thesis
"Computational aspects of class group actions and applications to post-quantum cryptography"
speakers: Wouter Castryck, Chloe Martindale, Ben Smith
date and time: Wednesday 28 February 2024, 10:15 - 14:15
location: Leiden University, Huygens Building, room 2.11-2.14
10:15 - 11:15 Chloe Martindale (University of Bristol) -
Parametrizing maximal quaternion orders along supersingular l-isogeny paths
Abstract: Isogeny graphs of supersingular elliptic curves have many fascinating properties. For example, for certain parameter choices, they are optimal expander graphs in which we can efficiently compute the neighbours of any vertex. This particular property has caused supersingular isogeny graphs to be used in cryptographic protocols, especially in recent years in which the focus of the international cryptographic community has been shifting to post-quantum cryptography. Traditional key exchange protocols rely on factoring or the discrete logarithm problem, both of which can be solved in polynomial time by a quantum computer, hence the need to build new systems based on different computationally infeasible problems from number theory. One such example is the isogeny problem: given two elliptic curves, compute an isogeny between them (if it exists). Rephrased in graph-theoretical terms: given two vertices in a isogeny graph, find a path between them (if it exists). This turns out to be especially hard in the case of supersingular isogeny graphs, exactly because they are optimal expanders. Another fascinating property of supersingular isogeny graphs is their relation to both quaternion algebras and Shimura curves. The endomorphism ring of a supersingular elliptic curve is a maximal order in a quaternion algebra. In this talk, we will show how to exploit the relation to Shimura curves to parameterize endomorphism rings of supersingular elliptic curves based on their position in the graph. A parametrization of this kind serves to improve our understanding of the supersingular isogeny problem, especially as an aid in studying properties of the specific graph on which our cryptosystems are built, for example to look for security vulnerabilities.
This is joint work with Laia Amorós and James Clements and has also been contributed to by Annamaria Iezzi and Jana Sotáková.
11:30 - 12:30 Ben Smith (INRIA & LIX) -
Class groups in cryptography: back from the dead
Abstract: Ideal class groups of orders in quadratic number fields were once a thing in cryptography, but after being overtaken by elliptic-curve cryptosystems two decades ago, they have mostly lain forgotten. Now they are back, as a convenient source of unknown-order groups with trustless setup. However, the algorithms and security estimates that we need to use class groups in secure cryptosystems have barely been updated in over twenty years, and in some cases they are no longer fit for purpose. In this talk we will outline some of the challenges, and describe some attempted solutions.
13:15 - 14:15 Wouter Castryck (KU Leuven) - The isogeny interpolation problem
Abstract: It is easy to show that a degree-d isogeny phi between two elliptic curves E and E' is always uniquely determined by the images of any 4d + 1 points. The "isogeny interpolation problem" is about efficiently evaluating phi at any given point P on E, upon input of such interpolation data. The recent(ish) attacks on SIKE solve this problem in a special case, namely where the interpolation points span E[N] for some smooth N, coprime to d and the characteristic of the base field, such that N^2 > 4d. In the meantime we can handle many other types of groups, but in full generality the interpolation problem remains unsolved. I will give an overview of the known cases, and discuss some of the difficulties we face in the remaining cases. This is joint ongoing work with Decru, De Feo, Maino, Martindale, Panny, Robert and Wesolowski.
Marc Houben will defend his thesis in a public ceremony at 16:15, Academy Building, Rapenburg 73, Leiden.
Symposium organiser: Marco Streng