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
-
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},
url = {https://eprint.iacr.org/2019/103}
}
