Paper 2023/106

Deuring for the People: Supersingular Elliptic Curves with Prescribed Endomorphism Ring in General Characteristic

Jonathan Komada Eriksen, Norwegian University of Science and Technology
Lorenz Panny, Institute of Information Science, Academia Sinica
Jana Sotáková, University of Amsterdam, QuSoft
Mattia Veroni, Norwegian University of Science and Technology
Abstract

Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields. In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the characteristic. Our algorithm follows the same overall strategy as earlier works, but we add simple (yet effective) optimizations to multiple subroutines to significantly improve the practical performance of the method. To demonstrate the impact of our improvements, we show that our implementation achieves highly practical running times even for examples of cryptographic size. One implication of these findings is that cryptographic security reductions based on KLPT-derived algorithms (such as [EHLMP18; Wes22]) have become tighter, and therefore more meaningful in practice. Another is the pure bliss of fast(er) computer algebra: We provide a Sage implementation which works for general primes and includes many necessary tools for computational number theorists' and cryptographers' needs when working with endomorphism rings of supersingular elliptic curves. This includes the KLPT algorithm, translation of ideals to isogenies, and finding supersingular elliptic curves with known endomorphism ring for general primes. Finally, the Deuring correspondence has recently received increased interest because of its role in the SQISign signature scheme [DeF+20]. We provide a short and self-contained summary of the state-of-the-art algorithms without going into any of the cryptographic intricacies of SQISign.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. LuCaNT 2023
Keywords
algorithmssupersingular elliptic curvesendomorphism ringsquaternion algebras
Contact author(s)
jonathan k eriksen @ ntnu no
lorenz @ yx7 cc
ja sotakova @ gmail com
mattia veroni @ ntnu no
History
2023-08-20: last of 2 revisions
2023-01-27: received
See all versions
Short URL
https://ia.cr/2023/106
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/106,
      author = {Jonathan Komada Eriksen and Lorenz Panny and Jana Sotáková and Mattia Veroni},
      title = {Deuring for the People: Supersingular Elliptic Curves with Prescribed Endomorphism Ring in General Characteristic},
      howpublished = {Cryptology ePrint Archive, Paper 2023/106},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/106}},
      url = {https://eprint.iacr.org/2023/106}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.