Date de l'exposé : 14 octobre 2022
An overview of the Deuring correspondence and isogeny-based cryptography
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.
This topic is divided in two parts: the first is dedicated to the theoretic and algorithmic study of the mathematical objects of the Deuring correspondence, while the second builds protocols on the results and the algorithms of the first parts.
In the first part, we develop two main axes of research.
First, we contribute to the problem of solving norm equations in various families of orders and ideals. These algorithms play a crucial role in a number of the protocols and algorithms that constitute the remaining part of our work. In particular, we extend the initial results of Kohel, Lauter, Petit and Tignol (KLPT) to the orders whose Gorenstein closure is an Eichler order, allowing us, among other things, to solve norm equations inside any maximal order and their ideals.
Second, we look at isogeny representations to evaluate and computes isogenies. The classical method is to use the Vélu formulas and we introduce a new algorithm with a complexity in the squareroot of the degree to compute them. Then, we look at the representation based on ideals that can be derived from the Deuring correspondence. With this representation, we get algorithms of logarithmic complexity in the degree. We present new algorithms, more efficient in practice, for this representation. Finally, we present a third representation, based on suborders of the endomorphism ring. This representation is not equivalent to the one based on ideals, and this is what motivates its study.
In the second part, we construct three new protocols. We present SQISign, a signature protocol based on the proof of knowledge of endomorphism ring. This scheme is an improvement of the signature from Galbraith, Petit and Silva and is based on a generalization of the KLPT algorithm. We made an implementation using our efficient algorithms to compute the ideal representation. The security of SQISign is based on a new computational problem.
Then, we introduce Séta, a public key encryption scheme. This primitive is derived from a trapdoor one way function obtained by modifying the torsion point attacks from Petit in 2017 and we implemented it on top of the SQISign code.
Finally, we construct pSIDH, a prime degree version of the SIDH scheme from our new suborder representation.
date: 16-17 novembre 2022
prenom: European
nom: CyberWeek
universite: Rennes
titre: Workshop mise en oeuvre de la cryptographie post-quantique
resume: L'inscription est gratuite mais obligatoire. Le programme est disponible à l'adresse
https://www.european-cyber-week.eu/programme
