Source-linked AI summary
Quantum Copy-Protection and Quantum Money
Scott Aaronson
TL;DR
The paper addresses whether quantum states can support publicly verifiable unclonable money and copy-protected programs, problems left open or newly posed beyond classical copyable information. It uses quantum-complexity techniques, including oracle constructions, simulation, a complexity-theoretic no-cloning theorem, and quantum t-designs. The results establish oracle-relative feasibility and introduce explicit candidate schemes outside the oracle setting, while leaving their security under existing assumptions unresolved.
Problem
The paper asks whether quantum money can be publicly verified while remaining hard to copy, and whether quantum states can serve as copy-protected programs that evaluate f without yielding additional programs.
Method
The paper combines quantum-oracle constructions with simulators, a Complexity-Theoretic No-Cloning Theorem, and explicit quantum t-designs to analyze money and copy-protection.
Results
The results give complexity-theoretic evidence that publicly verifiable quantum money and quantum copy-protection are possible, including copy-protection for nonlearnable function families relative to an oracle.
Takeaways & Limitations
The oracle results establish feasibility in a relativized setting, while the paper also supplies explicit candidate schemes for publicly verifiable quantum money and point-function copy-protection.
Takeaways & Limitations
Security of the explicit schemes is not based on any existing cryptographic assumption, and the copy-protection theorem only handles piracy algorithms that more than double the number of programs.
Abstract
from arXiv · showhide
Forty years ago, Wiesner proposed using quantum states to create money that is physically impossible to counterfeit, something that cannot be done in the classical world. However, Wiesner's scheme required a central bank to verify the money, and the question of whether there can be unclonable quantum money that anyone can verify has remained open since. One can also ask a related question, which seems to be new: can quantum states be used as copy-protected programs, which let the user evaluate some function f, but not create more programs for f? This paper tackles both questions using the arsenal of modern computational complexity. Our main result is that there exist quantum oracles relative to which publicly-verifiable quantum money is possible, and any family of functions that cannot be efficiently learned from its input-output behavior can be quantumly copy-protected. This provides the first formal evidence that these tasks are achievable. The technical core of our result is a "Complexity-Theoretic No-Cloning Theorem," which generalizes both the standard No-Cloning Theorem and the optimality of Grover search, and might be of independent interest. Our security argument also requires explicit constructions of quantum t-designs. Moving beyond the oracle world, we also present an explicit candidate scheme for publicly-verifiable quantum money, based on random stabilizer states; as well as two explicit schemes for copy-protecting the family of point functions. We do not know how to base the security of these schemes on any existing cryptographic assumption. (Note that without an oracle, we can only hope for security under some computational assumption.)
1 Introduction
The paper revisits publicly verifiable quantum money and quantum copy-protected software, establishing oracle-based feasibility and proposing explicit candidate schemes. Its central technical tool is a complexity-theoretic no-cloning theorem connecting cloning hardness with quantum search lower bounds.
- 1 Introduction: The paper asks whether quantum states can provide publicly verifiable money or useful programs that cannot be copied.Quantum copy-protected software would let users compute f without efficiently preparing additional useful programs for f.
- 1 Introduction: There exists a quantum oracle relative to which publicly verifiable quantum money and copy-protection of arbitrary software are possible.The copy-protection claim concerns software that is not learnable from input-output behavior by polynomial-time quantum computation.
- 1 Introduction: Beyond oracle results, the paper proposes explicit candidate quantum-money schemes and copy-protection schemes for point functions.The point-function application distributes password-authentication programs that cannot be used to create additional password-recognition programs.
- 1 Introduction: The oracle result provides complexity-theoretic evidence that both publicly verifiable quantum money and quantum copy-protection are achievable.It also implies that proving impossibility would require techniques sensitive to quantum oracles.
- 1.1 Techniques: The Complexity-Theoretic No-Cloning Theorem generalizes both the standard No-Cloning Theorem and the BBBV lower bound for quantum search.It considers producing more copies from an initial supply while access to a state-recognition oracle is available.
- 1.1 Techniques: For quantum copy-protection, learnability is identified as the only obstruction in the oracle setting.A simulator converts a piracy algorithm into an algorithm that learns the function using black-box access.
- 1.2 Related Work: The explicit schemes lack security proofs based on existing cryptographic assumptions, while earlier publicly verifiable quantum money proposals were insecure.The earlier proposal relied on factoring Blum integers and was vulnerable to quantum factoring and entangled measurements.
2 Preliminaries
The paper formalizes quantum money and related security notions, then establishes computational-assumption results for private-key schemes while contrasting copy-protection with obfuscation.
- Quantum money definitions: A quantum money scheme uses a bank, an authenticator, and a counterfeiter model to formalize production, verification, and resistance to increasing valid notes.Public-key schemes give the counterfeiter the public key; private-key schemes do not, and query security grants access to an authentication oracle.
- Quantum money definitions: Negligible soundness error prevents any polynomial-time counterfeiter from increasing expected accepted-state wealth by more than a negligible amount, even with entangled outputs.The definition applies to arbitrary polynomially many input and output registers.
- Quantum money results: If quantum-secure pseudorandom functions exist, the BBBW construction gives private-key quantum money with perfect completeness and exponentially small soundness error.The BBBW scheme is not query-secure because repeated authentication queries can reveal a classical description of the banknote state.
- Quantum money results: Any quantum money scheme satisfying the formal definition must rely on some computational assumption.This contrasts with Wiesner’s original information-theoretic construction, which required a bank-maintained lookup table when expressed in the framework.
- Quantum copy-protection: Copy-protection is impossible classically and cannot apply to function families learnable from input-output behavior, making it a distinct quantum cryptographic task from obfuscation.The paper emphasizes that copy-protection’s possibility fundamentally depends on quantum mechanics.
3 Quantum Money
This section presents a random-stabilizer candidate for publicly verifiable quantum money and an oracle construction proving public-key quantum money is possible relative to a quantum oracle.
- 3.1 Candidate scheme: The explicit public-key money candidate samples random stabilizer states and authenticates them using signed tables of randomly generated stabilizer measurements.The bank distributes the states, measurement table, and a classical signature; authentication checks a randomly selected measurement per state and accepts by majority vote.
- 3.1 Candidate scheme: Choosing ℓ sufficiently larger than 1/ε^2 makes authentication rejection exponentially small and allows the note to be reused an exponential number of times.The reuse claim follows because uncomputing restores a state exponentially close in trace distance to the original tensor product.
- 3.1 Candidate scheme: The stabilizer-state security conjecture links counterfeiting to noisy decoding for random linear codes, but holds only in suitable parameter ranges.Security fails when m ≤ n/ε or when ε is too large, because efficient reconstruction or Gaussian elimination becomes possible.
- 3.2 Oracle result: There exists a quantum oracle relative to which a public-key quantum money scheme exists, with all parties receiving identical oracle access.Counterfeiters still require Ω(2^n/2) oracle queries to find the secret key, by Grover-search optimality.
- 3.2 Oracle result: A quantum oracle can encode each secret key s with a unique public key e_s and a random Haar state |ψ_s⟩, while enabling public authentication of matching pairs.The oracle prepares banknotes from |0⟩|s⟩ and authenticates them by recognizing |ψ_s⟩ associated with e_s.
4 Quantum Copy-Protection
The paper develops two candidate schemes for copy-protecting point functions and proves an oracle result showing that non-quantumly-learnable function families can be copy-protected. Its proof uses a simulator, quantum t-designs, and the Complexity-Theoretic No-Cloning Theorem to constrain piracy.
- Two schemes for point functions: The paper proposes two explicit quantum copy-protection schemes for the family of point functions.One uses random quantum circuits; the other uses hidden subgroups of the symmetric group.
- Two schemes for point functions: The random-circuit scheme generates a quantum program from a pseudorandom-generator output interpreted as a circuit description.The program is |ψs⟩ = Ug(s)|0⟩^⊗m, and evaluation checks whether the circuit output matches |0⟩^⊗m.
- Two schemes for point functions: Random quantum circuits make programs for distinct inputs have exponentially small overlap, while learning the secret remains hard under the stated pseudorandom-generator assumptions.The overlap claim uses approximate unitary 2-designs; the passage also states that polynomially many copies do not enable efficient learning unless the generator is insecure against quantum adversaries.
- Two schemes for point functions: The paper conjectures that neither scheme allows polynomial-time preparation of an additional useful program, but its candidate security is not based on a standard cryptographic assumption.For the random-circuit construction, the conjecture rules out producing a further copy or any other state from which the point function can be efficiently computed.
- Two schemes for point functions: The second scheme encodes the secret as an involutive permutation and uses a state built from random permutations; recovering the secret is related to the symmetric-group Hidden Subgroup Problem.The paper states that recovery would require entangled measurements on Ω(n log n) coset states, beyond present-day techniques.
- Oracle result: There exists a quantum oracle relative to which every efficiently computable, non-quantumly-learnable function family can be quantumly copy-protected.The proof simulates piracy using a quantum t-design and uses no-cloning to show that some output programs cannot depend essentially on the simulated oracle.
5 Open Problems
The paper identifies open questions about stronger candidate schemes, security assumptions, broader applications, and improved theoretical guarantees for quantum money and copy-protection.
- Security assumptions: Can explicit schemes for public-key quantum money and copy-protected point functions be proven secure under standard cryptographic assumptions?
- Broader function families: Can quantum copy-protection be extended beyond point functions to richer families, including trapdoor inversion functions?
- Related functionalities: Can unclonable quantum identification cards or quantum proofs be constructed, and how do these functionalities relate to money and copy-protection?
- Technical directions: Open technical questions concern information-theoretic security for few program copies, entanglement-free schemes, classical-oracle constructions, unsplittable amplification, improved no-cloning parameters, and quantum-secure PRF reductions.