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 Cryptography and Information Security (VCRIS)

Implementation of the BHT quantum algorithm for finding collisions of a lightweight hash function on IBM “Sherbrooke” via Qiskit

Nghi Nguyen Van, Minh Thang Vu, Hanh Tran Thi, Nam Hai Ngo, Ba Linh Vu, Van Duan Nguyen

Published Oct 30, 2025• 0 citations
Publisher

Abstract

The Brassard–Høyer–Tapp (BHT) algorithm, introduced in 1997, demonstrates that cryptographic-hash collisions can be located with lower computational cost than classical brute-force search. Yet, no experimental realization of BHT for hash-function cryptanalysis on an actual quantum processor has been reported. In this paper, we present practical implementation and in-depth analysis of BHT applied to a lightweight cryptographic hash on IBM’s quantum hardware. Using Qiskit, we design the quantum circuit for the target hash and embed the BHT subroutines. Our results quantify both the algorithmic complexity and the number of qubit required for successful collision discovery, and they provide a roadmap for extending the technique to real-world hash functions once quantum resources scale to the necessary size.

DOI
10.1109/vcris68011.2025.11250564

Related papers

Cost analysis of hash collisions : will quantum computers make SHARCS obsolete?

Daniel J. Bernstein

Current proposals for special-purpose factorization hardware will become obsolete if large quantum computers are built: the number-field sieve scales much more poorly than Shor's quantum algorithm for factorization. Will all special-purpose cryptanalytic hardware become obsolete in a post-quantum world?\nA quantum algorithm by Brassard, HØyer, and Tapp has frequently been claimed to reduce the cost of b-bit hash collisions from 2^b/2 to 2^b/3.\nThis paper analyzes the Brassard-HØyer-Tapp algorithm and shows that it has fundamentally worse price-performance ratio than the classical van Oorschot-Wiener hash-collision circuits, even under optimistic assumptions regarding the speed of quantum computers.

•Jan 1, 2009•61 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

An Efficient Quantum cryptanalysis of lightweight hash function - PHOTON-Beetle

Swamy Naidu Allu, Appala Naidu Tentu, Gangadhara Rao Kancharla

Quantum cryptanalysis methods are used to crack the majority of symmetric key ciphers. With this knowledge, cryptologists should be able to create post-quantum symmetric ciphers by incorporating these new quantum cryptanalysis techniques into their toolkit. Secure communication is crucial for applications related to the Internet of Things (IoT) to avoid cyberattacks. Cryptographic hash functions can be used to protect data integrity. The development of large-scale, fault-tolerant quantum computers is the most significant challenge. Recent techniques to attack symmetric key schemes can be achieved by using the Pre-image attack method, Simon’s algorithm, or by combining Simon’s and Grover’s algorithms. In this study, we explored some of the most recent methods for quantum cryptanalysis of symmetric key ciphers. Firstly, we discussed the design of quantum cryptanalysis methods, along with the advantages over classical procedures. In this paper, we illustrate the implementation of the NIST-standard lightweight hash function PHOTON-Beetle on a Quantum Computer (using IBM Qiskit), which is mostly used in IoT devices. Efficient quantum implementation of PHOTON-Beetle is proposed in this paper. This paper calculates the quantum cost of PHOTON-Beetle for every layer and compares it with [1].

International Conference on Automation, Computing and Renewable Systems (ICACRS)•Dec 11, 2023•1 citation

Optimized Implementation and Analysis of CHAM in Quantum Computing

Yujin Yang, Kyungbae Jang, Anubhab Baksi +1 more

A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.

Applied Sciences•Apr 20, 2023•9 citations

Quantum lower bounds for the collision and the element distinctness problems

Scott Aaronson, Yaoyun Shi

Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f ( i ) = f ( j ), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an r -to-one function must evaluate the function Ω(( n / r ) 1/3 ) times, where n is the size of the domain and r | n . This matches an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of Ω( n 2/3 ) queries for the element distinctness problem, which is to determine whether n integers are all distinct. The best previous lower bound was Ω(√ n ) queries.

Journal of the ACM•Jul 1, 2004•353 citations

An Analaysis on Quantum Implementation ofLightweiht Hash Algorithm

Akkocaoğlu, Hande

