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 ≤296 hardware, finding interesting price-points.
Abstract In this paper we provide a framework for applying classical search and preprocessing to quantum oracles for use with Grover’s quantum search algorithm in order to lower the quantum circuit-complexity of Grover’s algorithm for single-target search problems. This has the effect (for certain problems) of reducing a portion of the polynomial overhead contributed by the implementation cost of quantum oracles and can be used to provide either strict improvements or advantageous trade-offs in circuit-complexity. Our results indicate that it is possible for quantum oracles for certain single-target preimage search problems to reduce the quantum circuit-size from O 2 n / 2 ⋅ m C O(2n/2⋅mC) (where C originates from the cost of implementing the quantum oracle) to O ( 2 n / 2 ⋅ m C ) O(2n/2⋅mC) without the use of quantum ram, whilst also slightly reducing the number of required qubits. This framework captures a previous optimisation of Grover’s algorithm using preprocessing [21] applied to cryptanalysis, providing new asymptotic analysis. We additionally provide insights and asymptotic improvements on recent cryptanalysis [16] of SIKE [14] via Grover’s algorithm, demonstrating that the speedup applies to this attack and impacting upon quantum security estimates [16] incorporated into the SIKE specification [14].
Large quantum computers pose a threat to our public-key cryptographic infrastructure. The possible responses are: \n \nDo nothing; accept the fact that quantum computers might be used to break widely deployed protocols. \nMitigate the threat by switching entirely to symmetric-key protocols. \nMitigate the threat by switching to different public-key protocols. \n \nEach user of public-key cryptography will make one of these choices, and we should not expect consensus. Some users will do nothing---perhaps because they view the threat as being too remote. And some users will find that they never needed public-key cryptography in the first place. \n \nThe work that I present here is for people who need public-key cryptography and want to switch to new protocols. Each of the three articles raises the security estimate of a cryptosystem by showing that some attack is less effective than was previously believed. Each article thereby reduces the cost of using a protocol by letting the user choose smaller (or more efficient) parameters at a fixed level of security. \n \nIn Part 1, I present joint work with Samuel Jaques in which we revise security estimates for the Supersingular Isogeny Key Exchange (SIKE) protocol. We show that known quantum claw-finding algorithms do not outperform classical claw-finding algorithms. This allows us to recommend 434-bit primes for use in SIKE at the same security level that 503-bit primes had previously been recommended. \n \nIn Part 2, I present joint work with Martin Albrecht, Vlad Gheorghiu, and Eamonn Postelthwaite that examines the impact of quantum search on sieving algorithms for the shortest vector problem. Cryptographers commonly assume that the cost of solving the shortest vector problem in dimension d is 2(0.265ldots+o(1))d quantumly and 2(0.292ldots+o(1))d classically. These are upper bounds based on a near neighbor search algorithm due to Becker--Ducas--Gama--Laarhoven. Naively, one might think that d must be at least 483(approx128/0.265) to avoid attacks that cost fewer than 2128 operations. Our analysis accounts for terms in the o(1) that were previously ignored. In a realistic model of quantum computation, we find that applying the Becker--Ducas--Gama--Laarhoven algorithm in dimension d>376 will cost more than 2128 operations. We also find reason to believe that the classical algorithm will outperform the quantum algorithm in dimensions d<288. \n \nIn Part 3, I present solo work on a variant of post-quantum RSA. The original pqRSA proposal by Bernstein--Heninger--Lou--Valenta uses terabyte keys of the form n=p1p2p3p4cdotspicdotsp231 where each pi is a 4096-bit prime. My variant uses terabyte keys of the form n=p12p23p35p47cdotspipiicdotsp20044225287 where each pi is a 4096-bit prime and pii is the i-th prime. Prime generation is the most expensive part of post-quantum RSA in practice, so the smaller number of prime factors in my proposal gives a large speedup in key generation. The repeated factors help an attacker identify an element of small order, and thereby allow the attacker to use a small-order variant of Shor's algorithm. I analyze small-order attacks and discuss the cost of the classical pre-computation that they require.