Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2512.14759

Quantum Resource Analysis of Low-Round Keccak/SHA-3 Preimage Attack: From Classical 2^57.8 to Quantum 2^28.9 using Qiskit Modeling

Ramin Rezvani Gilkolae

quant-phcs.CRSubmitted Dec 15, 2025• Announced Dec 16, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

Applying Grover's Algorithm to Hash Functions: A Software Perspective

Richard H. Preston

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.

arXiv:2202.10982•IEEE Transactions on Quantum Engineering•Jan 1, 2022•38 citations

A framework for reducing the overhead of the quantum oracle for use with Grover’s algorithm with applications to cryptanalysis of SIKE

Jean‐François Biasse, Benjamin Pring

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].

Journal of Mathematical Cryptology•Nov 17, 2020•9 citations

Resource-Efficient Reversible Quantum Circuit for Theta Function in SHA-3

Yeonsong Suh, Younghoon Park

With the advancement of quantum computing, traditional hash based security structures are increasingly exposed to threats posed by quantum algorithms. In particular, Grover's algorithm enables significantly faster pre-image attacks on hash functions than classical approaches, highlighting the need for circuit-level quantum countermeasures. To break with quantum computer, implementation of quantum circuit for the hash function is essential. However, the existing approaches require too many gates or discard ancilla qubits. In this paper, we propose a reversible quantum circuit for the$\theta$operation in the Keccak algorithm a core component of SHA-3, by explicitly implementing the inverse function$\theta^{-1}$. The proposed circuit allows for ancilla qubit reuse and achieves a substantial reduction in number of CNOT gates and qubits compare to previous researches. While the depth of our circuit slightly exceeds that of some existing approaches, the compact and modular design of the$\theta$operation provides a solid foundation for further enhancement.

International Conference on Ubiquitous and Future Networks•Jul 8, 2025•0 citations

Improved Quantum Cryptanalysis of MD5 and SHA-1

Kyungbae Jang, Hwajeong Seo, Anupam Chattopadhyay

MD5 and SHA-1 are widely studied hash functions in cryptanalysis, owing to their well-structured round functions and historical significance in cryptography. This paper presents improved quantum circuit implementations of MD5 and SHA-1 specifically optimized for quantum cryptanalysis. We reduce the quantum implementation cost of auxiliary functions and eliminate the use of ancilla qubits, while reducing circuit depth (the number of sequential gate layers) by parallelizing multiple additions in the round operations of MD5 and SHA-1. Additionally, the quantum implementations of MD5 and SHA-1 are optimized by considering a fixed input size under the attack scenario. The proposed implementations achieve a 63% improvement in the depth - qubit count metric for MD5 and a 27% improvement for SHA-1 compared to previous works. By providing reduced quantum resources, this work establishes an improved baseline for the quantum cryptanalysis of MD5 and SHA-1. We analyze quantum attacks on MD5 and SHA-1, showing that the preimage attacks require a full depth of 279 and 296 for MD5 and SHA-1, respectively, while the collision attacks require a full depth of 254 and 264. For a realistic evaluation, we also estimate the quantum resources for fault-tolerant quantum computation, including the number of physical qubits and the runtime, to break MD5 and SHA-1.

IEEE Access•Jan 1, 2026•0 citations

Quantum cryptanalysis of SPN ciphers with known plaintext

Uroosa Kiran, Aneela Safdar, Saif Ullah Khalid +2 more

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.

npj Quantum Information•Apr 1, 2026•0 citations

Quantum search for scaled hash function preimages

Sergi Ramos-Calderer, Emanuele Bellini, José Ignacio Latorre +2 more

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.

arXiv:2009.00621•Quantum Information Processing•May 1, 2021•22 citations
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.
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.
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)O\left(2^{n/2}\cdot mC\right)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)O(2^{n/2} \cdot m\sqrt{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].
With the advancement of quantum computing, traditional hash based security structures are increasingly exposed to threats posed by quantum algorithms. In particular, Grover's algorithm enables significantly faster pre-image attacks on hash functions than classical approaches, highlighting the need for circuit-level quantum countermeasures. To break with quantum computer, implementation of quantum circuit for the hash function is essential. However, the existing approaches require too many gates or discard ancilla qubits. In this paper, we propose a reversible quantum circuit for theθ\thetaθoperation in the Keccak algorithm a core component of SHA-3, by explicitly implementing the inverse functionθ−1\theta^{-1}θ−1. The proposed circuit allows for ancilla qubit reuse and achieves a substantial reduction in number of CNOT gates and qubits compare to previous researches. While the depth of our circuit slightly exceeds that of some existing approaches, the compact and modular design of theθ\thetaθoperation provides a solid foundation for further enhancement.
MD5 and SHA-1 are widely studied hash functions in cryptanalysis, owing to their well-structured round functions and historical significance in cryptography. This paper presents improved quantum circuit implementations of MD5 and SHA-1 specifically optimized for quantum cryptanalysis. We reduce the quantum implementation cost of auxiliary functions and eliminate the use of ancilla qubits, while reducing circuit depth (the number of sequential gate layers) by parallelizing multiple additions in the round operations of MD5 and SHA-1. Additionally, the quantum implementations of MD5 and SHA-1 are optimized by considering a fixed input size under the attack scenario. The proposed implementations achieve a 63% improvement in the depth - qubit count metric for MD5 and a 27% improvement for SHA-1 compared to previous works. By providing reduced quantum resources, this work establishes an improved baseline for the quantum cryptanalysis of MD5 and SHA-1. We analyze quantum attacks on MD5 and SHA-1, showing that the preimage attacks require a full depth of 279 and 296 for MD5 and SHA-1, respectively, while the collision attacks require a full depth of 254 and 264. For a realistic evaluation, we also estimate the quantum resources for fault-tolerant quantum computation, including the number of physical qubits and the runtime, to break MD5 and SHA-1.
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.
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.