Parallelism strategies for the tuneable golden-claw finding problem

Abstract

In this paper we study a strategy for adapting the “Tiny Claw” Grover-based attack of Biasse and Pring (A framework for reducing the overhead of the quantum oracle for use with Grover's algorithm with applications to cryptanalysis of SIKE, J. Math. Cryptol. 15 (2019), pp. 143–156) for attacking SIKE and abstract it under a realistic model of classical memory-access costs. Our results allow us to retain the almost quadratic reduction in the overheads involved with the implementing the quantum oracle in this cost model and demonstrate how the cost of the parallel version of this attack scales in a manner superior to that of a naive use of Grover’s algorithm. In order to investigate the utility of the Tiny Claw approach, we perform a quantum resource estimation of the classical and quantum resources required to attack various SIKE instances with Tiny Claw when when we are limited to $\le 2^{96}$ hardware, finding interesting price-points.

Keywords:

• Quantum cryptanalysis
• quantum search
• CSSI
• SIKE

Acknowledgments

The authors would like to thank Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler and Mathias Soeken for early access to the results of [23]. The authors would also like to thank the reviewers for an initial submission of this work to PQCRYPTO 2020 and to the reviewers of this journal – the advice from both sources was thoughtful, very helpful and a large amount of the suggestions were incorporated into the final work. Benjamin Pring was funded during the development of this research by EPRSC grant EP/M50645X/1, National Science Foundation grant 183980, NIST grant 60NANB17D184, a Seed grant of the Florida Center for Cybersecurity and a USF proposal enhancement grant.

Disclosure statement

No potential conflict of interest was reported by the author(s). Author list in alphabetical order; see https://www.ams.org/profession/leaders/culture/CultureStatement04.pdf.

Additional information

Funding

Benjamin Pring was funded during the development of this research by EPRSC grant EP/M50645X/1, National Science Foundation grant 183980, NIST grant 60NANB17D184, a Seed grant of the Florida Center for Cybersecurity and a USF proposal enhancement grant.