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