Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As such, it will be important to minimize persistent memory in quantum protocols.
In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed in a classical oracle model and also in the standard model, but we observe that the quantum memory required for these protocols is quite large. In this work, we significantly decrease the quantum secret key size, in some cases achieving asymptotically optimal size. To do so, we develop novel techniques for proving the security of cryptosystems using coset states, which are one of the main tools used in unclonable cryptography.
Comments
This work is subsumed by [HSVZ-26] (https://eprint.iacr.org/2026/1210)
Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As such, it will be important to minimize persistent memory in quantum protocols.
In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed in a classical oracle model and also in the standard model, but we observe that the quantum memory required for these protocols is quite large. In this work, we significantly decrease the quantum secret key size, in some cases achieving asymptotically optimal size. To do so, we develop novel techniques for proving the security of cryptosystems using coset states, which are one of the main tools used in unclonable cryptography.
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.
We propose a novel concept of securing cryptographic keys which we call “Unclonable Secret Keys,” where any cryptographic object is modified so that its secret key is an unclonable quantum bit-string whereas all other parameters such as messages, public keys, ciphertexts, signatures, etc., remain classical. We study this model in the authentication and encryption setting giving a plethora of definitions and positive results as well as several applications that are impossible in a purely classical setting. In the authentication setting, we define the notion of one-shot signatures, a fundamental element in building unclonable keys, where the signing key not only is unclonable, but also is restricted to signing only one message even in the paradoxical scenario where it is generated dishonestly. We propose a construction relative to a classical oracle and prove its unconditional security. Moreover, we provide numerous applications including a signature scheme where an adversary can sign as many messages as it wants and yet it cannot generate two signing keys for the same public key. We show that one-shot signatures are sufficient to build a proof-of-work-based decentralized cryptocurrency with several ideal properties: it does not make use of a blockchain, it allows sending money over insecure classical channels and it admits several smart contracts. Moreover, we demonstrate that a weaker version of one-shot signatures, namely privately verifiable tokens for signatures, are sufficient to reduce any classically queried stateful oracle to a stateless one. This effectively eliminates, in a provable manner, resetting attacks to hardware devices (modeled as oracles). In the encryption setting, we study different forms of unclonable decryption keys. We give constructions that vary on their security guarantees and their flexibility. We start with the simplest setting of secret key encryption with honestly generated keys and show that it exists in the quantum random oracle model. We provide a range of extensions, such as public key encryption with dishonestly generated keys, predicate encryption, broadcast encryption and more.
We provide a pre-obfuscation circuit-level implementation of an efficient one shot signature scheme, which has known applications to delegated signatures, secure token transfer, and publicly verifiable randomness. The algorithm consists of two stages: a key generation stage where a classical public key/quantum secret key pair is produced, and a signing stage where the quantum secret key is processed with a message string to produce a classical signature. There is no algorithmic error in the construction and the signed message can be efficiently checked by a classical verifier. Our scheme works by preparing a superposition over elements of a random affine coset determined by the output of a puncturable pseudorandom function, together with a circuit that tests coset membership. The logical qubit number scales like Θ(κlog(r)+n+l) and the gate complexity scales like Θ(n3+nl), where r is the public key size, n+l is the signature size, l is the message size, and κ=Ω(n) is the cryptographic security parameter. We provide explicit qubit and gate counts before obfuscation. A secure instantiation additionally requires modified key generation and a security proof for the resulting obfuscated construction.
By leveraging the no-cloning principle of quantum mechanics, unclonable cryptography enables us to achieve novel cryptographic protocols that are otherwise impossible classically. Two most notable examples of unclonable cryptography are quantum copy-protection and unclonable encryption. Most known constructions rely on the quantum random oracle model (as opposed to the plain model), in which all parties have access in superposition to a powerful random oracle. Despite receiving a lot of attention in recent years, two important open questions still remain: copy-protection of point functions in the plain model, which is usually considered as feasibility demonstration, and unclonable encryption with unclonable indistinguishability security in the plain model. A core ingredient of these protocols is the so-called monogamy-of-entanglement property. Such games allow quantifying the correlations between the outcomes of multiple non-communicating parties sharing entanglement in a particular context. Specifically, we define the games between a challenger and three players in which the first player is asked to split and share a quantum state between the two others, who are then simultaneously asked a question and need to output the correct answer. In this work, by relying on previous works of Coladangelo, Liu, Liu, and Zhandry (Crypto'21) and Culf and Vidick (Quantum'22), we establish a new monogamy-of-entanglement property for subspace coset states, which allows us to progress towards the aforementioned goals. However, it is not sufficient on its own, and we present two conjectures that would allow first to show that copy-protection of point functions exists in the plain model, with different challenge distributions (including arguably the most natural ones), and then that unclonable encryption with unclonable indistinguishability security exists in the plain model. We believe that our new monogamy-of-entanglement to be of independent interest, and it could be useful in other applications as well. To highlight this last point, we leverage our new monogamy-of-entanglement property to show the existence of a tokenized signature scheme with a new security definition, called unclonable unforgeability.
By leveraging the no-cloning principle of quantum mechanics, unclonable cryptography enables us to achieve novel cryptographic protocols that are otherwise impossible classically. Two most notable examples of unclonable cryptography are copy-protection (CP) and unclonable encryption (UE). Most known constructions rely on the QROM (as opposed to the plain model). Despite receiving a lot of attention in recent years, two important open questions still remain: CP for point functions in the plain model, which is usually considered as feasibility demonstration, and UE with unclonable indistinguishability security in the plain model. A core ingredient of these protocols is the so-called monogamy-of-entanglement (MoE) property. Such games allow quantifying the correlations between the outcomes of multiple non-communicating parties sharing entanglement in a particular context. Specifically, we define the games between a challenger and three players in which the first player is asked to split and share a quantum state between the two others, who are then simultaneously asked a question and need to output the correct answer. In this work, by relying on previous works [CLLZ21, CV22], we establish a new MoE property for subspace coset states, which allows us to progress towards the aforementioned goals. However, it is not sufficient on its own, and we present two conjectures that would allow first to show that CP of point functions exists in the plain model, with different challenge distributions, and then that UE with unclonable indistinguishability security exists in the plain model. We believe that our new MoE to be of independent interest, and it could be useful in other applications as well. To highlight this last point, we leverage our new MoE property to show the existence of a tokenized signature scheme with a new security definition, called unclonable unforgeability.
Properties of quantum mechanics such as entanglement and the no-cloning theorem enable new forms of cryptography that are unattainable in classical models of computation. Quantum information, however, is harder to process, store, and transmit than classical information. As such, it is desirable to construct semi-quantum cryptographic protocols where only a subset of the parties have quantum capabilities while the rest operate classically. In this dissertation, we analyze the security of semi-quantum protocols based on two approaches: (i) nonlocality-based techniques and (ii) the hardness of the Learning with Errors (LWE) problem. In the first part of the dissertation, we leverage a form of Bell test to construct a quantum position verification (QPV) protocol. Initial QPV protocols required verifiers to prepare and send quantum states to an honest prover to achieve security against adversaries with bounded memory or entanglement. Later work constructed QPV protocols with classical verifiers but required additional assumptions such as the hardness of LWE or of random circuit sampling. We construct a variant of QPV where classical verifiers verify the spatial locations of two provers. We use the nonlocal correlations produced by the two provers to show security against adversaries with bounded quantum memory without making any computational intractability assumptions. In the second part of the dissertation, we use trapdoor claw-free functions (TCFs) to construct semi-quantum cryptographic protocols. TCFs, which are constructible from the hardness of LWE, have been shown to be immensely valuable in the construction of classically verifiable quantum cryptographic protocols. As opposed to previous work where the server is asked to prepare a claw state and perform Pauli-X and Z measurements, we use a technique that leverages the entire range of qubit measurements on the XY-plane. We use this technique to construct three protocols: (i) a one-round blind remote state preparation protocol that delegates the preparation of an arbitrary state on the XY-plane up to a Pauli-X correction; (ii) a two-round proof of quantumness whose security is directly in terms of the hardness of LWE and only requires the prover to prepare and measure a single claw state; and (iii) a 1-of-2 Puzzle with a single qubit auxiliary state.