Paper 2019/298

Improved Classical Cryptanalysis of SIKE in Practice

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

Abstract

The main contribution of this work is an optimized implementation of the vanOorschot-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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2020
Keywords
Post-quantum cryptographysupersingular elliptic curvesisogeniesSIDHSIKEparallel collision searchvan Oorschot-Wiener algorithm
Contact author(s)
fernando virdia 2016 @ rhul ac uk
mnaehrig @ microsoft com
History
2020-06-03: last of 4 revisions
2019-03-20: received
See all versions
Short URL
https://ia.cr/2019/298
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/298,
      author = {Craig Costello and Patrick Longa and Michael Naehrig and Joost Renes and Fernando Virdia},
      title = {Improved Classical Cryptanalysis of SIKE in Practice},
      howpublished = {Cryptology ePrint Archive, Paper 2019/298},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/298}},
      url = {https://eprint.iacr.org/2019/298}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.