PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Money from Hidden Subspaces

Scott Aaronson, Paul Christiano

arXiv:1203.4740v3quant-phcs.CC

TL;DR

The paper addresses whether quantum money can be publicly verified and cryptographically secured without relying solely on the No-Cloning Theorem. It constructs hidden-subspace money using multivariate polynomials, proves unconditional security for a classical-oracle version, and gives a public-key scheme under a classical hardness conjecture while repairing Wiesner’s online attack problem.

  • Problem

    Public-key quantum money requires anyone to authenticate a banknote without obtaining an efficient way to prepare or copy it, and its security needs a computational assumption beyond the No-Cloning Theorem.

  • Method

    The paper encodes hidden subspaces through membership oracles and random multivariate polynomials, analyzes cloning with an inner-product adversary method, and builds full schemes from mini-schemes and quantum-secure signatures.

  • Results

    The paper proves an unconditionally secure public-key scheme relative to a classical oracle and, assuming its classical hardness conjecture, a public-key scheme with perfect completeness and 1/exp(n) soundness error.

  • Takeaways & Limitations

    The constructions provide public-key quantum money based on a classical cryptographic assumption and an unconditionally secure private-key scheme against adaptive bank interaction.

  • Takeaways & Limitations

    The central hardness conjecture concerns structured systems with large solution spaces, paired subspaces, and a 2^-n/2 success threshold, leaving possible structure-specific attacks unresolved.

Abstract

from arXiv · show

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a "classical" hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the "black-box" version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner's original setting -- quantum money that can only be verified by the bank -- we are able to use our techniques to patch a major security hole in Wiesner's scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis -- matching the original intuition for quantum money, based on the existence of complementary observables. Our security proofs use a new variant of Ambainis's quantum adversary method, and several other tools that might be of independent interest.

1 Introduction

The paper develops quantum money that addresses public verifiability and cryptographic security, while also repairing Wiesner’s online-attack weakness. Its hidden-subspace approach combines unconditional black-box security with a classical hardness assumption for an explicit scheme.

  • Motivation: Classical information can be copied freely, motivating quantum money as a way to prevent counterfeiting without relying on a trusted third party.The paper contrasts classical copyability with quantum-mechanical restrictions on cloning.
  • The challenge: Public-key quantum money asks whether anyone can verify a banknote without gaining an efficient method to prepare or copy it.Earlier work established only oracle-relative possibilities or schemes whose security was difficult to characterize.
  • Our results: The paper’s main contribution is a public-key scheme that is the first to achieve public verifiability and cryptographic security among the listed goals.The construction uses hidden subspaces and combines mini-schemes with quantum-secure digital signatures.
  • Our results: The inner-product adversary method proves that cloning hidden-subspace states requires 2^Ω(n) oracle queries.It compares parallel executions on distinct subspaces and tracks how counterfeiting changes their inner product.
  • Our results: Relative to a classical oracle, the black-box construction is an unconditionally secure public-key quantum money scheme with exponentially small soundness error.A polynomial-time counterfeiter cannot make verification accept more banknotes than it received except with probability at most 1/exp(n).
  • Our results: The private-key adaptation is unconditionally secure against adaptive interaction with the bank, resolving the online attack problem in Wiesner’s and BBBW’s schemes.This is presented as the first provably secure solution to that security hole.
  • Our results: Random multivariate polynomials encode subspaces as zero-sets, yielding an explicit public-key scheme whose security rests on a classical hardness conjecture.Breaking the scheme would enable recovery of the hidden subspace from the polynomial descriptions, while the theorem gives perfect completeness and 1/exp(n) soundness error.

2 Preliminaries

The paper fixes notation and formalizes the cryptographic primitives used later, including quantum-secure signatures and quantum states. It also introduces a monotonic quantum-search procedure that retains Grover’s quadratic speedup.

  • Notation: A subspace S has an orthogonal complement S⊥ consisting of vectors orthogonal to every vector in S, with the meaning depending on whether the ambient space is C2^n or F_2^n.The paper distinguishes quantum-state orthogonality from binary-vector orthogonality.
  • Oracles: A classical oracle applies the phase transformation |x⟩→(−1)^f(x)|x⟩ and may still be queried in quantum superposition.Quantum oracles are instead arbitrary n-qubit unitaries applied as black boxes.
  • Cryptography: A digital signature scheme uses KeyGen, Sign, and Ver, and security forbids a quantum counterfeiter with nonadaptive classical signing access from forging a new message.Completeness requires verification of honestly generated signatures to accept with probability at least 1−ε.
  • Cryptography: A quantum-secure one-way function yields a digital signature scheme secure against quantum chosen-message attacks.The paper also states a relativized version relative to a suitable oracle.
  • Quantum Search: The standard amplification procedure can overshoot its target subspace, so the paper develops a hybrid search algorithm with monotonic convergence and quadratic speedup.The resulting state ρ can achieve fidelity F(ρ,G)≥1−δ after suitable oracle calls.

3 Formalizing Quantum Money

This section formalizes public-key quantum money, introduces mini-schemes as a simpler construction target, and proves generic transformations from mini-schemes and signatures to full schemes. It also establishes amplification results for projective mini-schemes and notes their scope limitations.

  • 3.1 Quantum Money Schemes: A public-key quantum money scheme lets a bank generate banknotes, lets anyone verify them, and prevents polynomially many valid notes from yielding more valid notes with non-negligible probability.The formal model uses KeyGen, Bank, and Ver, with classical and quantum components allowed in a banknote.
  • 3.1 Quantum Money Schemes: Soundness requires that a counterfeiter mapping q valid banknotes to r alleged notes satisfies Pr[Count(kpublic,C(...))>q]≤δ.The probability ranges over keys, valid banknotes, and the behavior of Count and the counterfeiter.
  • 3.1 Quantum Money Schemes: A scheme is secure when its completeness error is at most 1/3 and its soundness error is negligible.Completeness can be amplified, and exponentially small completeness error supports exp(n) verifications before a note wears out.
  • 3.2 Mini-Schemes: Mini-schemes simplify quantum money by issuing a classical serial number with one quantum state and using only Bank and Ver.They are designed to be easier to construct and analyze than full schemes.
  • 3.2 Mini-Schemes: A secure public-key money scheme implies a secure mini-scheme, while a secure secret-based mini-scheme implies a quantum-secure one-way function.These propositions connect the simpler primitive to both full schemes and classical cryptographic hardness.
  • 3.2 Mini-Schemes: For projective mini-schemes, any counterfeiter with non-negligible copying probability can be amplified into one whose copying probability is arbitrarily close to 1.The transformation depends on the success and target-error parameters, not on the particular banknote.
  • 3.2 Mini-Schemes: The amplification theorem is unlikely to hold for arbitrary non-projective mini-schemes, and the largest applicable class remains open.A verifier accepting every state with a small nonzero probability gives the stated obstruction.
  • 3.3 The Standard Construction: A secure mini-scheme combined with a quantum-secure digital signature scheme yields a secure public-key quantum money scheme, including in relativized settings.The paper’s constructions can also provide the needed signature schemes within the oracle framework.

4 Inner-Product Adversary Method

The inner-product adversary method bounds how quickly a counterfeiter can reduce overlaps between oracle-dependent executions. By averaging over carefully related oracle pairs, it converts the required constant overlap reduction into an exponential query lower bound.

  • Motivation: A public-key counterfeiter may possess a valid money state and query its verification procedure, so neither the No-Cloning Theorem nor Grover’s lower bound alone captures the attack.The desired theorem must handle both resources simultaneously.
  • Consequences: Theorem 20 generalizes the earlier Complexity-Theoretic No-Cloning Theorem and is later applied to public-key quantum money relative to a classical oracle.The original Haar-random-state theorem is recovered separately in an appendix.
  • Technical Difficulty: Because a fixed oracle pair can give the initial state a one-query head start, the proof samples oracle pairs from a distribution and bounds the expected one-query progress.Most oracle pairs remain resistant even if some pairs permit substantial single-query progress.
  • Method Idea: The method tracks the inner product between parallel executions that attempt to clone two distinct states using their corresponding membership oracles.Successful cloning decreases the relevant overlap, creating a progress target for the lower-bound argument.
  • Method Idea: A successful counterfeiter must decrease the relevant inner product by at least 1/4, while one query decreases the average inner product by at most 1/exp(n).This yields a 2^Ω(n) query requirement.
  • Formal Method: The inner-product adversary framework defines oracle-dependent subspaces, a symmetric relation on oracle pairs, and a progress measure whose decrease per query is bounded by a lemma.Theorem 20 packages these conditions into the resulting query lower bound.

5 Classical Oracle Scheme

The hidden-subspace mini-scheme uses public classical membership oracles for a random subspace and its orthogonal complement to verify a quantum money state. Its security is unconditional in the classical-oracle model, with exponentially small soundness error.

  • Construction: The bank distributes |A⟩ while keeping a classical description of the random n/2-dimensional subspace A secret.The verifier receives access to membership oracles for A and A⊥.
  • Construction: The verifier implements projectors onto A and A⊥, applies a Hadamard transform between them, and returns the state to |A⟩.This uses only two complementary-basis tests.
  • Verification: VA is a projector onto |A⟩, so honest notes are accepted with certainty and arbitrary states are accepted with probability |⟨ψ|A⟩|2.Thus the mini-scheme has perfect completeness.
  • Security: Uniform randomization makes the counterfeiting problem average-case hard, yielding a mini-scheme with 1/exp(n) soundness error.The security reduction converts attacks on the full scheme into attacks using only the subspace membership oracles.
  • Full scheme: Combining the mini-scheme with a digital signature scheme gives a public-key quantum money scheme with perfect completeness and 1/exp(n) soundness error.The construction is defined relative to a classical oracle.

6 Explicit Quantum Money Scheme

The explicit scheme replaces classical membership oracles with low-degree multivariate polynomials whose common zero-set hides a subspace. Its security is reduced to a subspace-hiding conjecture, while completeness remains perfect and soundness is exponentially small.

  • Construction: Finding a common zero of random multivariate polynomials is generally hard, while evaluating whether a given point is a common zero is easy.This asymmetry supplies the proposed mechanism for hiding subspaces.
  • Polynomial systems: A sufficiently large system of βn sampled polynomials determines A with probability 1 − 2^-Ω(n).For each point outside A, the probability that all βn polynomials vanish there is 2^-βn.
  • Construction: The explicit scheme publishes polynomial systems vanishing on A and A⊥, allowing users to test membership without publishing the subspaces themselves.These systems are sampled from distributions over polynomials that vanish on the corresponding subspaces.
  • Security: The explicit mini-scheme has perfect completeness because the published polynomial tests accept the legitimate subspace state.The construction therefore preserves the oracle mini-scheme's honest-verification behavior.
  • Security: Assuming Conjecture 34, the explicit mini-scheme is secure and the complete public-key scheme has perfect completeness with soundness error 2^-Ω(n).The security proof reduces successful counterfeiting to the stated hardness conjecture.
  • Assumption: Conjecture 34 is stronger than generic hardness of random polynomial systems because it imposes structured solution spaces, paired systems, and exponentially small allowed success.These additional requirements leave possible attacks exploiting the structure unruled out.

7 Private-Key Quantum Money

The private-key construction adapts hidden-subspace money to repair the online attack problem in Wiesner-like schemes. It achieves unconditional query security relative to a random oracle and computational query security under a pseudorandom function.

  • Security gap: Wiesner’s and BBBW’s schemes are vulnerable when a counterfeiter can submit notes to a bank and receive the post-measurement states.Adaptive verification queries can reveal the classical description of a note.
  • Security gap: A counterfeiter can learn each qubit in Wiesner’s scheme by replacing it with candidate states and estimating acceptance probabilities through O(log n) bank queries.This attack recovers a complete classical description using O(n log n) queries.
  • Security: Relative to a random oracle, the scheme has perfect completeness, 2^-Ω(n) soundness error, and information-theoretic query security.Replacing the random oracle with a pseudorandom function yields query security against quantum polynomial-time distinguishers.
  • Consequence: The construction gives the first private-key quantum money schemes that remain unconditionally secure under adaptive bank interaction.It directly addresses the major security hole identified in Wiesner’s and BBBW’s schemes.
  • Construction: The hidden-subspace private-key scheme uses a random subspace Ak,s and verifies a note by a projective measurement accepting with probability ⟨Ak,s|ρ|Ak,s⟩.The banknote includes a serial number and the corresponding uniform subspace state.
  • Security reduction: Adaptive verification queries can be simulated using membership oracles for Ak,s and Ak,s⊥, reducing private-key attacks to the unconditional public-key security proof.This is the core reason the private-key construction withstands adaptive interaction with the bank.

