Cryptology ePrint Archive: Report 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.
Category / Keywords: quantum cryptanalysis
Original Publication (in the same form): IACR-CRYPTO-2019
Date: received 2 Feb 2019, last revised 19 Jun 2019
Contact author: sam e jaques at gmail com,jschanck@uwaterloo ca
Available format(s): PDF | BibTeX Citation
Version: 20190619:191423 (All versions of this report)
Short URL: ia.cr/2019/103
[ Cryptology ePrint archive ]