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:2009.00621 · Quantum Information Processing

Quantum search for scaled hash function preimages

Sergi Ramos-Calderer, Emanuele Bellini, José Ignacio Latorre, Marc Manzano, Víctor Mateu

Published May 1, 2021• 22 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s11128-021-03118-9

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•46 citations

Assessing Quantum Threats to Cryptographic Hash Structures in Cyber Defense Systems Using Grover Based Oracle Modeling

Santi Amalia Ar-Nur, Teddy Mantoro

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.

International Conference on Frontiers of Engineering and Emerging Technologies (FET)•Apr 22, 2026•0 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

On quantum preimage attacks

Răzvan Roşie

We propose a preimage attack against cryptographic hash functions based on the speedup enabled by quantum computing. Preimage resistance is a fundamental property cryptographic hash functions must possess. The motivation behind this work relies in the lack of conventional attacks against newly introduced hash schemes such as the recently elected SHA-3 standard. The proposed algorithm consists of two parts: a classical one running in O(log |S|), where S represents the searched space, and a quantum part that contains the bulk of the Deutsch-Jozsa circuit. The mixed approach we follow makes use of the quantum parallelism concept to check the existence of an argument (preimage) for a given hash value (image) in the preestablished search space. For this purpose, we explain how a non-unitary measurement gate can be used to determine if S contains the target value. Our method is entirely theoretical and is based on the assumptions that a hash function can be implemented by a quantum computer and the key measurement gate we describe is physically realizable. Finally, we present how the algorithm finds a solution on S.

arXiv:1412.3164•Dec 10, 2014•0 citations

Practical Guide to Using a Quantum Computer (Based on Materials from the International Quantum Center at CERN, Switzerland) # 7

Mikhail Pavlov

Abstract This laboratory work presents a practical implementation of Grover’s search algorithm using the Qiskit framework. The material is based on educational resources developed by the International Quantum Center at CERN (Switzerland) and is intended to provide hands-on experience with amplitude amplification and oracle-based quantum search. In Laboratory Work No. 7, participants construct Grover’s algorithm step by step. The implementation begins with defining a function that initializes the quantum registers and prepares the initial stage of the circuit. The output qubit associated with the oracle is set to the state ∣1⟩|1\rangle∣1⟩ to enable phase inversion through the phase kickback mechanism. Hadamard gates are then applied to create a uniform superposition over the search space. The oracle is designed to mark the target state by applying a phase shift, effectively flipping the sign of the amplitude corresponding to the solution. This is followed by the diffusion operator (inversion about the mean), which amplifies the probability amplitude of the marked state. The Grover iteration—composed of the oracle and diffusion operator—is repeated an optimal number of times to maximize the probability of measuring the correct result. The laboratory exercise emphasizes the principles of quantum amplitude amplification, circuit modularization, oracle construction, and measurement-based verification. By executing the algorithm on simulators and cloud-accessible quantum hardware, participants observe the quadratic speedup of Grover’s algorithm compared to classical linear search methods. This practical guide bridges theoretical understanding of quantum search with executable quantum circuits, reinforcing the operational aspects of quantum algorithm design within modern quantum computing

•Mar 3, 2026•0 citations

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

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.

quant-pharXiv:2512.14759•Dec 16, 2025•0 citations
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.
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.
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.
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].
We propose a preimage attack against cryptographic hash functions based on the speedup enabled by quantum computing. Preimage resistance is a fundamental property cryptographic hash functions must possess. The motivation behind this work relies in the lack of conventional attacks against newly introduced hash schemes such as the recently elected SHA-3 standard. The proposed algorithm consists of two parts: a classical one running in O(log |S|), where S represents the searched space, and a quantum part that contains the bulk of the Deutsch-Jozsa circuit. The mixed approach we follow makes use of the quantum parallelism concept to check the existence of an argument (preimage) for a given hash value (image) in the preestablished search space. For this purpose, we explain how a non-unitary measurement gate can be used to determine if S contains the target value. Our method is entirely theoretical and is based on the assumptions that a hash function can be implemented by a quantum computer and the key measurement gate we describe is physically realizable. Finally, we present how the algorithm finds a solution on S.
Abstract This laboratory work presents a practical implementation of Grover’s search algorithm using the Qiskit framework. The material is based on educational resources developed by the International Quantum Center at CERN (Switzerland) and is intended to provide hands-on experience with amplitude amplification and oracle-based quantum search. In Laboratory Work No. 7, participants construct Grover’s algorithm step by step. The implementation begins with defining a function that initializes the quantum registers and prepares the initial stage of the circuit. The output qubit associated with the oracle is set to the state ∣1⟩|1\rangle∣1⟩ to enable phase inversion through the phase kickback mechanism. Hadamard gates are then applied to create a uniform superposition over the search space. The oracle is designed to mark the target state by applying a phase shift, effectively flipping the sign of the amplitude corresponding to the solution. This is followed by the diffusion operator (inversion about the mean), which amplifies the probability amplitude of the marked state. The Grover iteration—composed of the oracle and diffusion operator—is repeated an optimal number of times to maximize the probability of measuring the correct result. The laboratory exercise emphasizes the principles of quantum amplitude amplification, circuit modularization, oracle construction, and measurement-based verification. By executing the algorithm on simulators and cloud-accessible quantum hardware, participants observe the quadratic speedup of Grover’s algorithm compared to classical linear search methods. This practical guide bridges theoretical understanding of quantum search with executable quantum circuits, reinforcing the operational aspects of quantum algorithm design within modern quantum computing
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.