The supersingular endomorphism ring problem given one endomorphism

Arthur Herlédan Le Merdy; Benjamin Wesolowski

Paper 2023/1448

The supersingular endomorphism ring problem given one endomorphism

Arthur Herlédan Le Merdy, ENS de Lyon, LIP, UMR 5668 (U. Lyon, ENS de Lyon, Inria, UCBL), France, UMPA, UMR 5669, Lyon, France

Benjamin Wesolowski, ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France

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 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.

Note: The endomorphism division algorithm has been generalized to an isogeny division algorithm.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Isogeny-based cryptography Endomorphism ring Supersingular elliptic curve Orientation Class group Cryptanalysis
Contact author(s): arthur herledan_le_merdy @ ens-lyon fr
benjamin wesolowski @ ens-lyon fr
History: 2025-02-10: revised; 2023-09-22: received; See all versions
Short URL: https://ia.cr/2023/1448
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1448,
      author = {Arthur Herlédan Le Merdy and Benjamin Wesolowski},
      title = {The supersingular endomorphism ring problem given one endomorphism},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1448},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1448}
}