International Symposium on Information Theory and its Applications
Complexity of Solving Hash Puzzles Using Revised Boyer Quantum Algorithm
Chris Idota, Yuichi Kaji
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.