International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE

Authors:
Samuel Jaques
John M. Schanck
Download:
DOI: 10.1007/978-3-030-26948-7_2 (login may be required)
Search ePrint
Search Google
Award: Best Young Researcher Paper
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.
Video from CRYPTO 2019
BibTeX
@article{crypto-2019-29855,
  title={Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11692},
  pages={32-61},
  doi={10.1007/978-3-030-26948-7_2},
  author={Samuel Jaques and John M. Schanck},
  year=2019
}