Paper 2018/313

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.

Metadata
Available format(s)
PDF
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
2018-04-03: received
See all versions
Short URL
https://ia.cr/2018/313
License
Creative Commons Attribution
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.