Paper 2019/298

Improved Classical Cryptanalysis of the Computational Supersingular Isogeny Problem

Craig Costello and Patrick Longa and Michael Naehrig and Joost Renes and Fernando Virdia

Abstract

Two recent papers have made significant advances towards a better understanding of the concrete hardness of the computational supersingular isogeny (CSSI) problem; this problem underlies the supersingular isogeny key encapsulation (SIKE) protocol, which is the only isogeny-based submission to the NIST post-quantum standardization effort. The first paper, by Adj, Cervantes-Vazquez, Chi-Dominguez, Menezes and Rodriguez-Henriquez, argues that the van Oorschot-Wiener (vOW) parallel collision finding algorithm is the best choice of classical algorithm for CSSI, and subsequently shows that the SIKE team were too conservative in their classical security estimates. The second paper, by Jaques and Schanck, gives an in-depth analysis into the best known quantum algorithms for CSSI, concluding that quantum algorithms do not achieve a significant advantage over the vOW algorithm and showing that the SIKE team were overly conservative in their quantum security analysis as well. Both papers agree that significantly smaller parameters could be used in the SIKE proposal to achieve NIST's security requirements. The main contribution of this work is an implementation of the van Oorschot-Wiener algorithm. We present a number of novel improvements, both to practical instantiations of the generic vOW algorithm and to its instantiation in the context of SIKE, that culminate in an improved classical cryptanalysis of CSSI. Subsequently, we study a set of three SIKE parameterizations - one from the original proposal, SIKEp751, and two from the two papers above, SIKEp434 and SIKEp610 -that we endorse for inclusion in future versions of the SIKE proposal. We provide assembly-optimized performance benchmarks for these parameter sets, which show that the SIKE protocol can be computed in approximately 6.4, 16.8 and 25.8 milliseconds on a 3.4GHz Intel Skylake processor at NIST's levels 1, 3, and 5, respectively.