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