Seminar Sessions
A seminar session for young isogenists.
Season three
The schedule for Season three of The Isogeny Club is to be finalised. For now, the focus is on the
at Eurocrypt on April 22th, Lyon, France.
Previous talks
Season two
-
Sarah Arpin - Orientations and Isogeny Graphs
Leiden University
January 31st, 17:00 (CET).abstract
To study supersingular isogeny graphs, one may add to the elliptic curves the information of an orientation, or a particular embedding of an imaginary quadratic field into the endomorphism ring of the curve. Recent cryptographic protocols (Séta, OSIDH) have made use of orientations to define new hard problems on supersingular isogeny graphs. The mathematics of orientations have been studied for a long time, but the algorithmic implications are just now being understood.
As part of a recent Women in Numbers 5 (WIN5) collaboration, my collaborators and I use orientations towards two different goals: 1. path-finding algorithms in the supersingular ℓ-isogeny graph and 2. understanding and counting cycles in the supersingular ℓ-isogeny graph. In this talk, we will first introduce the theory of orientations and discuss the relevant hard problems. We will go on to describe the path-finding algorithms and the theory behind cycle-counting which stem from adding orientations to supersingular elliptic curves.
-
Andrea Basso - A Post-Quantum Oblivious PRF from Isogenies
University of Bristol
February 14th, 17:00 (CET).abstract
An oblivious pseudorandom function, or OPRF, is an important primitive that is used to build many advanced cryptographic protocols. Despite its relevance, very few post-quantum solutions exist.
In this talk, we present a novel OPRF protocol that is post-quantum, verifiable, round-optimal, and moderately compact. The protocol is based on a previous SIDH-based construction by Boneh et al., which was later shown to be insecure due to an attack on its one-more unpredictability. We propose an efficient countermeasure against this attack, and we demonstrate how to adapt the protocol to work with the countermeasures against the SIDH attacks. To achieve this, we also propose the first proof of isogeny knowledge that is compatible with masked torsion points, which may be of independent interest. We also design a novel non-interactive proof of knowledge of parallel isogenies, which reduces the number of communication rounds of the OPRF to the theoretically-optimal two. Putting everything together, we obtain the most compact post-quantum verifiable OPRF protocol.
-
Jonathan Komada Eriksen - Deuring for the People!
NTNU
February 28th, 17:00 (CET).abstract
In Season one, talk four of the Isogeny Club, we saw a presentation on computing the Deuring correspondence. The efficiency of this computation depends a lot on the characteristic one is working over, and applications such as SQIsign, require primes p of a special form to do this computation. In this presentation, we look at computing the Deuring correspondence in general characteristic, i.e. without assuming any special form of the prime p being used. We start by recalling a "standard" algorithm for computing the Deuring correspondence, before discussing specific optimisations for the case of general characteristic.
-
Michael Meyer - SQISign primes: Fantastic p's and where to find them
University of Regensburg
March 14th, 17:00 (CET).
abstract
As discussed in the Isogeny Club talks by Antonin Leroux and Jonathan Komada Eriksen, SQISign requires a special prime characteristic in order to be efficient. In particular, we require a large factor of p^2-1 to be smooth. In this talk, we discuss the related problem of finding twin smooth integers via two different methods: the PTE-sieve that uses solutions to the Prouhet-Tarry-Escott problem, and an algorithm by Conrey-Holmstrom-McLaughlin. Although most of our results are not directly applicable to SQISign, we show how smaller twin smooths can be used to construct SQISign-friendly primes. Our approach is especially suitable for finding parameters for the NIST-III and NIST-V security levels.
-
Pierrick Dartois - SQISignHD: signing with higher dimensional isogenies
INRIA Bordeaux
March 28th, 17:00 (CEST).
abstract
The SQISign isogeny-based post-quantum digital signature scheme introduced by De Feo, Kohel, Leroux, Petit and Wesolowski outputs very compact signatures at the expense of a high signature time. In this talk, we introduce a new scheme based on SQISign and the polynomial time torsion point attacks against SIDH due to Castryck, Decru, Maino, Martindale and Robert to sign with higher dimensional isogenies. This scheme remains to be implemented but we expect a significant signature time improvement, better security properties and signatures even more compact than in the original SQISign scheme.
-
Valerie Gilchrist - Evaluating rational isogenies with irrational kernel points
Université Libre de Bruxelles
April 11th, 17:00 (CEST).
abstract
An isogeny can be defined over a given field even when its kernel generators, which we need for efficient Vélu formulae, are only defined over some extension. How can we efficiently evaluate these isogenies? In this talk we will present some new algorithms for this and related problems.
Season one
-
Thomas Decru - Breaking SIKE
KU Leuven
September 13th, 17:00 (CEST).abstract
Thomas paints a somewhat broader picture of the genus-2 isogeny setting to showcase how Wouter Castryck and Thomas found all the pieces of the puzzle to break SIKE.
-
Bruno Sterner - git commit -m “isogenies”
University of Surrey
September 27th, 17:00 (CEST).abstract
Supersingular isogeny graphs possess many properties that make it an interesting object to study mathematically as well as attempt to apply for cryptographic purposes. In this talk, Bruno will present one of these properties and showcase how it can be applied to construct a commitment scheme. This commitment scheme has strong security properties and doesn’t require random oracles.
-
Maria Corte-Real Santos - [superlative]Solver: Attacking the General Isogeny Problem
University College London
October 11th, 17:00 (CEST).abstract
The general supersingular isogeny problem is the foundational hardness assumption underpinning isogeny-based cryptography. Its conjectured classical and quantum hardness has cemented isogenies as a promising tool for building post-quantum secure protocols.
In this talk, we will look at the general isogeny problem in low dimensions. More specifically, we consider the hardness of finding an isogeny between two given supersingular elliptic curves or two superspecial abelian surfaces defined over 𝔽p2. Viewing these as path finding problems in a related isogeny graph, we introduce a general framework for solving these problems and present the state-of-the-art attacks against them. We will also discuss a strategy for improving their concrete complexity, based on joint work with Craig Costello, Sam Frengley and Jia Shi.
-
Antonin Leroux - A new algorithm for the effective Deuring correspondence: making SQISign
faster
DGA,
October 25th, 17:00 (CEST).abstract
The quantum computer is a threat to cryptography as it can solve the problems upon which relies the security of a lot of protocols. Isogeny-based cryptography is a family of protocols relying on the hardness of finding an isogeny between two supersingular elliptic curves, a problem assumed hard even for a quantum computer. In this talk, we focus on the connection between isogeny-based cryptography and quaternion algebras called the Deuring correspondence.
We will start with a generic overview of the applications of the Deuring correspondence to isogeny-based cryptography, before presenting a new algorithm to compute and realize the Deuring correspondence. In particular, this can be applied to speed-up the SQISign signature scheme.
-
Tako Boris Fouotsa - Torsion point images in SIDH: from savior to killer
EPFL,
November 8th, 17:00 (CET).abstract
The first isogeny-based key exchange is the CRS (Couveignes - Rostovtsev - Stolbunov) scheme, which uses ordinary isogenies. The CRS scheme is relatively slow and is subject to a sub-exponential quantum attack. This motivated Jao and De Feo to suggest SIDH, which uses supersingular isogenies that, as opposed to ordinary isogenies, do not commute. To solve this commutativity issue, Jao and De Feo publish images of torsion points through the secret isogeny. SIDH was then faster and was not vulnerable to sub-exponential quantum attacks.
Today, the picture has changed considerably. The torsion point images have been used to design both adaptive and passive attacks on SIDH. Recently, we reached the "point de non retour": they were used to design a polynomial classical attack on SIDH.
In this talk, we will tell the story of the torsion point images in SIDH. We will go through their role in the design of SIDH, and in the design of both adaptive and passive attacks on SIDH.
-
Sabrina Kunzweiler - Genus 2 Isogenies
Ruhr University Bochum
November 22nd, 17:00 (CET).abstract
Elliptic curves are abelian varieties of dimension one. It is only natural to consider generalizations of isogeny-based cryptographic protocols to higher dimensions. Apart from mathematical curiosity, the recent attacks on SIDH have shown that it is essential to study such generalizations in order to understand the security of elliptic curve based protocols.
This talk gives an introduction to Jacobians of genus-2 curves (abelian varieties of dimension 2) and isogenies in this setting. The focus lies on the computation of Richelot isogenies.
-
Marc Houben - Horizontal racewalking using radical isogenies
Universiteit Leiden
December 13th, 17:00 (CET).
abstract
Radical isogeny formulae are equations that can be used to efficiently compute long chains of isogenies of small degree. Basically, they express the coefficients of the next curve in a chain of N-isogenies explicitly in terms of some expression involving the N-th root of a quantity depending on the Weierstrass coefficients of the input curve. One can prove that such an expression always exists, but finding it is a nontrivial task. We present a new method for finding radical isogeny formulae that extends the range for which we know them from N ≤ 13 to N ≤ 37.
We rewrite the existing and new formulae to optimize for fast evaluation. For even N, we present a conjecture that determines which N-th root must be taken in order to stay on the surface of the CSIDH isogeny graph, and we prove this conjecture for N ≤ 14. The combination of the above results in a speed up of a factor 3 for long chains of 2-isogenies over 512 bit prime fields, and we gain 12% over the previous implementation of CSIDH with radical isogenies.
Personal page • Slides • Recording • Discussion
Reach Jonathan and Krijn
via isogenyclub@gmail.com to join!
Overview of discussion available at askcryp.to.
Researchseminars.org here.
Twitter here.
YouTube here.