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\left(2^{n/2}\cdot mC\right)$ (where C originates from the cost of implementing the quantum oracle) to O ( 2 n / 2 ⋅ m C ) $O(2^{n/2} \cdot m\sqrt{C})$ 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].
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].
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024
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.
The advancement of quantum computing poses emerging challenges to cryptographic hash functions that underpin modern cyber defense systems. In particular, Grover’s algorithm theoretically offers a quadratic speedup for preimage search, potentially reducing the effective security margin of hash-based primitives used to protect long-lived strategic data. This study adopts a structure-oriented perspective to analyze ARX-like and sponge-like hash constructions using Grover-based oracle modeling. Reversible toy hash abstractions are employed to construct quantum oracles and simulate Grover attacks under both ideal (noise-free) and Noisy Intermediate-Scale Quantum (NISQ) conditions. The analysis evaluates success probability, oracle cost, and noise sensitivity. Results show non-monotonic amplitude amplification under ideal conditions, with structural differences affecting phase behavior. However, under realistic noise, amplitude amplification is significantly attenuated for both constructions, limiting practical quantum advantage. The findings further show that oracle complexity, reflected in circuit depth and multi-qubit gate usage, plays a dominant role in determining attack feasibility beyond asymptotic complexity reductions. This work provides a structure-level framework for assessing quantum risks to cryptographic hash functions and supports informed post-quantum cyber defense planning.
Grover search algorithm is the most representative quantum attack method that threatens the security of symmetric key cryptography. If the Grover search algorithm is applied to symmetric key cryptography, the security level of target symmetric key cryptography can be lowered from n-bit to n2-bit. When applying Grover’s search algorithm to the block cipher that is the target of potential quantum attacks, the target block cipher must be implemented as quantum circuits. Starting with the AES block cipher, a number of works have been conducted to optimize and implement target block ciphers into quantum circuits. Recently, many studies have been published to implement lightweight block ciphers as quantum circuits. In this paper, we present optimal quantum circuit designs of symmetric key cryptography, including PRESENT and GIFT block ciphers. The proposed method optimized PRESENT and GIFT block ciphers by minimizing qubits, quantum gates, and circuit depth. We compare proposed PRESENT and GIFT quantum circuits with other results of lightweight block cipher implementations in quantum circuits. Finally, quantum resources of PRESENT and GIFT block ciphers required for the oracle of the Grover search algorithm were estimated.
Key recovery attack on SPN ciphers such as AES is NP hard in complexity. Previous studies have estimated the quantum resources required for implementing Grover’s key search for AES, but these are largely theoretical in nature. The key challenges to implement Grover’s algorithm on current quantum hardware include the number of available qubits, noise, and decoherence. However, the rapid advancement of hardware has brought us closer to practical realization for the cryptanalysis of light-weight SPN ciphers. This study presents an efficient quantum circuit implementation of Mini-AES, a 16-bit variant of AES, employing standard CNOT and Toffoli gates. To the best of our knowledge, our work provides the first complete quantum implementations of all core Mini-AES components for the quantum oracle. The effects of noise are emulated for each module of the quantum oracle and quantified. Furthermore, Grover’s algorithm is applied to Mini-AES to perform successful key recovery through a known-plaintext attack, demonstrating significant amplitude amplification while using near-optimal Grover’s iterations, thereby reducing the total quantum volume. The optimal Grover’s iterations have been obtained empirically as well as validated with finite-shot analysis. Notably, the application of Grover’s algorithm reveals key clustering behavior in Mini-AES, which has been corroborated through classical simulation.
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.