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 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.
A main application of quantum information in cryptography is copy-protection, where we encode a functionality (such as a decryption key or software) into a reusable quantum state so that it cannot be split into two adversaries (called freeloaders) that both remain useful.
Previous works have only shown security for independently sampled challenges for the two adversaries. A competing natural security notion is identical-challenge security where the adversaries receive the same challenge. This notion has many real-life applications and connections to other fundamental primitives such as unclonable bits (i.e. unclonable encryption) and unclonable lockboxes (i.e. copy-protection of point functions). Despite its importance and numerous attempts, achieving identical-challenge security in the plain model has remained open.
We first make progress on the definitional foundations of copy-protection by introducing natural copy-protection security definitions that imply the previous ones (including identical-challenge security) and better capture the security intuitions and real-life use cases; and we also characterize the relationship between the previous definitions. Then, we show how to achieve in the plain model our new stronger definitions for copy-protection of general classes of functionalities. In particular, we resolve the long-standing open questions of copy-protection of point functions, copy-protection of compute-and-compare programs, and identical-challenge secure copy-protection of decryption keys and all puncturable functionalities.
Our technical core is a new decisional monogamy-of-entanglement result for coset states, which both allows us to achieve our new results, and also significantly simplifies and unifies unclonable cryptography proofs. We believe this will have further applications and may be of independent interest.
We establish a strong monogamy-of-entanglement property for subspace coset states, which are uniform superpositions of vectors in a linear subspace of F2n to which has been applied a quantum one-time pad. This property was conjectured recently by [Coladangelo, Liu, Liu, and Zhandry, Crypto'21] and shown to have applications to unclonable decryption and copy-protection of pseudorandom functions. We present two proofs, one which directly follows the method of the original paper and the other which uses an observation from [Vidick and Zhang, Eurocrypt'20] to reduce the analysis to a simpler monogamy game based on BB'84 states. Both proofs ultimately rely on the same proof technique, introduced in [Tomamichel, Fehr, Kaniewski and Wehner, New Journal of Physics '13].
Unclonable cryptography is concerned with leveraging the no-cloning principle to build cryptographic primitives that are otherwise impossible to achieve classically. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We present a new approach to unclonable encryption via a reduction to a novel question about nonlocal quantum state discrimination: how well can non-communicating -- but entangled -- players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is showing that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We leverage this result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing.
Much of the strength of quantum cryptography may be attributed to the no-cloning property of quantum information. We construct three new cryptographic primitives whose security is based on uncloneability, and that have in common that their security can be established via a novel monogamy-of-entanglement (MoE) property: - We define interactive uncloneable encryption, a version of the uncloneable encryption defined by Broadbent and Lord [TQC 2020] where the receiver must partake in an interaction with the sender in order to decrypt the ciphertext. We provide a one-round construction that is secure in the information-theoretic setting, in the sense that no other receiver may learn the message even if she eavesdrops on all the interactions. - We provide a way to make a bit string commitment scheme uncloneable. The scheme is augmented with a check step chronologically in between the commit and open steps, where an honest sender verifies that the commitment may not be opened by an eavesdropper, even if the receiver is malicious. - We construct a receiver-independent quantum key distribution (QKD) scheme, which strengthens the notion of one-sided device independent QKD of Tomamichel, Fehr, Kaniewski, and Wehner (TFKW) [NJP 2013] by also permitting the receiver's classical device to be untrusted. Explicitly, the sender remains fully trusted while only the receiver's communication is trusted. To show security, we prove an extension of the MoE property of coset states introduced by Coladangelo, Liu, Liu, and Zhandry [Crypto 2021]. In our stronger version, the player Charlie also receives Bob's answer prior to making his guess, simulating a party who eavesdrops on an interaction. To use this property, we express it as a new type of entropic uncertainty relation which arises naturally from the structure of the underlying MoE game.
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.