Shor’s quantum factoring algorithm and a few other efficient quantum algorithms break many clas-sical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against quantum attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quan-tum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are “quantum-friendly”. We characterize sufficient conditions such that a classical reduction can be “lifted ” to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in [BDH11] carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in [BDH11] is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model [Zha12b] and the simple hybrid arguments framework in [HSS11]) can be reformulated under our unified framework. 1
Shor’s quantum factoring algorithm and a few other efficient quantum algorithms break many clas-sical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against quantum attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quan-tum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are “quantum-friendly”. We characterize sufficient conditions such that a classical reduction can be “lifted ” to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in [BDH11] carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in [BDH11] is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model [Zha12b] and the simple hybrid arguments framework in [HSS11]) can be reformulated under our unified framework. 1
Shor's quantum factoring algorithm and a few other efficient quantum algorithms break many classical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against \emph{quantum} attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quantum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are "quantum-friendly". We characterize sufficient conditions such that a classical reduction can be "lifted" to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in~\cite{BDH11} carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in~\cite{BDH11} is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model~\cite{Zha12ibe} and the simple hybrid arguments framework in~\cite{HSS11}) can be reformulated under our unified framework.
Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.
It is obviously necessary that the security of post-quantum cryptographic schemes is based on computational problems that are hard to solve even with a quantum computer (unlike, e.g., factoring). Examples of such computational problems appear in the theory of lattices or in coding theory. However, this is not sufficient: also the security proof, which comes in the form of an algorithmic reduction that turns any hypothetical attacker into an algorithm that solves the considered hard computational problem, needs to be valid when considering quantum computing as the model of computation. In this work, we provide an overview of the hurdles one typically encounters when proving the security of post-quantum cryptographic schemes, and we elaborate on some of the mathematical techniques that have been developed in order to overcome these hurdles (to some extent). We also analyze the caveat that even when a security proof can be established (by reducing the security to a quantum-hard computational problem), the reduction often suffers from a larger reduction loss, compared to when proving classical security, which negatively affects the concrete security. In the second part of this work, we offer a survey of the respective reduction losses in (1) generic transformations that are often used in the design of cryptographic schemes (like the Fiat-Shamir and Fujisaki-Okamoto transformations), and (2) some concrete cryptographic schemes (with a focus on those standardized by NIST), when considering classical and when considering post-quantum security. Finally, we investigate how these reduction losses translate into bit security, the standard measure of the concrete security of a cryptographic scheme (or of the hardness of an underlying computational problem). A natural question is how the bit security is affected by the different reduction losses we encountered. Surprisingly, we observe that a better or worse reduction (in terms of the reduction loss) is not always reflected as such in the bit security. We explain this phenomenon by the fact that the bit security is oblivious to the actual advantage–time function, and instead considers a worst-case behavior of that function. Thus, by exploiting the actual advantage–time function there is potential to get more accurate (i.e., less conservative) estimates for the concrete security.
The rapid advancement of quantum computing presents a fundamental challenge to modern cryptographic security, particularly in the domain of hash functions that ensure data integrity, authentication, and blockchain security. Traditional crypto graphic hash functions such as SHA-256, SHA-3, and BLAKE2 rely on computational hardness assumptions that become obsolete in the presence of large-scale quantum computers. Shor’s algorithm can efficiently break RSA and ECC-based cryptosys tems, while Grover’s algorithm reduces the security of traditional hash functions by square root complexity, significantly weakening their preimage and collision resistance. This quantum threat necessitates the development of post-quantum secure hashing techniques that remain resilient against both classical and quantum adversaries. This paper proposes Quantum Hashing, a novel cryptographic framework that integrates quantum entanglement, lattice-based cryptography, and hybrid quantum classical hashing to construct post-quantum secure hash functions. We introduce a formal model for Quantum Collision Resistance (QCR) and provide entropy-based ran domness enhancement to ensure unpredictable hash outputs. Unlike classical hashing approaches, our framework leverages the hardness of lattice problems (e.g., Shortest Vector Problem, Learning with Errors) to withstand quantum attacks while incorpo rating Quantum Key Distribution (QKD) mechanisms to enhance entropy and key management. Furthermore, we evaluate the security of Quantum Hashing under various attack models, comparing its resistance against Grover’s search and collision attacks. We benchmark its performance against NIST Post-Quantum Cryptography (PQC) final ists, including CRYSTALS-DILITHIUM, SPHINCS+, and Falcon, demonstrating that our approach offers superior resilience while maintaining computational feasibility. Additionally, we present an implementation of Quantum Hashing using Qiskit, show casing its practical applicability in quantum circuits and quantum-secure blockchain architectures. Our findings highlight that Quantum Hashing provides a scalable, entropy-efficient, and post-quantum resilient cryptographic primitive suitable for next-generation cryptographic applications. This work paves the way for secure post-quantum digital signatures, blockchain consensus mechanisms, and zero-knowledge proof systems that require tamper-resistant hashing in a quantum computing era.
We call quantum security the area of IT security dealing with scenarios where one or more parties have access to quantum hardware. This encompasses both the fields of post-quantum cryptography (that is, traditional cryptography engineered to be resistant against quantum adversaries), and quantum cryptography (that is, security protocols designed to be natively run on a quantum infrastructure, such as quantum key distribution). Moreover, there exist also hybrid models, where traditional cryptographic schemes are somehow `mixed' with quantum operations in certain scenarios. Even if a fully-fledged, scalable quantum computer has yet to be built, recent results and the pace of research in its realization call for attention, lest we suddenly find ourselves one day with an obsolete security infrastructure. For this reason, in the last two decades research in quantum security has experienced an exponential growth in interest and investments. In this work, we propose the first systematic classification of quantum security scenarios, and for each of them we recall the main tools and results, as well as presenting new ones. We achieve this goal by identifying four distinct quantum security classes, or domains, each of them encompassing the security notions and constructions related to a particular scenario. We start with the class QS0, which is `classical cryptography' (meaning that no quantum scenario is considered), where we present some classical constructions and results as a preliminary step. Regarding post-quantum cryptography, we introduce the class QS1, where we discuss in detail the problems arising when designing a classical cryptographic object meant to be resistant against adversaries with local quantum computing power, and we provide a classification of the possible quantum security reductions in this scenario when considering provable security. Moreover, we present results about the quantum security and insecurity of the Fiat-Shamir transformation (a useful tool used to turn interactive identification schemes into digital signatures), and ORAMs (protocols used to outsource a database in a private way). In respect to hybrid classical-quantum models, in the security class QS2 we discuss in detail the possible scenarios where these scenarios arise, and what a correct formalization should be in terms of quantum oracle access. We also provide a novel framework for the quantum security (both in terms of indistinguishability and semantic security) of secret-key encryption schemes, and we give explicit secure constructions, as well as impossibility results. Finally, in the class QS3 we consider all those cryptographic constructions designed to run natively on quantum hardware. We give constructions for quantum encryption schemes (both in the secret- and public-key scenario), and we introduce transformations for obtaining such schemes by conceptually simpler schemes from the class QS2. Moreover, we introduce a quantum version of ORAM, called quantum ORAM (QORAM), aimed at outsourcing in a private way a database composed of quantum data. In proposing a suitable security model and an explicit construction for QORAMs, we also introduce a technique of independent interest which models a quantum adversary able to extract information from a quantum system without disturbing it `too much'. We believe that the framework we introduce in this work will be a valuable tool for the scientific community in addressing the challenges arising when formalizing sound constructions and notions of security in the quantum world.
Modern public-key cryptography relies on the hardness of mathematical problems such as integer factorization and discrete logarithms. However, the development of quantum computing poses an imminent threat to these assumptions. Shor’s algorithm, in particular, can factor large semiprimes exponentially faster than classical algorithms, compromising systems like RSA, DSA, and ECC. This paper explores the mathematical foundations of pre-quantum cryptography, discusses the limitations of classical security models when confronted with quantum capabilities, and then pays attention to post-quantum cryptography (PQC), a field dedicated to developing cryptographic schemes resilient against both classical and quantum attacks. Among the proposed families, this paper focuses specifically on hash function–based cryptography for its simplicity and minimal reliance on algebraic structure. This study focuses in particular on SPHINCS+, a stateless hash-based digital signature scheme currently under consideration by NIST. Through detailed mathematical explanation and a visual example, we analyze its construction using Winternitz One-Time Signatures and Merkle trees. The results highlight SPHINCS+ as a robust candidate for post-quantum security due to its reliance on well-understood hash primitives and its resistance to known quantum algorithms such as Grover’s. Finally, this paper discusses ongoing challenges such as performance trade-offs, standardization, and real-world deployment. This research underscores the urgency of adopting quantum-resistant cryptographic systems before large-scale quantum computers become a reality.