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 at uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20190619:191423 (All versions of this report)

Short URL: ia.cr/2019/103