International Association for Cryptologic Research

International Association
for Cryptologic Research


Improved Classical Cryptanalysis of SIKE in Practice

Craig Costello
Patrick Longa
Michael Naehrig
Joost Renes
Fernando Virdia
DOI: 10.1007/978-3-030-45388-6_18
Search ePrint
Search Google
Abstract: The main contribution of this work is an optimized implementation of the van Oorschot-Wiener (vOW) parallel collision finding algorithm. As is typical for cryptanalysis against conjectured hard problems (e. g. factoring or discrete logarithms), challenges can arise in the implementation that are not captured in the theory, making the performance of the algorithm in practice a crucial element of estimating security. We present a number of novel improvements, both to generic instantiations of the vOW algorithm finding collisions in arbitrary functions, and to its instantiation in the context of the supersingular isogeny key encapsulation (SIKE) protocol, that culminate in an improved classical cryptanalysis of the computational supersingular isogeny (CSSI) problem. In particular, we present a scalable implementation that can be applied to the Round-2 parameter sets of SIKE that can be used to give confidence in their security levels.
Video from PKC 2020
  title={Improved Classical Cryptanalysis of SIKE in Practice},
  booktitle={Public-Key Cryptography – PKC 2020},
  series={Public-Key Cryptography – PKC 2020},
  author={Craig Costello and Patrick Longa and Michael Naehrig and Joost Renes and Fernando Virdia},