A quantum tamper-evident encryption scheme is a non-interactive symmetric-key encryption scheme mapping classical messages to quantum ciphertexts such that an honest recipient of a ciphertext can detect with high probability any meaningful eavesdropping. This quantum cryptographic primitive was first introduced by Gottesman in 2003. Beyond formally defining this security notion, Gottesman's work had three main contributions: showing that any quantum authentication scheme is also a tamper-evident scheme, noting that a quantum key distribution scheme can be constructed from any tamper-evident scheme, and constructing a prepare-and-measure tamper-evident scheme using only Wiesner states inspired by Shor and Preskill's proof of security for the BB84 quantum key distribution scheme. In this work, we further our understanding of tamper-evident encryption by formally relating it to other quantum cryptographic primitives in an information-theoretic setting. In particular, we show that tamper evidence implies encryption, answering a question left open by Gottesman, we show that it can be constructed from any encryption scheme with revocation and vice-versa, and we formalize an existing sketch of a construction of quantum money from any tamper-evident encryption scheme. These results also yield as a corollary that any scheme allowing the revocation of a message must be an encryption scheme. We also show separations between tamper evidence and other primitives, notably showing that tamper evidence does not imply authentication and does not imply uncloneable encryption.
A quantum tamper-evident encryption scheme is a non-interactive symmetric-key encryption scheme mapping classical messages to quantum ciphertexts such that an honest recipient of a ciphertext can detect with high probability any meaningful eavesdropping. This quantum cryptographic primitive was first introduced by Gottesman in 2003. Beyond formally defining this security notion, Gottesman's work had three main contributions: showing that any quantum authentication scheme is also a tamper-evident scheme, noting that a quantum key distribution scheme can be constructed from any tamper-evident scheme, and constructing a prepare-and-measure tamper-evident scheme using only Wiesner states inspired by Shor and Preskill's proof of security for the BB84 quantum key distribution scheme. In this work, we further our understanding of tamper-evident encryption by formally relating it to other quantum cryptographic primitives in an information-theoretic setting. In particular, we show that tamper evidence implies encryption, answering a question left open by Gottesman, we show that it can be constructed from any encryption scheme with revocation and vice-versa, and we formalize an existing sketch of a construction of quantum money from any tamper-evident encryption scheme. These results also yield as a corollary that any scheme allowing the revocation of a message must be an encryption scheme. We also show separations between tamper evidence and other primitives, notably showing that tamper evidence does not imply authentication and does not imply uncloneable encryption.
We propose an information-theoretically secure encryption scheme for classical messages with quantum ciphertexts that offers detection of eavesdropping attacks, and re-usability of the key in case no eavesdropping took place: the entire key can be securely re-used for encrypting new messages as long as no attack is detected. This is known to be impossible for fully classical schemes, where there is no way to detect plain eavesdropping attacks. This particular application of quantum techniques to cryptography was originally proposed by Bennett, Brassard and Breidbart in 1982, even before proposing quantum-key-distribution, and a simple candidate scheme was suggested but no rigorous security analysis was given. The idea was picked up again in 2005, when Damgard, Pedersen and Salvail suggested a new scheme for the same task, but now with a rigorous security analysis. However, their scheme is much more demanding in terms of quantum capabilities: it requires the users to have a quantum computer. In contrast, and like the original scheme by Bennett et al., our new scheme merely requires to prepare and measure single BB84 qubits. As such, we not only show a provably-secure scheme that is within reach of current technology, but we also confirm Bennett et al.'s original intuition that a scheme in the spirit of their original construction is indeed secure.
Public-key cryptosystems for quantum messages are considered from two aspects: public-key encryption and public-key authentication. Firstly, we propose a general construction of quantum public-key encryption scheme, and then construct an information-theoretic secure instance. Then, we propose a quantum public-key authentication scheme, which can protect the integrity of quantum messages. This scheme can both encrypt and authenticate quantum messages. It is information-theoretic secure with regard to encryption, and the success probability of tampering decreases exponentially with the security parameter with regard to authentication. Compared with classical public-key cryptosystems, one private-key in our schemes corresponds to an exponential number of public-keys, and every quantum public-key used by the sender is an unknown quantum state to the sender.
The emergence of quantum computing has provided new paradigms for cryptography. On the one hand, it poses significant new threats to existing classically cryptographic systems, requiring the community to define new security models that capture what a quantum adversary can do. On the other hand, it gives us new tools to design cryptographic protocols, with weaker assumptions than in the classical world, or even protocols that are impossible classically. In this survey, we first give an overview of new security definitions for classical cryptography, considering quantum adversaries who can either only use local quantum computation (post-quantum security), or even send quantum messages and in particular have access to oracle in superposition (quantum security). We explore these new notions through the examples of commitments, zero-knowledge proofs, encryption, and signatures. Then, we present what is arguably the most famous application of quantum cryptography: quantum key distribution (QKD) protocols that take advantage of unique properties of quantum mechanics to provide secure communication unconditionally. We also explore cryptography beyond QKD, focusing on unclonable cryptography: a family of cryptographic functionalities, built with quantum states, and designed to be resistant to counterfeit by leveraging the “no-cloning” theorem. We examine in particular quantum money, but also the recent notions of unclonable encryption and copy-protection, including related variants. By presenting a comprehensive survey of these topics, this paper aims to provide a thorough understanding of the current landscape and future potential of quantum cryptography.
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.
In the context of classical information, every message is composed of 0s and 1s; these messages can generally be copied at will. However, when quantum phenomena are used to model information, this guarantee no longer exists. This difference gives rise to a range of cryptographic possibilities when one considers encoding certain messages as quantum information. In our case, we analyze a potential benefit of encoding part of an encryption scheme’s ciphertext as quantum information. We call this type of ciphertext a quantum ciphertext. In particular, quantum ciphertexts are useful when one wants to be able to prove the deletion of the plaintext underlying a ciphertext. Since classical ciphertexts can be copied, clearly such feat is impossible using classical information alone. However, we show that quantum encodings allow such certified deletion. More precisely, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext, should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements, and the scheme is robust against noise in these devices. Furthermore, we provide a proof of security which requires only a finite amount of communication, and which therefore avoids the common technique of relying on the analysis of an asymptotic case.
Tamper-resilient cryptography studies how to protect data against adversaries who can physically manipulate codewords before they are decoded. The notion of tamper detection codes formalizes this goal, requiring that any unauthorized modification be detected with high probability. Classical results, starting from Jafargholi and Wichs (TCC 2015), established the existence of such codes against very large families of tampering functions, subject to structural restrictions ruling out identity and constant maps. Recent works of Boddu and Kapshikar (Quantum, 7) and Bergamaschi (Eurocrypt 2024) have extended these ideas to quantum adversaries, but only consider unitary tampering families. In this work, we give the first general treatment of tamper detection against arbitrary quantum maps. We show that Haar-random encoding schemes achieve exponentially small soundness error against any adversarial family whose size, Kraus rank, and entanglement fidelity obey natural constraints, which are direct quantum analogues of restrictions in the classical setting. Our results unify and extend previous works. Beyond this, we demonstrate a fundamental separation between classical and quantum tamper detection. Classically, relaxed tamper detection which allows either rejection or recovery of the original message cannot protect even against the family of constant functions. This family is of size 2n. In contrast, we show that quantum encodings can handle this obstruction, and we conjecture and provide evidence that they may in fact provide relaxed tamper detection and non-malleable security against any family of quantum maps of size up to 22αn for any constant α<21, leading to a conjecture on the existence of universal quantum tamper detection. Our results provide the first evidence that quantum tamper detection is strictly more powerful than its classical counterpart.