100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

Damien Robert

Breaking SIDH in polynomial time
Jeudi, 27 Avril, 2023 - 10:30
Résumé : 

SIDH/SIKE was a post quantum key exchange mechanism based on isogenies
between supersingular elliptic curves which was selected in July 5 2022 by
NIST to advance to the fourth round of the PQC competition. It was soon
after broken during the summer in a series of three papers by
Castryck-Decru, Maino-Martindale and myself.

The attacks all use the extra information on the torsion points used for
the key exchange. We first review Petit’s dimension 1 torsion point attack
from 2017 which could only apply to unbalanced parameters. Then we explain
how the dimension 2 attacks of Maino-Martindale and especially
Castryck-Decru could break in heuristic (but in practice very effective)
polynomial time some parameters, including the NIST submission where the
starting curve $E:y^2=x^3+x$ has explicit endomorphism.
Finally we explain how by going to dimension 8, we could break in proven
quasi-linear time all parameters for SIKE.

We will also explain how the SIDH protocol worked at the beginning of the talk.
We will see that the attack ultimately relies on a very simple 2x2 matrix


Institution de l'orateur : 
Institut de Mathématiques de Bordeaux
Thème de recherche : 
Théorie des nombres
Salle : 
logo uga logo cnrs