The supersingular endomorphism ring problem given one endomorphism
Authors
Abstract
Given a supersingular elliptic curve E and a non-scalar endomorphism α of E, we prove that the endomorphism ring of E can be computed in classical time about disc(Z[α])^1/4, and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions.
Along the way, we describe and analyse a general algorithm to divide isogenies in polynomial time, and to solve the Primitivisation problem in polynomial time. Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results.
References
How to cite
Arthur {Herlédan Le Merdy} and Benjamin Wesolowski, The supersingular endomorphism ring problem given one endomorphism. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/akgyivrzn.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.