This is the discussion thread for the sixth (and last) session of season three of The Isogeny Club , where Charlotte presents her talk titled: Finding isogenies of fixed degree between supersingular elliptic curves
Abstract:
Finding isogenies between supersingular elliptic curves is a natural algorithmic problem, known to be equivalent to computing the curves’ endomorphism rings. When the isogeny is additionally required to have a specific degree, the problem appears to be somewhat different in nature, yet it is also considered a hard problem in isogeny-based cryptography.
In this talk, we present improved classical and quantum algorithms that compute an isogeny of a specified degree d between two given curves E and E’ (over 𝔽p2), when it exists. We use the general strategy of first computing the endomorphism rings of both curves as well as the reduced norm form associated to Hom(E, E’). This is followed by trying to represent the integer d as a solution of the reduced form since it can be translated to give a degree-d isogeny.
The algorithms presented in this talk explore different methods for solving quadratic Diophantine equations (such as Cornacchia’s and Coppersmith’s algorithms) in combination with exhaustively guessing or searching over variables with Grover in the quantum setting. This allows us to obtain essentially memory-free algorithms with better time complexity than meet-in-the-middle algorithms for large sets of parameters ranging between d ≈ p1/2 and d ≈ p³, depending on the chosen algorithm and whether quantum resources can be accessed.
Video:
