Colloquium Algebra - Wouter Castryck, University of Leuven

Title: Breaking the Supersingular Isogeny Diffie-Hellman protocol

Abstract:

Finding an explicit isogeny between two given isogenous elliptic curves over a finite field is considered a hard problem, even for quantum computers. In 2011 this led Jao and De Feo to propose a key exchange protocol that became known as SIDH, short for Supersingular Isogeny Diffie-Hellman. The security of SIDH does not rely on a pure isogeny problem, due to certain "auxiliary" elliptic curve points that are exchanged during the protocol (for constructive reasons).

In 2017 SIDH was submitted to the NIST standardization effort for post-quantum cryptography, and since then it has attracted a lot of attention. Early July, it advanced to the fourth round. In this talk I will discuss a break of SIDH that was discovered in collaboration with Thomas Decru about three weeks later. The attack uses isogenies between abelian surfaces and exploits the aforementioned auxiliary points, so it does not break the pure isogeny problem. It allows for a full key recovery at the highest security level in a few hours. As time permits, I will also discuss some more recent improvements and follow-up work due to Maino-Martindale, Wesolowski, and Robert.