Maria Corte-Real Santos

An effective Deuring correspondence over extension fields and its application to isogeny-based cryptography

The Deuring correspondence gives an isomorphism between endomorphism rings of supersingular elliptic curves defined over Fp2 and maximal orders in a quaternion algebra over Q. In fact, this correspondence is an equivalence of categories, meaning that an isogeny between two such elliptic curves corresponds to an ideal connecting the corresponding maximal orders. In this talk, we will introduce effective algorithms for performing this correspondence when our isogenies whose kernels contain points that are not Fp2 rational.

We will then demonstrate two applications of these algorithms. Firstly, we will show its application to the isogeny-based signature scheme, SQIsign. By allowing extension fields in the signing procedure, we can increase the amount of rational 2*-torsion available, which provides a large speed-up in verification at the cost of a modest slow down during signing. Alongside other algorithmic improvements, we can achieve a 3x decrease in the number of Fp-operations required compared to the verification algorithm currently used in the reference implementation of SQIsign.

Secondly, we will outline how this can be used to compute Hilbert class polynomials and modular polynomials from supersingular elliptic curves.