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
-
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},
url = {https://eprint.iacr.org/2017/962}
}
