Multi-Copy Security in Quantum Cryptography and More

Authors

Abstract

Unclonable cryptography leverages the quantum no-cloning principle to achieve strong security guarantees that are impossible to achieve in a classical world. Most existing works in this area only consider the basic single-copy security, and there been only a few works that achieve the more realistic notion of \emph{collusion-resistance} (where adversary receives multiple keys), which is the gold standard in cryptography. Further, existing works that do consider collusion-resistance have convoluted non-black-box solutions, and are highly tailored to their own applications, with little hope to generalize, and they often re-invent the tools from both single-key quantum cryptography as well as collusion-resistant classical cryptography. Moreover, the question of \emph{multi-copy security}, where the adversary receives multiple copies of the same state (rather than merely getting multiple independently sampled keys) is almost completely open.

In this work, we develop a large toolset of black-box compilers and technical lemmata for dealing with collusion-resistance and multi-copy security in quantum cryptography. Using our toolset, we obtain a large number of new feasibility results with black-box constructions, with proofs that are significantly \emph{simpler} than the existing proofs in literature.

In particular, we introduce a generic compiler that upgrades single-key secure quantum protection (copy-protection/LOCC leakage-resilience/secure leasing) schemes for decryption keys to collusion-resistant secure schemes. Then, we also introduce a generic compiler that upgrades collusion-resistant primitives to achieve multi-copy security, assuming only one-way functions.

Using our toolset, we obtain a large number of new feasibility results. We obtain the first multi-copy secure constructions of public-key quantum money (termed quantum coins), single-decryptor encryption (SDE), unclonable encryption, and more. We obtain the first collusion-resistant secure key-leasing scheme with a fully classical lessor. Finally, we obtain the first LOCC leakage-resilient PKE scheme with multi-copy security, thus making progress towards achieving \emph{quantum key-fire} in the plain model.

Finally, as part of our toolset, we also show various technical results, such as the collusion-resistant analogue of the \emph{one-way-to-hiding (O2H) lemma}, a quantum-state analogue of the small-range-distributions lemma, a \emph{quantum pigeonhole lemma} for entangled adversaries and the first deterministic signature scheme with quantum-query security. We also show that independent-challenge security implies identical-challenge security in collusion-resistant copy-protection search games, and thus we obtain the first schemes with such security.