Cryptology ePrint Archive: Report 2018/313

On the cost of computing isogenies between supersingular elliptic curves

Gora Adj and Daniel Cervantes-Vázquez and Jesús-Javier Chi-Domínguez and Alfred Menezes and Francisco Rodríguez-Henríquez

Abstract: The security of the Jao-De Feo Supersingular Isogeny Diffie-Hellman (SIDH) key agreement scheme is based on the intractability of the Computational Supersingular Isogeny (CSSI) problem --- computing ${\mathbb F}_{p^2}$-rational isogenies of degrees $2^e$ and $3^e$ between certain supersingular elliptic curves defined over ${\mathbb F}_{p^2}$. The classical meet-in-the-middle attack on CSSI has an expected running time of $O(p^{1/4})$, but also has $O(p^{1/4})$ storage requirements. In this paper, we demonstrate that the van Oorschot-Wiener collision finding algorithm has a lower cost (but higher running time) for solving CSSI, and thus should be used instead of the meet-in-the-middle attack to assess the security of SIDH against classical attacks. The smaller parameter $p$ brings significantly improved performance for SIDH.

Category / Keywords: public-key cryptography / SIDH, CSSI, cryptanalysis

Date: received 3 Apr 2018, last revised 14 May 2018

Contact author: jjchi at computacion cs cinvestav mx

Available format(s): PDF | BibTeX Citation

Version: 20180514:233120 (All versions of this report)

Short URL: ia.cr/2018/313


[ Cryptology ePrint archive ]