Paper 2017/986

On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves

Kirsten Eisentraeger, Sean Hallgren, and Travis Morrison

Abstract

Cryptosystems based on supersingular isogenies have been proposed recently for use in post-quantum cryptography. Three problems have emerged related to their hardness: computing an isogeny between two curves, computing the endomorphism ring of a curve, and computing a maximal order associated to it. While some of these problems are believed to be polynomial-time equivalent based on heuristics, their relationship is still unknown. We give the first reduction between these problems, with the aid of one more problem which we call Action-on-$\ell$-Torsion. We show that computing $\ell$-power isogenies reduces to computing maximal orders and Action-on-$\ell$-Torsion. We also define the notion of a compact representation of an endomorphism, and use this to show that endomorphism rings always have polynomial representation size. We then reduce the endomorphism ring problem to computing maximal orders and Action-on-$\ell$-Torsion, thus laying the foundation for analysis of the hardness of endomorphism ring computation. This identifies these last two problems as one possible way to attack some systems, such as hash functions based on the $\ell$-isogeny graph of supersingular elliptic curves. This gives the potential to use algebraic tools in quaternion algebras to solve the problems. We also discuss how these reductions apply to attacks on a hash function of Charles, Goren, and Lauter.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Supersingular isogeny based cryptographynumber theory
Contact author(s)
txm950 @ psu edu
History
2017-10-09: received
Short URL
https://ia.cr/2017/986
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/986,
      author = {Kirsten Eisentraeger and Sean Hallgren and Travis Morrison},
      title = {On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2017/986},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/986}},
      url = {https://eprint.iacr.org/2017/986}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.