The rapid advancement of quantum computing technology presents a significant challenge to the field of cryptography, particularly affecting the security of hash functions that form the foundation of many cryptographic protocols. Hash functions are widely used to ensure data integrity, generate digital signatures, and securely store passwords. However, the emergence of quantum algorithms—such as Grover’s algorithm—threatens to undermine the security assumptions on which these hash functions are based by significantly reducing their effective security levels. This paper aims to provide a comprehensive analysis of the vulnerabilities introduced by quantum computing to traditional hash functions, detailing how these weaknesses can be exploited by quantum adversaries. We explore the fundamental properties of hash functions, including pre-image resistance, second pre-image resistance, and collision resistance, and assess how these properties are affected in a quantum context. Furthermore, we examine the implications of these vulnerabilities for existing cryptographic systems and emphasize the urgent need for the development of post-quantum cryptographic standards. In response to these challenges, we review ongoing research efforts focused on designing hash functions that are resilient to quantum attacks. We evaluate several promising candidates for post-quantum hash functions, considering their security properties, performance metrics, and practical applicability. The findings of this paper highlight the necessity of transitioning to post-quantum cryptographic solutions to safeguard sensitive information in an increasingly quantum-capable world. Ultimately, we advocate for proactive measures within the cryptographic community to adopt and implement these new standards, thereby ensuring robust data security in the age of quantum computing.
Authentication is an indispensable part of Quantum Cryptography, which is an unconditionally secure key distribution technique based on the laws of nature. Without proper authentication, Quantum Cryptography is vulnerable to “man-in-the-middle” attacks. Therefore, to guarantee unconditional security of any Quantum Cryptographic protocols, the authentication used must also be unconditionally secure. The standard in Quantum Cryptography is to use theWegman-Carter authentication, which is unconditionally secure and is based on the idea of universal hashing. In this thesis, we first investigate properties of a Strongly Universal hash function family to facilitate understanding the properties of (classical) authentication used in Quantum Cryptography. Then, we study vulnerabilities of a recently proposed authentication protocol intended to rule out a "man-in-the-middle" attack on Quantum Cryptography. Here, we point out that the proposed authentication primitive is not secure when used in a generic Quantum Cryptographic protocol. Lastly, we estimate the lifetime of authentication using encrypted tags when the encryption key is partially known. Under simplifying assumptions, we derive that the lifetime is linearly dependent on the length of the authentication key. Experimental results that support the theoretical results are also presented.
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.
Quantum cryptographic primitives beyond key distribution remain a less well understood area of research. In classical cryptography, one-way functions underpin nearly all standard cryptographic protocols, motivating the search for meaningful quantum analogues and for a clear understanding of the physical and computational mechanisms that could enforce one-wayness. In this article, we review quantum one-way functions and a range of closely related quantum-state primitives, including one-way state generators, pseudorandom quantum states, and efficiently indistinguishable pairs of states. We discuss both computational and information-theoretic notions of quantum one-wayness, emphasizing the different adversarial models and security assumptions that underlie these constructions. We compare and contrast the various proposed primitives, and clarify their conceptual relationships. Particular emphasis is placed on questions of physical realizability, experimental feasibility, and robustness to noise. Finally, we outline open problems and future directions toward the development of practical quantum cryptographic primitives beyond key distribution, and the emergence of a broader quantum-cryptographic ecosystem.
Cryptographic hash functions are fundamental primitives widely used in practice. For such a function
f:{0,1}n→{0,1}m, it is nearly impossible for an adversary to produce the hash
f(x) without knowing the secret message
x∈{0,1}n. Unfortunately, all hash functions are vulnerable under the side-channel attack, which is a grave concern for information security in practice. This is because typically
m≪n and an adversary needs only
m bits of information to pass the verification test. In sharp contrast, we show that when quantum states are used, the leakage allowed can be almost the entire secret. More precisely, we call a function that maps
n bits to
m qubits a quantum cryptographic function if the maximum fidelity between two distinct hashes is negligible in
n. We show that for any
k=n−ω(logn), all quantum cryptographic hash functions remain cryptographically secure when leaking
k bits of information. By the quantum fingerprinting constructions of Buhrman et al.~({\em Phys. Rev. Lett.} 87, 167902), for all
m=ω(logn), there exist such quantum cryptographic hash functions. We also show that one only needs
ω(log2n) qubits to verify a quantum cryptographic hash, rather than the whole classical information needed to generate one. Our result also shows that to approximately produce a small amount of quantum side information on a classical secret, it may require almost the full information of the secret. This large gap represents a significant barrier for proving quantum security of classical-proof extractors.