A note on the security of CSIDH
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We propose a quantum algorithm for computing an isogeny between two elliptic curves \(E_1,E_2\) defined over a finite field such that there is an imaginary quadratic order \(\mathcal {O}\) satisfying \(\mathcal {O}\simeq {\text {End}}(E_i)\) for \(i = 1,2\). This concerns ordinary curves and supersingular curves defined over \(\mathbb {F}_p\) (the latter used in the recent CSIDH proposal). Our algorithm has heuristic asymptotic run time \(e^{O\left( \sqrt{\log (|\varDelta |)}\right) }\) and requires polynomial quantum memory and \(e^{O\left( \sqrt{\log (|\varDelta |)}\right) }\) quantumly accessible classical memory, where \(\varDelta \) is the discriminant of \(\mathcal {O}\). This asymptotic complexity outperforms all other available methods for computing isogenies.