Quantum software frameworks provide software engineers with the tools to study quantum algorithms as applied to practical problems. We implement classical hash functions MD5, SHA-1, SHA-2, and SHA-3 as quantum oracles to study the computational resource requirements of conducting a preimage attack with Grover's Algorithm. We introduce an improvement to the SHA-3 oracle that reduces the number of logical qubits required in the Keccak block permutation by 40%. The source code is available athttps://github.com/rhpreston/grovers-hash-functions.
Quantum software frameworks provide software engineers with the tools to study quantum algorithms as applied to practical problems. We implement classical hash functions MD5, SHA-1, SHA-2, and SHA-3 as quantum oracles to study the computational resource requirements of conducting a preimage attack with Grover's Algorithm. We introduce an improvement to the SHA-3 oracle that reduces the number of logical qubits required in the Keccak block permutation by 40%. The source code is available athttps://github.com/rhpreston/grovers-hash-functions.
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.
Abstract We present the implementation of Grover’s algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions, whose design only uses modular addition, word rotation and bitwise exclusive or. Our implementation provides the means to assess with precision the scaling of the number of gates and depth of a full-fledged quantum circuit designed to find the preimages of a given hash digest. The detailed construction of the quantum oracle shows that the presence of AND gates, OR gates, shifts of bits and the reuse of the initial state along the computation require extra quantum resources as compared with other hash functions based on modular additions, XOR gates and rotations. We also track the entanglement entropy present in the quantum register at every step along the computation, showing that it becomes maximal at the inner core of the first action of the quantum oracle, which implies that no classical simulation based on tensor networks would be of relevance. Finally, we show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover’s algorithm can only provide some marginal practical advantage in terms of error mitigation.
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].
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.
Cryptographic hash functions are important building blocks of many security systems. A preimage attack on hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage. The current paper presents a new quantum algorithm for hash preimage attacks, which can break the preimage resistance with circuit complexity O(2n/3) using O(2n/3) running times, where n is the input bit length of the hash function. The quantum circuit complexity is apparently reduced from O(2n/2) to O(2n/3) at the cost of O(2n/3) running times requirements compared with the existing algorithms.
The rapid advancement of quantum computing presents a fundamental challenge to modern cryptographic security, particularly in the domain of hash functions that ensure data integrity, authentication, and blockchain security. Traditional crypto graphic hash functions such as SHA-256, SHA-3, and BLAKE2 rely on computational hardness assumptions that become obsolete in the presence of large-scale quantum computers. Shor’s algorithm can efficiently break RSA and ECC-based cryptosys tems, while Grover’s algorithm reduces the security of traditional hash functions by square root complexity, significantly weakening their preimage and collision resistance. This quantum threat necessitates the development of post-quantum secure hashing techniques that remain resilient against both classical and quantum adversaries. This paper proposes Quantum Hashing, a novel cryptographic framework that integrates quantum entanglement, lattice-based cryptography, and hybrid quantum classical hashing to construct post-quantum secure hash functions. We introduce a formal model for Quantum Collision Resistance (QCR) and provide entropy-based ran domness enhancement to ensure unpredictable hash outputs. Unlike classical hashing approaches, our framework leverages the hardness of lattice problems (e.g., Shortest Vector Problem, Learning with Errors) to withstand quantum attacks while incorpo rating Quantum Key Distribution (QKD) mechanisms to enhance entropy and key management. Furthermore, we evaluate the security of Quantum Hashing under various attack models, comparing its resistance against Grover’s search and collision attacks. We benchmark its performance against NIST Post-Quantum Cryptography (PQC) final ists, including CRYSTALS-DILITHIUM, SPHINCS+, and Falcon, demonstrating that our approach offers superior resilience while maintaining computational feasibility. Additionally, we present an implementation of Quantum Hashing using Qiskit, show casing its practical applicability in quantum circuits and quantum-secure blockchain architectures. Our findings highlight that Quantum Hashing provides a scalable, entropy-efficient, and post-quantum resilient cryptographic primitive suitable for next-generation cryptographic applications. This work paves the way for secure post-quantum digital signatures, blockchain consensus mechanisms, and zero-knowledge proof systems that require tamper-resistant hashing in a quantum computing era.