[Resource Topic] 2018/313: On the cost of computing isogenies between supersingular elliptic curves

Welcome to the resource topic for 2018/313

Title:
On the cost of computing isogenies between supersingular elliptic curves

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

ePrint: https://eprint.iacr.org/2018/313

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .