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 Symposium on Information Theory and its Applications

Complexity of Solving Hash Puzzles Using Revised Boyer Quantum Algorithm

Chris Idota, Yuichi Kaji

Published Nov 10, 2024• 0 citations
Publisher

Abstract

This study investigates the computational complexity of solving hash puzzles using quantum algorithms. A hash puzzle is formalized as a problem for finding a pre-image whose hash value falls within a specified target set. It is known that Grover quantum search algorithm and Boyer algorithm, which is a Bayesian utilization of Grover algorithm, can compute the preimage of a given hash value more efficiently than non-quantum algorithms. However, those quantum algorithms use implicit assumptions and approximations that are not compatible with a general hash puzzle. This study revises Boyer algorithm by excluding those assumptions and approximations, and clarifies the relation between the size of the target set of a hash puzzle and the complexity necessary for solving the puzzle. It is shown that, in the quantum framework, a hash puzzle with fewer targets can be easier to solve than a hash puzzle with more targets, which contradicts to the classical understanding where puzzles with fewer targets are more difficult to solve.

DOI
10.23919/isita60732.2024.10858248

Related papers

Quantum Cryptanalysis of Affine Cipher

Mahima Mary Mathews, V. Panchami, Vishnu Ajith

Quantum Algorithms reduce the computational complexity or solve certain difficult problems that were originally impossible to solve with classical computers. Grover’s search algorithm is a Quantum computation algorithm that can find target elements from a set of unstructured data with the best possible,$O(\sqrt {N})$queries. Grover’s search Quantum circuits implemented accurately can be used to successfully search and find the keys of Symmetric ciphers. However, very few demonstrations of such practical cryptanalysis are available. In this paper, practical Quantum cryptanalysis circuits for Affine Cipher are proposed and demonstrated, that successfully break the cipher by finding the keys.

IEEE Journal on Emerging and Selected Topics in Circuits and Systems•Jul 15, 2024•4 citations

Classical Equivalent Quantum Based Pattern Matching Algorithms

Kapil Kumar Soni, Akhtar Rasool

The pattern matching problem is imperative in diversified field of computer science, and it finds occurrences of the pattern string(s) of any arbitrary length “M” in the large text string of length “N”. Since past decades the solutions to a problem have been suggesting through efficient algorithms. Classical benchmark algorithms such as Knuth Morris Pratt and Boyer Moore locates such solution in O(N) time, equivalent quantum algorithms can utilize quantum computations which are inherently parallel and obtains computational speedup by providing the solution in O(√N) time. The quantum pattern matching algorithm uses Grover's search logic that finds an element existence in the large unstructured text data of “N” items in O(√N) time, instead classically it takes O(N) time. The article comprises of introductory pattern matching tactics, quantum basics, Grover's search method, quantum based pattern matching algorithms, their illustration followed by complexity analysis, and finally concludes with the possible algorithmic variations and relevant applications.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•0 citations

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

Quantum Computing Algorithms for Solving Complex Mathematical Problems

Et al. Lalit Mohan Trivedi

The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.

International Journal on Recent and Innovation Trends in Computing and Communication•Nov 7, 2023•2 citations

Quantum Implementation and Analysis of SHA-2 and SHA-3

Kyungbae Jang, Sejin Lim, Yujin Oh +4 more

Quantum computers have the potential to solve a number of hard problems that are believed to be almost impossible to solve by classical computers. This observation has sparked a surge of research to apply quantum algorithms against the cryptographic systems to evaluate its quantum resistance. In assessing the security strength of the cryptographic algorithms against the upcoming quantum threats, it is crucial to precisely estimate the quantum resource requirement (generally in terms of circuit depth and quantum bit count). The National Institute of Standards and Technology by the US government specified five quantum security levels so that the relative quantum strength of a given cipher can be compared to the standard ones. There have been some progress in the NIST-specified quantum security levels for the odd levels (i.e., 1, 3 and 5), following the work of Jaques et al. (Eurocrypt’20). However, levels 2 and 4, which correspond to the quantum collision finding attacks for the SHA-2 and SHA-3 hash functions, quantum attack complexities are arguably not well-studied. This is where our article fits in. In this article, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.

IEEE Transactions on Emerging Topics in Computing•Mar 7, 2025•24 citations

On New Quantum Search Algorithms and Complexity of NP-Complete Problems

Dhananjay P. Mehendale

We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!

•Jul 1, 2016•0 citations
This study investigates the computational complexity of solving hash puzzles using quantum algorithms. A hash puzzle is formalized as a problem for finding a pre-image whose hash value falls within a specified target set. It is known that Grover quantum search algorithm and Boyer algorithm, which is a Bayesian utilization of Grover algorithm, can compute the preimage of a given hash value more efficiently than non-quantum algorithms. However, those quantum algorithms use implicit assumptions and approximations that are not compatible with a general hash puzzle. This study revises Boyer algorithm by excluding those assumptions and approximations, and clarifies the relation between the size of the target set of a hash puzzle and the complexity necessary for solving the puzzle. It is shown that, in the quantum framework, a hash puzzle with fewer targets can be easier to solve than a hash puzzle with more targets, which contradicts to the classical understanding where puzzles with fewer targets are more difficult to solve.
Quantum Algorithms reduce the computational complexity or solve certain difficult problems that were originally impossible to solve with classical computers. Grover’s search algorithm is a Quantum computation algorithm that can find target elements from a set of unstructured data with the best possible,O(N)O(\sqrt {N})O(N​)queries. Grover’s search Quantum circuits implemented accurately can be used to successfully search and find the keys of Symmetric ciphers. However, very few demonstrations of such practical cryptanalysis are available. In this paper, practical Quantum cryptanalysis circuits for Affine Cipher are proposed and demonstrated, that successfully break the cipher by finding the keys.
The pattern matching problem is imperative in diversified field of computer science, and it finds occurrences of the pattern string(s) of any arbitrary length “M” in the large text string of length “N”. Since past decades the solutions to a problem have been suggesting through efficient algorithms. Classical benchmark algorithms such as Knuth Morris Pratt and Boyer Moore locates such solution in O(N) time, equivalent quantum algorithms can utilize quantum computations which are inherently parallel and obtains computational speedup by providing the solution in O(√N) time. The quantum pattern matching algorithm uses Grover's search logic that finds an element existence in the large unstructured text data of “N” items in O(√N) time, instead classically it takes O(N) time. The article comprises of introductory pattern matching tactics, quantum basics, Grover's search method, quantum based pattern matching algorithms, their illustration followed by complexity analysis, and finally concludes with the possible algorithmic variations and relevant applications.
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 power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.
Quantum computers have the potential to solve a number of hard problems that are believed to be almost impossible to solve by classical computers. This observation has sparked a surge of research to apply quantum algorithms against the cryptographic systems to evaluate its quantum resistance. In assessing the security strength of the cryptographic algorithms against the upcoming quantum threats, it is crucial to precisely estimate the quantum resource requirement (generally in terms of circuit depth and quantum bit count). The National Institute of Standards and Technology by the US government specified five quantum security levels so that the relative quantum strength of a given cipher can be compared to the standard ones. There have been some progress in the NIST-specified quantum security levels for the odd levels (i.e., 1, 3 and 5), following the work of Jaques et al. (Eurocrypt’20). However, levels 2 and 4, which correspond to the quantum collision finding attacks for the SHA-2 and SHA-3 hash functions, quantum attack complexities are arguably not well-studied. This is where our article fits in. In this article, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.
We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!