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

International Conference on Ubiquitous and Future Networks

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

Yeonsong Suh, Younghoon Park

Published Jul 8, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/icufn65838.2025.11169923

Related papers

Grover on Scrypt

Gyeongju Song, Hwajeong Seo

This paper presents an optimized quantum circuit for the scrypt cryptographic algorithm. We applied various optimization techniques to reduce the DW cost, which is the product of the time and space complexity of quantum circuits. In our proposed method, the number of ancilla qubits was significantly reduced through the use of optimized inverse operations, while the depth was minimized by implementing parallel structures. For the SHA-256, we devised a structure that achieves a substantial reduction in the number of ancilla qubits with only a slight increase in quantum circuit depth. By cleaning the dirty ancilla qubits used in the previous round through inverse operations, we enabled their reuse in each subsequent round. Specifically, we reduced the number of 8128 ancilla qubits, achieving this with an increase of only 6 in the full depth of the quantum circuit. Additionally, within Salsa20/8 in SMix, we reused qubits through inverse operations and performed some operations in parallel to reduce both the number of qubits and the overall quantum circuit depth. Finally, our quantum circuit for scrypt demonstrates a significant reduction in the width (the number of qubits) with only a minimal increase in the full quantum circuit depth.

Electronics•Aug 10, 2024•1 citation

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

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

A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with Grover’s Algorithm

Gyeongju Song, Kyungbae Jang, Hyunji Kim +1 more

Grover’s search algorithm accelerates the key search on the symmetric key cipher and the pre-image attack on the hash function. To conduct Grover’s search algorithm, the target cipher algorithm should be efficiently implemented in a quantum circuit. Currently, small quantum computers are difficult to operate with large quantum circuits due to limited performance. Therefore, if a large quantum computer that can operate Grover’s algorithm appears, it is expected that a cipher attack will be possible. In this paper, we propose a parallel structure quantum circuit for the Korean hash function standard (i.e., LSH). The proposed quantum circuit designed a parallel operation structure for the message expansion (i.e., MsgExp) function and the mix function, which are the internal structures of the LSH hash function. This approach shows an efficient result for quantum circuit implementation in terms of quantum resources by reducing the depth of the quantum circuit by about 96% through the trade-off of appropriate quantum resources compared to previous work. This result can be a reference for the implementation of a parallel quantum circuit in the future and is expected to advance the attack timing of the search algorithm for Grover’s LSH hash function.

Applied Sciences•Oct 27, 2022•6 citations

Resource-Constrained Quantum Implementation and Analysis of Mini-AES Cipher

Syed Shahmir, Ghulam Murtaza, Elmahdi Bentafat +4 more

Quantum search algorithms, such as Grover's algorithm, will soon pose a threat to current encryption standards as quantum computing advances toward practical implementation. These algorithms rely on quantum circuits that map cryptographic algorithms into appropriate Hilbert spaces, thus linking algorithmic inputs and outputs through quantum superposition. However, implementing and testing such circuits on existing quantum simulators, such as Qiskit, encounters significant memory and computational bottlenecks that limit research progress. To address these simulation constraints, we present a resource-optimized quantum circuit implementation of a complete two-round Mini-AES encryption algorithm. Our approach systematically converts the cipher's algebraic structure using algebraic normal form (ANF) equations, mapping XOR operations to CNOT gates and AND operations to Toffoli gates. To reduce memory overhead, we implement an ancilla-reuse strategy utilizing mid-circuit measurements and resets. Additionally, we introduce an automated procedure that generates Qiskitcompatible quantum circuits for arbitrary S-boxes and cryptographic primitives, streamlining the development of quantum cryptanalysis implementations. Our implementation achieves full encryption and decryption in a quantum circuit with modest gate requirements that can be achieved by the current or near-future state of the art quantum computers. In addition, we provide system utilization metrics to validate our resource-constrained implementation. This compact and pedagogically accessible implementation establishes a practical foundation for quantum cryptanalysis research and post-quantum cryptographic analysis.

arXiv:2503.06566•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•0 citations

Depth-Optimized Quantum Circuit of Gauss–Jordan Elimination

Kyungbae Jang, Yujin Oh, Hwajeong Seo

Quantum computers have the capacity to solve certain complex problems more efficiently than classical computers. To fully leverage these quantum advantages, adapting classical arithmetic for quantum systems in a circuit level is essential. In this paper, we introduce a depth-optimized quantum circuit of Gauss–Jordan elimination for matrices in binary. This quantum circuit is a crucial module for accelerating Information Set Decoding (ISD) using Grover’s algorithm. ISD is a cryptographic technique used in analyzing code-based cryptographic algorithms. When combined with Grover’s search, it achieves a square root reduction in complexity. The proposed method emphasizes the potential for parallelization in the quantum circuit implementation of Gauss–Jordan elimination. We allocate additional ancilla qubits to enable parallel operations within the target matrix and further reuse these ancilla qubits to minimize overhead from our additional allocation. The proposed quantum circuit for Gauss–Jordan elimination achieves the lowest Toffoli depth compared to the-state-of-art previous works.

