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 F_(p~2)-rational isogenies of degrees 2~e and 3~e between certain supersingular elliptic curves defined over 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 golden 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.
展开▼
