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.
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].
This paper presents a hardware-conscious analysis of the quantum acceleration of the classical 3-round Keccak-256 preimage attack using Grover's Algorithm. While the theoretical quantum speed-up from T_cl=2^{57.8} (classical) to T_qu = 2^{28.9} (quantum) is mathematically sound, the practical implementation overhead is so extreme that attacks remain wholly infeasible in both resource and runtime dimensions. Using Qiskit-based circuit synthesis, we derive that a 3-round Keccak quantum oracle requires: 9,600 Toffoli gates (with uncomputation for reversibility); 3,200 logical qubits (1,600 state + 1,600 auxiliary); 7.47 * 10^{13} total 2-qubit gates (full Grover search); 3.2 million physical qubits (with quantum error correction)PROHIBITIVE; 0.12 years (43 days) to 2,365+ years execution time, depending on machine assumptions. These barriers -- particularly the physical qubit requirements, circuit depth, and error accumulation -- render the quantum attack infeasible for any foreseeable quantum computer. Consequently, SHA-3 security is not threatened by quantum computers for preimage attacks. We emphasize the critical importance of hardware-aware complexity analysis in quantum cryptanalysis: the elegant asymptotic theory of Grover's Algorithm hides an engineering overhead so prohibitive that the quantum approach becomes infeasible from both resource and implementation perspectives.
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.
Grover’s algorithm represents a cornerstone quantum attack against symmetric cryptography, offering a quadratic speedup for exhaustive key search. While its theoretical properties are well established, the practical robustness of Grover’s algorithm under non-ideal oracle execution remains insufficiently quantified, particularly in security-relevant contexts. This work presents a comprehensive quantitative analysis of Grover’s robustness against intermittent oracle failures, modeling realistic execution imperfections that may arise in practical quantum attack scenarios. Using a reduced two-dimensional representation of amplitude amplification, we define and measure a practical reliability threshold beyond which Grover’s success probability collapses abruptly. Our results demonstrate that this threshold decreases exponentially with problem size, scaling as p∗(n)∝2−n/2, implying that cryptographically relevant problem sizes require unrealistically high oracle reliability to preserve quantum advantage. For n=40, the oracle must fail less than once every ∼800,000 iterations to preserve practical advantage, a requirement that becomes exponentially more stringent for larger key sizes. These findings do not contradict Grover’s theoretical correctness but highlight critical robustness limitations that must be explicitly considered when assessing quantum threats to symmetric cryptography. We provide actionable insights for post-quantum security assessment by translating abstract quantum assumptions into concrete reliability requirements, demonstrating that the practical feasibility of Grover-based attacks may be significantly lower than commonly assumed under realistic hardware constraints.
Abstract The advent of quantum computing necessitates a rigorous reassessment of classical cryptographic primitives, particularly lightweight block ciphers (LBCs) deployed in resource-constrained environments. This work presents a comprehensive quantum implementation and security analysis of the Feistel-based LBC MIBS against quantum cryptanalysis. Using the inherent reversibility of its structure, we develop a novel ancilla-free quantum circuit that optimizes qubit count and depth. For MIBS-64 and MIBS-80, our implementation achieves quantum costs of 23,371 and 24,363, requiring 128 and 144 qubits, respectively, with a depth of 4,768. We subsequently quantify the cipher’s vulnerability to Grover’s key-search algorithm under the NIST PQC security constraint M A X D E P T H MAXDEPTH . By constructing Grover oracles using inner parallelization with multiple plaintext-ciphertext pairs to suppress false positives, we demonstrate total quantum attack costs of approximately 2 94 for MIBS-64 and 2 111 for MIBS-80. These values fall below NIST’s Level-1 security threshold (2 170 ), confirming the susceptibility of both MIBS variants to quantum key-recovery attacks despite their classical lightweight efficiency.
Abstract Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetric cryptography currently in use. Most attacks on these cryptosystems can be reduced to the shortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oracle model from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on the GaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle is proposed and analyzed. Two implementations of the new quantum oracle model are proposed and estimated. The complexity of implementing the new quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. Comparison of obtained results for new and existing models of quantum oracle is given.