logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

Breaking SIDH in polynomial time

Damien Robert

( Inria/IMB )

-

le 13 septembre 2022 à 10:00

SIDH/SIKE was a post quantum key exchange mechanism based on isogenies between supersingular elliptic curves which was recently 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:y2=x3+xE: y^2=x^3+x has explicit endomorphism ii. Finally we explain how by going to dimension 8, we could break in proven quasi-linear time all parameters for SIKE. We will 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 computation! There will also be (hopefully) fun memes during the talk!