### On the cost of computing isogenies between supersingular elliptic curves

Gora Adj, Daniel Cervantes-Vázquez, Jesús-Javier Chi-Domínguez, 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
SIDHCSSIcryptanalysis
Contact author(s)
jjchi @ computacion cs cinvestav mx
History
2018-07-18: last of 2 revisions
See all versions
Short URL
https://ia.cr/2018/313

CC BY

BibTeX

@misc{cryptoeprint:2018/313,
author = {Gora Adj and Daniel Cervantes-Vázquez and Jesús-Javier Chi-Domínguez and Alfred Menezes and Francisco Rodríguez-Henríquez},
title = {On the cost of computing isogenies between supersingular elliptic curves},
howpublished = {Cryptology ePrint Archive, Paper 2018/313},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/313}},
url = {https://eprint.iacr.org/2018/313}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.