The supersingular endomorphism ring problem given one endomorphism
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.
Authors
- Benjamin Wesolowski (ORCID: https://orcid.org/0000-0003-1249-6077)
- Arthur Le Merdy (ORCID: https://orcid.org/0009-0007-6116-6863)
Institutions
- Université Claude Bernard Lyon 1 (FR)
- École Normale Supérieure de Lyon (FR)
- Centre National de la Recherche Scientifique (FR)
- Institut national de recherche en sciences et technologies du numérique (FR)
- Laboratoire de l'Informatique du Parallélisme (FR)
- Unité de Mathématiques Pures et Appliquées (FR)
Publication Details
- Journal
- IACR Communications in Cryptology
- Published
- 2025-04-08
- DOI
- https://doi.org/10.62056/akgyivrzn
- Primary Topic
- Algebraic Geometry and Number Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Agence Nationale de la Recherche