Paper 2019/103

Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE

Samuel Jaques and John M. Schanck

Abstract

We introduce models of computation that enable direct comparisons between classical and quantum algorithms. Incorporating previous work on quantum computation and error correction, we justify the use of the gate-count and depth-times-width cost metrics for quantum circuits. We demonstrate the relevance of these models to cryptanalysis by revisiting, and increasing, the security estimates for the Supersingular Isogeny Diffie--Hellman (SIDH) and Supersingular Isogeny Key Encapsulation (SIKE) schemes. Our models, analyses, and physical justifications have applications to a number of memory intensive quantum algorithms.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2019
Keywords
quantum cryptanalysis
Contact author(s)
sam e jaques @ gmail com
jschanck @ uwaterloo ca
History
2019-06-19: revised
2019-02-05: received
See all versions
Short URL
https://ia.cr/2019/103
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/103,
      author = {Samuel Jaques and John M.  Schanck},
      title = {Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/103},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/103}},
      url = {https://eprint.iacr.org/2019/103}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.