Quantum algorithms for hash preimage attacks
Ping Wang, Shengping Tian, Zhiwei Sun, Ning Xie · Quantum Engineering · 2020
Cryptographic hash functions are important building blocks of many security systems. A preimage attack on hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage. The current paper presents a new quantum algorithm for hash preimage attacks, which can break the preimage resistance with circuit complexity O(2n/3) using O(2n/3) running times, where n is the input bit length of the hash function. The quantum circuit complexity is apparently reduced from O(2n/2) to O(2n/3) at the cost of O(2n/3) running times requirements compared with the existing algorithms.