Paper 2018/371

Supersingular isogeny graphs and endomorphism rings: reductions and solutions

Kirsten Eisentraeger, Sean Hallgren, Kristin Lauter, Travis Morrison, and Christophe Petit

Abstract

In this paper, we study several related computational problems for supersingular elliptic curves, their isogeny graphs, and their endomorphism rings. We prove reductions between the problem of path finding in the $\ell$-isogeny graph, computing maximal orders isomorphic to the endomorphism ring of a supersingular elliptic curve, and computing the endomorphism ring itself. We also give constructive versions of Deuring's correspondence, which associates to a maximal order in a certain quaternion algebra an isomorphism class of supersingular elliptic curves. The reductions are based on heuristics regarding the distribution of norms of elements in quaternion algebras. We show that conjugacy classes of maximal orders have a representative of polynomial size, and we define a way to represent endomorphism ring generators in a way that allows for efficient valuation at points on the curve. We relate these problems to the security of the Charles-Goren-Lauter hash function. We provide a collision attack for special but natural parameters of the hash function and prove that for general parameters its preimage and collision resistance are also equivalent to the endomorphism ring computation problem.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2018
Keywords
post-quantum cryptographyisogeny-based cryptographycryptanalysis
Contact author(s)
txm950 @ psu edu
History
2018-04-25: received
Short URL
https://ia.cr/2018/371
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/371,
      author = {Kirsten Eisentraeger and Sean Hallgren and Kristin Lauter and Travis Morrison and Christophe Petit},
      title = {Supersingular isogeny graphs and endomorphism rings: reductions and solutions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/371},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/371}},
      url = {https://eprint.iacr.org/2018/371}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.