Applied Sciences•Sep 24, 2024•5 citations
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.
This paper presents an optimized quantum circuit for the scrypt cryptographic algorithm. We applied various optimization techniques to reduce the DW cost, which is the product of the time and space complexity of quantum circuits. In our proposed method, the number of ancilla qubits was significantly reduced through the use of optimized inverse operations, while the depth was minimized by implementing parallel structures. For the SHA-256, we devised a structure that achieves a substantial reduction in the number of ancilla qubits with only a slight increase in quantum circuit depth. By cleaning the dirty ancilla qubits used in the previous round through inverse operations, we enabled their reuse in each subsequent round. Specifically, we reduced the number of 8128 ancilla qubits, achieving this with an increase of only 6 in the full depth of the quantum circuit. Additionally, within Salsa20/8 in SMix, we reused qubits through inverse operations and performed some operations in parallel to reduce both the number of qubits and the overall quantum circuit depth. Finally, our quantum circuit for scrypt demonstrates a significant reduction in the width (the number of qubits) with only a minimal increase in the full quantum circuit depth.
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.
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.
Grover’s search algorithm accelerates the key search on the symmetric key cipher and the pre-image attack on the hash function. To conduct Grover’s search algorithm, the target cipher algorithm should be efficiently implemented in a quantum circuit. Currently, small quantum computers are difficult to operate with large quantum circuits due to limited performance. Therefore, if a large quantum computer that can operate Grover’s algorithm appears, it is expected that a cipher attack will be possible. In this paper, we propose a parallel structure quantum circuit for the Korean hash function standard (i.e., LSH). The proposed quantum circuit designed a parallel operation structure for the message expansion (i.e., MsgExp) function and the mix function, which are the internal structures of the LSH hash function. This approach shows an efficient result for quantum circuit implementation in terms of quantum resources by reducing the depth of the quantum circuit by about 96% through the trade-off of appropriate quantum resources compared to previous work. This result can be a reference for the implementation of a parallel quantum circuit in the future and is expected to advance the attack timing of the search algorithm for Grover’s LSH hash function.
Quantum search algorithms, such as Grover's algorithm, will soon pose a threat to current encryption standards as quantum computing advances toward practical implementation. These algorithms rely on quantum circuits that map cryptographic algorithms into appropriate Hilbert spaces, thus linking algorithmic inputs and outputs through quantum superposition. However, implementing and testing such circuits on existing quantum simulators, such as Qiskit, encounters significant memory and computational bottlenecks that limit research progress. To address these simulation constraints, we present a resource-optimized quantum circuit implementation of a complete two-round Mini-AES encryption algorithm. Our approach systematically converts the cipher's algebraic structure using algebraic normal form (ANF) equations, mapping XOR operations to CNOT gates and AND operations to Toffoli gates. To reduce memory overhead, we implement an ancilla-reuse strategy utilizing mid-circuit measurements and resets. Additionally, we introduce an automated procedure that generates Qiskitcompatible quantum circuits for arbitrary S-boxes and cryptographic primitives, streamlining the development of quantum cryptanalysis implementations. Our implementation achieves full encryption and decryption in a quantum circuit with modest gate requirements that can be achieved by the current or near-future state of the art quantum computers. In addition, we provide system utilization metrics to validate our resource-constrained implementation. This compact and pedagogically accessible implementation establishes a practical foundation for quantum cryptanalysis research and post-quantum cryptographic analysis.
Quantum computers have the capacity to solve certain complex problems more efficiently than classical computers. To fully leverage these quantum advantages, adapting classical arithmetic for quantum systems in a circuit level is essential. In this paper, we introduce a depth-optimized quantum circuit of Gauss–Jordan elimination for matrices in binary. This quantum circuit is a crucial module for accelerating Information Set Decoding (ISD) using Grover’s algorithm. ISD is a cryptographic technique used in analyzing code-based cryptographic algorithms. When combined with Grover’s search, it achieves a square root reduction in complexity. The proposed method emphasizes the potential for parallelization in the quantum circuit implementation of Gauss–Jordan elimination. We allocate additional ancilla qubits to enable parallel operations within the target matrix and further reuse these ancilla qubits to minimize overhead from our additional allocation. The proposed quantum circuit for Gauss–Jordan elimination achieves the lowest Toffoli depth compared to the-state-of-art previous works.