Paper 2023/1399

The supersingular Endomorphism Ring and One Endomorphism problems are equivalent

Aurel Page, Univ. Bordeaux, CNRS, INRIA, Bordeaux INP, IMB, UMR 5251, F-33400 Talence, France
Benjamin Wesolowski, ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France
Abstract

The supersingular Endomorphism Ring problem is the following: given a supersingular elliptic curve, compute all of its endomorphisms. The presumed hardness of this problem is foundational for isogeny-based cryptography. The One Endomorphism problem only asks to find a single non-scalar endomorphism. We prove that these two problems are equivalent, under probabilistic polynomial time reductions. We prove a number of consequences. First, assuming the hardness of the endomorphism ring problem, the Charles–Goren–Lauter hash function is collision resistant, and the SQIsign identification protocol is sound for uniformly random keys. Second, the endomorphism ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves, a result previously known only for isogenies of smooth degree. Third, there exists an unconditional probabilistic algorithm to solve the endomorphism ring problem in time $\tilde O(p^{1/2})$, a result that previously required to assume the generalized Riemann hypothesis. To prove our main result, we introduce a flexible framework for the study of isogeny graphs with additional information. We prove a general and easy-to-use rapid mixing theorem.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in EUROCRYPT 2024
Keywords
Isogeny-based cryptographyendomorphism ring
Contact author(s)
aurel page @ inria fr
benjamin wesolowski @ ens-lyon fr
History
2024-03-08: revised
2023-09-18: received
See all versions
Short URL
https://ia.cr/2023/1399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1399,
      author = {Aurel Page and Benjamin Wesolowski},
      title = {The supersingular Endomorphism Ring and One Endomorphism problems are equivalent},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1399},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.