The rapid advancements in quantum technologies have introduced significant threats to the security of conventional cryptographic systems. In particular, the evaluation of quantum resource requirements—measured in terms of circuit depth and qubit count—has become essential for analyzing the resilience of widely used schemes such as AES and RSA, as well as cryptographic hash functions like SHA-2. At the same time, the widespread adoption of Internet of Things (IoT) applications has increased the exposure to cybersecurity risks, which are further exacerbated by the emerging capabilities of quantum adversaries. To address these challenges, the U.S. National Institute of Standards and Technology (NIST) launched a competition to standardize lightweight hash functions and defined five quantum security levels to assess their robustness. In this work, we conduct a resource analysis of the NIST Lightweight Hash Function finalists against the Grover search algorithm, providing detailed insights into their quantum resistance. The findings contribute to a more comprehensive understanding of the security strength of lightweight hash functions in the post-quantum era.

•Sep 5, 2025•0 citations
The Brassard–Høyer–Tapp (BHT) algorithm, introduced in 1997, demonstrates that cryptographic-hash collisions can be located with lower computational cost than classical brute-force search. Yet, no experimental realization of BHT for hash-function cryptanalysis on an actual quantum processor has been reported. In this paper, we present practical implementation and in-depth analysis of BHT applied to a lightweight cryptographic hash on IBM’s quantum hardware. Using Qiskit, we design the quantum circuit for the target hash and embed the BHT subroutines. Our results quantify both the algorithmic complexity and the number of qubit required for successful collision discovery, and they provide a roadmap for extending the technique to real-world hash functions once quantum resources scale to the necessary size.
Current proposals for special-purpose factorization hardware will become obsolete if large quantum computers are built: the number-field sieve scales much more poorly than Shor's quantum algorithm for factorization. Will all special-purpose cryptanalytic hardware become obsolete in a post-quantum world?\nA quantum algorithm by Brassard, HØyer, and Tapp has frequently been claimed to reduce the cost of b-bit hash collisions from 2^b/2 to 2^b/3.\nThis paper analyzes the Brassard-HØyer-Tapp algorithm and shows that it has fundamentally worse price-performance ratio than the classical van Oorschot-Wiener hash-collision circuits, even under optimistic assumptions regarding the speed of quantum computers.
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.
Quantum cryptanalysis methods are used to crack the majority of symmetric key ciphers. With this knowledge, cryptologists should be able to create post-quantum symmetric ciphers by incorporating these new quantum cryptanalysis techniques into their toolkit. Secure communication is crucial for applications related to the Internet of Things (IoT) to avoid cyberattacks. Cryptographic hash functions can be used to protect data integrity. The development of large-scale, fault-tolerant quantum computers is the most significant challenge. Recent techniques to attack symmetric key schemes can be achieved by using the Pre-image attack method, Simon’s algorithm, or by combining Simon’s and Grover’s algorithms. In this study, we explored some of the most recent methods for quantum cryptanalysis of symmetric key ciphers. Firstly, we discussed the design of quantum cryptanalysis methods, along with the advantages over classical procedures. In this paper, we illustrate the implementation of the NIST-standard lightweight hash function PHOTON-Beetle on a Quantum Computer (using IBM Qiskit), which is mostly used in IoT devices. Efficient quantum implementation of PHOTON-Beetle is proposed in this paper. This paper calculates the quantum cost of PHOTON-Beetle for every layer and compares it with [1].
A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.
Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f ( i ) = f ( j ), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an r -to-one function must evaluate the function Ω(( n / r ) 1/3 ) times, where n is the size of the domain and r | n . This matches an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of Ω( n 2/3 ) queries for the element distinctness problem, which is to determine whether n integers are all distinct. The best previous lower bound was Ω(√ n ) queries.
The rapid advancements in quantum technologies have introduced significant threats to the security of conventional cryptographic systems. In particular, the evaluation of quantum resource requirements—measured in terms of circuit depth and qubit count—has become essential for analyzing the resilience of widely used schemes such as AES and RSA, as well as cryptographic hash functions like SHA-2. At the same time, the widespread adoption of Internet of Things (IoT) applications has increased the exposure to cybersecurity risks, which are further exacerbated by the emerging capabilities of quantum adversaries. To address these challenges, the U.S. National Institute of Standards and Technology (NIST) launched a competition to standardize lightweight hash functions and defined five quantum security levels to assess their robustness. In this work, we conduct a resource analysis of the NIST Lightweight Hash Function finalists against the Grover search algorithm, providing detailed insights into their quantum resistance. The findings contribute to a more comprehensive understanding of the security strength of lightweight hash functions in the post-quantum era.