The idea of cracking a hash function at quantum speed

Abstract

The scientific article reviews and analyzes the current stage of cryptography development in the context of the inevitable post-quantum era. It is emphasized that post-quantum cryptography (PQC) is gaining the status of a key priority in the national security strategies of the world's leading developed countries, which are actively preparing for a fundamental transition to quantum-safe cryptographic practices. The consequence of the above is the urgent need for intensive development of the latest cryptographic algorithms, which by their nature will be resistant to attacks from powerful quantum computers. Today, several promising approaches to the creation of such quantum-safe algorithms based on various mathematical concepts and cryptographic primitives are already being actively studied. The article pays special attention to cryptography based on hash functions, which is considered one of the most promising areas in the context of developing reliable quantum-safe cryptographic tools. The potential for cracking cryptographic hash functions using quantum algorithms is analyzed. The article considers an original approach to assessing the quantum stability of hash functions, which consists in encoding the hash function itself in a quantum oracle, rather than its separate solution. A simplified (toy) hash function is used to clearly demonstrate the proposed idea. Based on the results of the experimental study, important conclusions are formulated, which indicate that quantum computers are indeed capable of significantly accelerating the process of inversion of cryptographic hash functions. This, in turn, provides strong grounds for serious concern about the cryptographic stability of various cryptographic primitives based on combinatorial problems. It is worth emphasizing that this problem is not limited to hash functions. This critically important observation means that to maintain a similar level of cryptographic security in the coming quantum era, the size of the input value of hash functions will likely need to be increased by at least half to compensate for the speedup provided by quantum algorithms.