8 Open Problems

The paper leaves open whether the explicit polynomial construction has nontrivial attacks and whether stronger, more standard assumptions can support public-key quantum money. It also points toward broader applications of hidden-subspace techniques and quantum uncloneability.

  • Explicit scheme: The explicit polynomial scheme may admit nontrivial attacks, including attacks based on Gröbner-basis algorithms.The paper asks whether its security can be based on assumptions that do not involve exponentially small success probabilities.
  • Explicit scheme: Open questions include how changing the field size or polynomial degree affects security and whether hidden subspaces have other cryptographic applications.Program obfuscation is suggested as one possible application.
  • Public-key money: It remains open whether unconditionally secure public-key quantum money can be built relative to a random oracle.The paper contrasts this with private-key Wiesner money and its own public-key construction relative to a non-random oracle.
  • Broader applications: The paper suggests quantum uncloneability as a broader cryptographic resource for signatures, commitments, proofs, and quantum software.It also raises questions about copy-protecting arbitrary programs relative to a classical oracle.
  • Related directions: The security of related copy-protection constructions appears to hinge on the Direct Product for Finding Black-Box Subspace Elements conjecture.A proof would also provide evidence for the multivariate-polynomial hardness conjecture underlying the explicit scheme.

9 Appendix: Reducing Completeness Error

The appendix shows that repeating verification can reduce completeness error exponentially while increasing soundness error only modestly. The construction applies to mini-schemes and has a direct public-key counterpart.

  • Completeness amplification: Completeness error can be reduced to 1/2p(n) for any polynomial p, while the amplified scheme has soundness error δ′.The original scheme assumes completeness error ε < 1/2 and soundness error δ < 1 − 2ε, with δ′ > δ.
  • Construction: The amplified mini-scheme repeats k independently generated banknotes and accepts when at least (1 − ε − η)k individual verifications accept.This repetition-based construction uses a composite banknote containing independently generated components.
  • Construction: The amplified double verifier checks two candidate states componentwise and accepts only when both repeated verification tests pass.Its input consists of the serial numbers and two purported states for each component banknote.
  • Security reduction: A counterfeiter for the amplified scheme would yield a counterfeiter for the original scheme with success probability at least (1 − 2ε − η)δ′.The reduction replaces one randomly chosen component with the original banknote and uses the amplified counterfeiter's outputs.
  • Extensions: The same amplification parameters extend directly to public-key quantum money, using independently chosen public/private key pairs for the composite components.An analogous result is also noted for digital signatures, with slightly better parameters, but details are omitted.

10 Appendix: Complexity-Theoretic No-Cloning Theorem

The appendix proves query lower bounds for cloning unknown quantum states given oracle access that recognizes them. These bounds support security arguments for quantum money and include a quadratically stronger quantum-oracle construction.

  • Approximate cloning: The lower bounds extend to approximate duplication and projection-based verification for Haar-random n-qubit states.The appendix states bounds for preparing states with overlap at least ε or passing a two-copy projector with probability at least ε.
  • Application to quantum money: The quantum-oracle mini-scheme construction is essentially the same as the classical-oracle construction but benefits from a quadratically better counterfeit-query lower bound.The appendix contrasts the quantum-oracle bound Ω(2^n/4) with the classical-oracle construction's weaker bound.
  • Complexity-Theoretic No-Cloning: Given one copy of an unknown n-qubit state and oracle access to a phase-flip oracle Uψ, cloning requires Ω(2^n/2) quantum queries.The oracle acts as −1 on |ψ⟩ and as +1 on every state orthogonal to |ψ⟩.
  • Complexity-Theoretic No-Cloning: The no-cloning lower bound is tight because amplitude amplification can find |ψ⟩ and prepare |ψ⟩⊗2 using O(2^n/2) queries.The matching upper bound is stated for the same oracle model.
  • Generalization: With k copies of |ψ⟩ and oracle access to Uψ, preparing |ψ⟩⊗k+1 with certainty requires Ω queries in the stated worst-case setting.The proof applies the inner-product adversary method to the overlap of successful output states.
Loading 1203.4740v3…