Paper 2017/962

Hard and Easy Problems for Supersingular Isogeny Graphs

Christophe Petit and Kristin Lauter

Abstract

We consider the endomorphism ring computation problem for supersingular elliptic curves, constructive versions of Deuring's correspondence, and the security of Charles-Goren-Lauter's cryptographic hash function. We show that constructing Deuring's correspondence is easy in one direction and equivalent to the endomorphism ring computation problem in the other direction. We also provide a collision attack for special but natural parameters of the hash function, and we prove that for general parameters its preimage and collision resistance are also equivalent to the endomorphism ring computation problem. Our reduction and attack techniques are of independent interest and may find further applications in both cryptanalysis and the design of new protocols.

Note: Small revisions occurred at the Eurocrypt 2018 rebuttal process, plus description of follow-up work

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
isogeny-based cryptographycryptanalysis
Contact author(s)
christophe f petit @ gmail com
History
2018-02-21: revised
2017-09-30: received
See all versions
Short URL
https://ia.cr/2017/962
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/962,
      author = {Christophe Petit and Kristin Lauter},
      title = {Hard and Easy Problems for Supersingular Isogeny Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/962},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/962}},
      url = {https://eprint.iacr.org/2017/962}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.