Cryptology ePrint Archive: Report 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.

Category / Keywords: isogeny-based cryptography, cryptanalysis

Date: received 29 Sep 2017, last revised 21 Feb 2018

Contact author: christophe f petit at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20180221:100650 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]