The supersingular endomorphism ring problem given one endomorphism

2023/09/21 by Arthur Herlédan Le Merdy, Merdy, Arthur Herlédan Le, Benjamin Wesolowski +1
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2309.11912

openalex publication_date 2023/09/21 · openalex created_date 2023/09/22 · openalex updated_date 2026/07/30

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[α])¹/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 prove that the Primitivisation problem can be solved in polynomial time (a problem previously believed to be hard), and we prove that the action of smooth ideals on oriented elliptic curves can be computed in polynomial time (previous results of this form required the ideal to be powersmooth, i.e., not divisible by any large prime power). Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results.

Related

• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent
• Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings
• Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
• The supersingular isogeny path and endomorphism ring problems are\n equivalent
• On the Correspondence between Supersingular Elliptic Curves and maximal quaternionic Orders