Plaintext
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401
www.theoryofcomputing.org
Quantum Money from Hidden Subspaces
Scott Aaronson∗ Paul Christiano†
Received April 21, 2012; Revised September 17, 2012; Published March 11, 2013
Abstract: 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 multivari-
ate 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.
∗ This material is based upon work supported by the National Science Foundation under Grant No. 0844626. Also supported
by a DARPA YFA grant, an NSF STC grant, a TIBCO Chair, and a Sloan Fellowship.
† This work was done while the author was a student at MIT.
ACM Classification: F.1.2, E.3
AMS Classification: 81P68, 94A60
Key words and phrases: electronic cash, multivariate polynomials, quantum cryptography, quantum
lower bounds
© 2013 Scott Aaronson and Paul Christiano
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a009
S COTT A ARONSON AND PAUL C HRISTIANO
Our money scheme is simpler than previous public-key quantum money schemes, includ-
ing 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.
Contents
1 Introduction 352
1.1 The history of quantum money . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
1.2 The challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
1.3 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
1.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
2 Preliminaries 359
2.1 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
2.2 Quantum information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
2.3 Quantum search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
3 Formalizing quantum money 366
3.1 Quantum money schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
3.2 Mini-schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
3.3 The standard construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
4 Inner-product adversary method 372
4.1 Idea of method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
4.2 The method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
5 Classical oracle scheme 376
5.1 The hidden subspace mini-scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
5.2 Formal specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
5.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
6 Explicit quantum money scheme 383
6.1 Useful facts about polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
6.2 Explicit hidden-subspace mini-scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
6.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
6.4 Justifying our hardness assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7 Private-key quantum money 389
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 350
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
8 Open problems 392
8.1 Quantum copy-protection and more . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
Appendices 393
A Reducing completeness error 393
B Complexity-theoretic no-cloning theorem 395
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 351
S COTT A ARONSON AND PAUL C HRISTIANO
1 Introduction
“Information wants to be free”—this slogan expresses the idea that classical bits, unlike traditional
economic goods, can be copied an unlimited number of times. The copyability of classical information
is one of the foundations of the digital economy, but it is also a nuisance to governments, publishers,
software companies, and others who wish to prevent copying. Today, essentially all electronic commerce
involves a trusted third party, such as a credit card company, to mediate transactions. Without such a
third party entering at some stage, it is impossible to prevent electronic cash from being counterfeited,
regardless of what cryptographic assumptions one makes.1
Famously, though, quantum bits do not “want to be free” in the same sense that classical bits do:
in many respects, they behave more like gold, oil, or other traditional economic goods. Indeed, the
No-Cloning Theorem, which is an immediate consequence of the linearity of quantum mechanics, says
that there is no physical procedure that takes as input an unknown2 quantum pure state |ψi, and that
produces as output two unentangled copies of |ψi, or even a close approximation thereof. The No-Cloning
Theorem is closely related to the uncertainty principle, which says that there exist “complementary”
properties of a quantum state (for example, its position and momentum) that cannot both be measured to
unlimited accuracy.3
1.1 The history of quantum money
But can one actually exploit the No-Cloning Theorem to achieve classically-impossible cryptographic
tasks? This question was first asked by Wiesner [42], in a remarkable paper written around 1970 (but only
published in 1983) that arguably founded quantum information science. In that paper, Wiesner proposed
a scheme for quantum money that would be physically impossible to clone. In Wiesner’s scheme, each
“banknote” would consist of a classical serial number s, together with a quantum state |ψs i consisting of
n unentangled qubits, each one
|0i + |1i |0i − |1i
|0i , |1i , √ , or √
2 2
with equal probability. The issuing bank would maintain a giant database, which stored a classical
description of |ψs i for each serial number s. Whenever someone wanted to verify a banknote, he or she
would take it back to the bank—whereupon the bank would use its knowledge of how |ψs i was prepared
to measure each qubit in the appropriate basis, and check that it got the correct outcomes. On the other
hand, it can be proved [33] that someone who did not know the appropriate bases could copy the banknote
with success probability at most (3/4)n .
Though historically revolutionary, Wiesner’s money scheme suffered at least three drawbacks:
1 The recent Bitcoin system is an interesting illustration of this principle: it gets rid of the centralized third party, but still
uses a “third party” distributed over the community of Bitcoin users.
2 The adjective “unknown” is needed because, if we knew a classical description of a procedure to prepare |ψi, then of
course we could run that procedure multiple times to prepare multiple copies.
3 Indeed, if we could copy |ψi, then we could violate the uncertainty principle by measuring one observable (such as position)
on some copies, and a complementary observable (such as momentum) on other copies. Conversely, if we could measure all the
properties of |ψi to unlimited accuracy, then we could use the measurement results to create additional copies of |ψi.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 352
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
(1) The “Verifiability Problem”: The only entity that can verify a banknote is the bank that printed
it.
(2) The “Online Attack Problem”: A counterfeiter able to submit banknotes for verification, and get
them back afterward, can easily break Wiesner’s scheme ([30, 3]; see also Section 7).
(3) The “Giant Database Problem”: The bank needs to maintain a database with an entry for every
banknote in circulation.
In followup work in 1982, Bennett, Brassard, Breidbart, and Wiesner [15] (henceforth BBBW) at
least showed how to eliminate the giant database problem: namely, by generating the state |ψs i = |ψ fk (s) i
using a pseudorandom function fk , with key k known only by the bank. Unlike Wiesner’s original scheme,
the BBBW scheme is no longer information-theoretically secure: a counterfeiter can recover k given
exponential computation time. On the other hand, a counterfeiter cannot break the scheme in polynomial
time, unless it can also distinguish fk from a random function.
These early ideas about quantum money inspired the field of quantum cryptography [14]. But
strangely, the subject of quantum money itself lay dormant for more than two decades, even as interest
in quantum computing exploded. However, the past few years have witnessed a “quantum money
renaissance.” Some recent work has offered partial solutions to the verifiability problem. For example,
Mosca and Stebila [34] suggested that the bank use a blind quantum computing protocol to offload the
verification of banknotes to local merchants, while Gavinsky [25] (see also followup work by Molina et
al. [33] and Pastawski et al. [37]) proposed a variant of Wiesner’s scheme that requires only classical
communication between the merchant and bank.
However, most of the focus today is on a more ambitious goal: namely, creating what Aaronson [3]
called public-key quantum money, or quantum money that anyone could authenticate, not just the bank
that printed it. As with public-key cryptography in the 1970s, it is far from obvious a priori whether
public-key quantum money is possible at all. Can a bank publish a description of a quantum circuit that
lets people feasibly recognize a state |ψi, but does not let them feasibly prepare or even copy |ψi?
Aaronson [3] gave the first formal treatment of public-key quantum money, as well as related notions
such as copy-protected quantum software. He proved that there exists a quantum oracle relative to which
secure public-key quantum money is possible. Unfortunately, that result, though already involved, did not
lead in any obvious way to an explicit (or “real-world”) quantum money scheme.4 He raised as an open
problem whether secure public-key quantum money is possible relative to a classical oracle. In the same
paper, Aaronson also proposed an explicit scheme, based on random stabilizer states, but could not offer
any evidence for its security. And indeed, the scheme was broken about a year afterward by Lutomirski et
al. [32], using an algorithm for finding planted cliques in random graphs due to Alon, Krivelevich, and
Sudakov [8].
Recently, Farhi et al. [24] took a completely different approach to public-key quantum money. They
proposed a quantum money scheme based on knot theory, where each banknote is a superposition over
exponentially-many oriented link diagrams. Within a given banknote, all the link diagrams L have the
4 Also, the proof of Aaronson’s result never appeared—an inexcusable debt that this paper finally repays, with interest.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 353
S COTT A ARONSON AND PAUL C HRISTIANO
same Alexander polynomial p(L) (a certain knot invariant).5 This p(L), together with a digital signature
of p(L), serves as the banknote’s “classical serial number.” Besides the unusual mathematics employed,
the work of Farhi et al. [24] (building on [32]) also introduced an idea that will play a major role in
our work. That idea is to construct public-key quantum money schemes by composing two “simpler”
ingredients: first, objects that we call mini-schemes; and second, classical digital signature schemes.
The main disadvantage of the knot-based scheme, which it shares with every previous scheme, is
that no one can say much about its security—other than that it has not yet been broken, and that various
known counterfeiting strategies fail. Indeed, even characterizing which quantum states Farhi et al.’s
verification procedure accepts remains a difficult open problem, on which progress seems likely to require
major advances in knot theory! In other words, there might be states that look completely different from
“legitimate banknotes,” but are still accepted with high probability.
In followup work, Lutomirski [31] proposed an “abstract” version of the knot scheme, which gets rid
of the link diagrams and Alexander polynomials, and simply uses a classical oracle to achieve the same
purposes. Lutomirski raised the challenge of proving that this oracle scheme is secure—in which case,
it would have yielded the first public-key quantum money scheme that was proven secure relative to a
classical oracle. Unfortunately, proving the security of Lutomirski’s scheme remains open, and seems
hard.6
As alluded to earlier, there is already some research on ways to break quantum money schemes.
Besides the papers by Lutomirski [30] and Lutomirski et al. [32] mentioned before, let us mention the
beautiful work of Farhi et al. on quantum state restoration [23]. As we discuss in Section 7, quantum
state restoration can be used to break many public-key quantum money schemes: roughly speaking, any
scheme where the banknotes contain only limited entanglement, and where verification consists of a
rank-1 projective measurement. This fact explains why our scheme, like the knot-based scheme of Farhi
et al. [24], will require highly-entangled banknotes.
1.2 The challenge
Work over the past few years has revealed a surprising richness in the quantum money problem—both
in the ideas that have been used to construct public-key quantum money schemes, and in the ideas that
have been used to break them. Of course, this record also underscores the need for caution! To whatever
extent we can, we ought to hold quantum money schemes to modern cryptographic standards, and not be
satisfied with “we tried to break it and failed.”
5 Instead of knots, Farhi et al. [24] could also have used, say, superpositions over n-vertex graphs having the same eigenvalue
spectrum. But in that case, their scheme would have been breakable, the reason being that the graph isomorphism problem is
easy for random graphs. By contrast, it is not known how to solve knot isomorphism efficiently, even with a quantum computer
and even for random knots.
6 One way to understand the difficulty is that any security proof for Lutomirski’s scheme would need to contain, as a special
case, a quantum lower bound for the so-called index erasure problem [10]. In other words, any fast quantum algorithm for index
erasure would imply a break of Lutomirski’s scheme.
At present, the simplest known proof of a quantum lower bound for index erasure is via a reduction from Aaronson’s quantum
lower bound for the collision problem [1] (cf. [6]). The latter is proved using the polynomial method of Beals et al. [12]. In
this work, by contrast, we will only manage to prove the security of our oracle scheme using a specially-designed variant of
Ambainis’s quantum adversary method [9]. There is a recent lower bound for the index erasure problem using the adversary
method [10], but it is quite involved.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 354
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
It is easy to see that, if public-key quantum money is possible, then it must rely on some computational
assumption, in addition to the No-Cloning Theorem.7 The best case would be to show that secure, public-
key quantum money is possible, if (for example) there exist one-way functions resistant to quantum
attack. Unfortunately, we seem a long way from showing anything of the kind. The basic problem is
that uncloneability is a novel cryptographic requirement: something that would not even make sense in
a classical context. Indeed, work by Farhi et al. [23] and Aaronson [3] has shown that it is sometimes
possible to copy quantum banknotes, via attacks that do not even measure the banknotes in an attempt to
learn a classical secret! Rather, these attacks simply perform some unitary transformation on a legitimate
banknote |$i together with an ancilla |0i, the end result of which is to produce |$i⊗2 . Given such a strange
attack, how can one deduce the failure of any “standard” cryptographic assumption?
Yet despite the novelty of the quantum money problem—or perhaps because of it—it seems reasonable
to want some non-tautological evidence that a public-key quantum money scheme is secure. A minimal
wish-list might include:
(1) Security under some plausible assumption, of a sort cryptographers know how to evaluate. Such an
assumption should talk only about computing a classical output from a classical input; it should
have nothing to do with cloning of quantum states.
(2) A proof that the money scheme is secure against black-box counterfeiters: those that do not exploit
the structure of some cryptographic function f used in verifying the banknotes.
(3) A “simple” verification process, which accepts all valid banknotes |$i with probability 1, and
rejects all banknotes that are far from |$i.
1.3 Our results
Our main contribution is a new public-key quantum money scheme, which achieves all three items in the
wish-list above, and which is the first to achieve (1) or (2). Regardless of whether our particular scheme
stands or falls, we introduce at least four techniques that should be useful for the design and analysis of
any public-key quantum money scheme. These are:
• The “inner-product adversary method,” a new variant of Ambainis’s quantum adversary method [9]
that can be used to rule out black-box counterfeiting strategies.
• A formal proof that full-fledged quantum money schemes can be constructed out of two simpler
ingredients: (a) objects that we call mini-schemes, and (b) conventional digital signature schemes
secure against quantum attack. (Note that this construction itself, sans the analysis, was introduced
in earlier work on quantum money, by Lutomirski et al. [32] and Farhi et al. [24].)
• A method to amplify weak counterfeiters into strong ones, so that one only needs to rule out the
latter to show security.
7 This is because a counterfeiter with unlimited time could simply search for a state |ψi that the (publicly-known) verification
procedure accepted.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 355
S COTT A ARONSON AND PAUL C HRISTIANO
• A new connection between (a) the security of quantum money schemes, and (b) the security of
conventional cryptosystems against attacks that succeed with exponentially-small probabilities.
A second contribution is to construct the first private-key quantum money schemes that remain
unconditionally secure, even if the counterfeiter can interact adaptively with the bank. This gives the first
solution to the “online attack problem,” a major security hole in the Wiesner [42] and BBBW [15] schemes
pointed out by Lutomirski [30] and Aaronson [3]. These private-key schemes are direct adaptations of
our public-key scheme.
In more detail, our quantum money scheme is based on hidden subspaces of the vector space Fn2 .
Each of our money states is a uniform superposition of the vectors in a random n/2-dimensional subspace
A ≤ Fn2 . We denote this superposition by |Ai. Crucially, we can recognize the state |Ai using only
membership oracles for A and for its dual subspace A⊥ . To do so, we apply the membership oracle for
A, then a Fourier transform, then the membership oracle for A⊥ , and then a second Fourier transform to
restore the original state. We prove that this operation computes a rank-1 projection onto |Ai.
Underlying the security of our money schemes is the assertion that the states |Ai are difficult to clone,
even given membership oracles for A and A⊥ . Or more concretely: any quantum algorithm that maps |Ai
to |Ai⊗2 must make 2Ω(n) queries to the A, A⊥ oracles.
In order to prove this statement, we introduce a new method for proving lower bounds on quantum
query complexity, which we call the inner-product adversary method. This technique considers a single
counterfeiting algorithm being run in parallel to clone two distinct states |Ai and |A0 i, with each having
access to the membership oracles for A, A⊥ or A0 , A0⊥ , as appropriate. To measure how much progress the
algorithm has made, we consider the inner product between the states produced by the parallel executions:
because hA|⊗2 |A0 i⊗2 < hA|A0 i for many pairs of subspaces A, A0 , in order to succeed a counterfeiter will
have to reduce this inner product substantially. We prove that when averaged over a suitable distribution
of pairs A, A0 , the expected inner product between the two states produced by the counterfeiter cannot
decrease too much with a single query to the membership oracles. We conclude that in order to produce
|Ai⊗2 given |Ai and membership oracles for A, A⊥ , a counterfeiter must use exponentially many queries.
Having ruled out the possibility of nearly perfect cloning, we introduce a new amplification protocol,
which allows us to transform a counterfeiter who succeeds with Ω (1/ poly(n)) success probability
into a counterfeiter who succeeds with probability arbitrarily close to 1. This technique is based on
combining standard Grover search with a monotonic state amplification protocol of Tulsi, Grover, and
Patel [41], to obtain monotonic convergence with the quadratic speedup of Grover search.8 Combining
this amplification with the inner-product adversary method, and applying a random linear transformation
to convert the counterfeiter’s worst case to its average case, we conclude that no counterfeiting algorithm
can succeed with any non-negligible probability on a non-negligible fraction of states |Ai.
Using these results, how do we produce a secure quantum money scheme? We now need to step back,
and discuss some general constructions that have nothing to do with hidden subspaces in particular. Before
constructing full-fledged quantum money schemes, we find it useful—following [32, 24]—to construct
simpler objects called quantum money mini-schemes, in which the bank issues only a single money state
and maintains no secret information. Formally, a mini-scheme is a protocol Bank for outputting pairs
8 Although the “quadratic speedup” part is not strictly necessary for us, it improves our lower bound on the number of queries
the counterfeiter needs to make—to the tight one, in fact—and might be of independent interest.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 356
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
(s, ρs ) and a verification procedure Vers for identifying ρs . We say a mini-scheme is complete if the state
ρs passes the verification Vers with high probability, and we say the scheme is secure if furthermore no
counterfeiter can take a single state ρs , and produce two (possibly-entangled) states ρ1 and ρ2 which
simultaneously pass the verification procedure with non-negligible probability.
In the case of hidden subspace money, for example, we can use our uncloneability result to produce
a secure mini-scheme relative to a classical oracle. The algorithm Bank queries the classical oracle to
obtain a serial number s and the description of a subspace A. Using this description, it prepares |Ai and
publishes (s, |Ai). The verification procedure uses the serial number s as an index into another classical
oracle, which allows it to test membership in A and A⊥ . We prove that the uncloneability of the states |Ai
implies that this mini-scheme is secure.
Using a construction introduced by Lutomirski et al. [32] and Farhi et al. [24], we also show that,
given any mini-scheme M, one can obtain a full-fledged quantum money scheme by combining M with
any (classical) digital signature scheme secure against quantum attacks. In the construction of [32, 24],
the issuing bank first uses the mini-scheme to produce a pair (s, ρs ); then it digitally signs the serial
number s and distributes (s, ρs , Sign (s)) as its banknote. Our contribution is to prove rigorously that, if a
counterfeiter can break the money scheme, then it must have been able to break either the underlying
mini-scheme or else the signature scheme.
By combining this reduction with our mini-scheme, we are able to obtain a “black-box” public key
quantum money scheme relative to a classical oracle, which is unconditionally secure:
Theorem (Security of Hidden Subspace Money). Relative to some (classical) oracle A, there exists a
secure public-key quantum money scheme.
More precisely, there is an algorithm KeyGenA which outputs pairs kprivate , kpublic with security
parameter n; an algorithm BankA kprivate which generates a “quantum banknote” |$i; and a verification
algorithm VerA kpublic , |$i which tests the authenticity of a purported banknote. These algorithms are
polynomial-time and have the following properties:
Completeness: If (kprivate , kpublic ) is produced by KeyGenA , then VerA kpublic , BankA kprivate accepts
with certainty.
Soundness: Suppose a would-be polynomial-time counterfeiter with access to A and kpublic is given q
valid banknotes. If this counterfeiter outputs any number of (possibly-entangled) quantum states,
there is at most a 1/ exp(n) probability that VerA will accept more than q of them.
By adapting these ideas to the private-key setting, we are also able to provide the first private-
key quantum money scheme that is unconditionally secure, even if the counterfeiter is able to interact
adaptively with the bank. This patches a security hole in Wiesner’s original scheme which was observed
in [30, 3], but which has not previously been addressed in a provably-secure way.
Finally, we provide a candidate cryptographic protocol for obfuscating the indicator functions of
subspaces A ≤ Fn2 . In order to obfuscate a membership oracle for A, we provide a random system of
polynomials p1 , . . . , pm that vanish on A. Membership in A can be tested by evaluating the pi , but given
only the pi , we conjecture that it is difficult to recover A. Combining this protocol with the black-box
money scheme, we obtain an explicit quantum money scheme. This scheme is also the first public-key
quantum money scheme whose security can be based on a plausible “classical” cryptographic assumption.
Here is the assumption:
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 357
S COTT A ARONSON AND PAUL C HRISTIANO
Conjecture (*). Suppose A is a uniformly-random n/2-dimensional subspace of Fn2 , and that {pi }1≤i≤2n ,
{qi }1≤i≤2n are systems of degree-d polynomials from Fn2 to F2 , which vanish on A and A⊥ respectively
but are otherwise uniformly-random. Then for large enough constant d, there is no polynomial-time
quantum algorithm that takes as input descriptions of the pi and the qi , and outputs a basis for A with
success probability Ω 2 −n/2 .
Note that we can trivially guess a single nonzero A element with success probability 2−n/2 , but
2
guessing a whole basis for A would succeed with probability only 2−Ω(n ) . Conjecture (*) asserts that it
is harder to find many elements of A than to find just one element.
The following theorem says that, if a counterfeiter could break our quantum money scheme, then with
nontrivial success probability, it could also recover a description of A from the pi and the qi alone—even
without having access to a bank that provides a valid money state |Ai.
Theorem. Assuming Conjecture (*), there exists a public-key quantum money scheme with perfect
completeness and 1/ exp(n) soundness error. That is, the verifier always accepts valid banknotes, and a
would-be counterfeiter succeeds only with 1/ exp(n) probability.9
The problem of recovering a subspace A, given a system of equations that vanish on A, is closely
related to algebraic cryptanalysis, and in particular to the so-called polynomial isomorphism problem. In
the latter problem, we are given as input two polynomials p, q : Fn → F related by an unknown linear
change of basis L; the challenge is to find L. When deg(p) = deg(q) = 3, the best known algorithms for
the polynomial isomorphism problem require exponential time [38, 26, 18]. An attacker might be able
to use known techniques to effectively reduce the degree of the polynomials in our scheme by 1, at the
expense of an exponentially reduced success probability [18]. Provided the degree is at least 4, however,
recovering A seems to be well beyond existing techniques.
1.4 Motivation
Unlike the closely-related task of quantum key distribution [14] (which is already practical), quantum
money currently seems to be a long way off. The basic difficulty is how to maintain the coherence of a
quantum money state for an appreciable length of time. All money eventually loses its value unless it is
spent, but money that decohered on a scale of microseconds would be an extreme example!
So one might wonder: why develop rigorous foundations for a cryptographic functionality that seems
so far from being practical? One answer is that, just as quantum key distribution uses many of the same
ideas as private-key quantum money, but without requiring long-lasting coherence, so it is not hard to
imagine protocols that would use many of the same ideas as public-key quantum money without requiring
long-lasting coherence. Indeed, depending on the problem, rapid decoherence might be a feature rather
than a bug!
As one example, public-key quantum money that decohered quickly could be used to create non-
interactive uncloneable signatures. These are n-qubit quantum states |ψi that an agent can efficiently
9 This theorem remains true even if the statement of Conjecture (*) is weakened by adding random noise to the p and the q ,
i i
so that only a constant fraction of them vanish on A or A⊥ . The presence of noise interferes substantially with known techniques
for solving systems of equations, though an attacker who was able to recover A from a single polynomial would of course not be
hindered by such noise.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 358
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
prepare using a private key, then freely hand out to passersby. By feeding |ψi, together with the agent’s
public key, into suitable measuring equipment, anyone can verify on the spot that the agent is who she says
she is and not an impostor. Compared with classical identification protocols, the novel feature here is that
the agent does not need to respond to a challenge—for example, digitally signing a random string—but
can instead just hand out a fixed |ψi non-interactively. Furthermore, because |ψi decoheres in a matter
of seconds, and recovering a classical description of |ψi from measurements on it is computationally
intractable, someone who is given |ψi cannot use it later to impersonate the agent.
Of course, if an attacker managed to solve the technological problem of keeping |ψi coherent for
very long times, then he could break this system, by collecting one or more copies of |ψi that an agent
had handed out, and using them to impersonate the agent. But in that case, whatever method the attacker
was using to keep the states coherent could also—once discovered—be used to create a secure public-key
quantum money scheme!
However, we believe the “real” reason to study quantum money is basically the same as the “real”
reason to study quantum computing as a whole—or for that matter, to study the many interesting aspects
of classical cryptography that are equally far from application. As theoretical computer scientists, we are
in the business of mapping out the inherent capabilities and limits of information processing.
In our case, what quantum money provides is a near-ideal playground for understanding the implica-
tions of the uncertainty principle and the No-Cloning Theorem. In the early days of quantum mechanics,
Bohr [16] and others argued that the uncertainty principle requires us to change our conception of science
itself—their basic argument being that, in physics, predictions are only ever as good as our knowledge of
a system’s initial state |ψi, but the uncertainty principle might mean that the initial state is unknowable
even with arbitrarily-precise measurements.
But does this argument have any “teeth”? In other words: among the properties of a quantum state
|ψi that make the state impossible to learn precisely or to duplicate, can any of those properties ever
matter empirically? To us, quantum money is interesting precisely because it gives one of the clearest
examples where the answer to that question is yes.
2 Preliminaries
To begin, we fix some notation. Let [N] = {1, . . . , N}. We call a function δ (n) negligible if δ (n) =
o(1/p(n)) for every polynomial p. Given a subspace S of a vector space V , let S⊥ be the orthogonal
complement of S: that is, the set of y ∈ V such that x · y = 0 for all x ∈ S. It is not hard to show that S⊥ is
⊥
also a subspace of V , that S⊥ = S, and that these properties hold even if · is “merely” a dot product
rather than an inner product. As a word of warning, this paper will use the same notation S⊥ in two very
different contexts:
n
• When V = C2 , the orthogonal complement S⊥ of, e. g., the subspace S ≤ V spanned by a single
computational basis state |xi, has 2n − 1 dimensions and is spanned by all basis states |yi such that
y 6= x.
• When V = Fn2 , the orthogonal complement S⊥ of, e. g., the subspace S ≤ V spanned by a single string
x = x1 . . . xn , has n−1 dimensions and consists of all strings y = y1 . . . yn such that x1 y1 +· · ·+xn yn ≡
0 (mod 2).
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 359
S COTT A ARONSON AND PAUL C HRISTIANO
By a classical oracle, we will mean a unitary transformation of the form |xi → (−1) f (x) |xi, for some
Boolean function f : {0, 1}∗ → {0, 1}. Note that, unless specified otherwise, even a classical oracle can
be queried in quantum superposition. A quantum oracle, by contrast, is an arbitrary n-qubit unitary
transformation U (or rather, a collection of such transformations U, one for each n) that a quantum
algorithm can apply in a black-box fashion. Quantum oracles were defined and studied by Aaronson and
Kuperberg [5].
2.1 Cryptography
Before we construct quantum money schemes, it will be helpful to have some “conventional” crypto-
graphic primitives in our toolbox. Foremost among these is a digital signature scheme secure against
quantum chosen-message attacks. We now define digital signature schemes—both for completeness, and
to fix the quantum attack model that is relevant for us.
Definition 2.1 (Digital Signature Schemes). A (classical, public-key) digital signature scheme D
consists of three probabilistic polynomial-time classical algorithms:
• KeyGen, which takes as input a security parameter 0n , and generates a key pair kprivate , kpublic .
• Sign, which takes as input kprivate and a message x, and generates a signature Sign kprivate , x .10
• Ver, which takes as input kpublic , a message x, and a claimed signature w, and either accepts or
rejects.
We say D has completeness error ε if Ver kpublic , x,Sign x, kprivate accepts with probability at
least 1 − ε for all messages x and key pairs kprivate , kpublic . Here the probability is over the behavior of
Ver and Sign.
Let C (the counterfeiter) be a quantum circuit of size poly (n) that takes kpublic as input11 and does
the following:
(1) Probabilistically generates a classical list of messages x1 , . . . , xm , and submits them to a signing
oracle O.
(2) Gets back independently-generated signatures w1 , . . . , wm , where wi := Sign kprivate , xi .
(3) Outputs a pair (x, w).
/ {x1 , . . . , xm } and Ver kpublic , x, w accepts. We say D has soundness error
We say C succeeds if x ∈
δ if every counterfeiter
C succeeds with probability at most δ . Here the probability is over the key pair
kprivate , kpublic and the behavior of C, Sign, and Ver.
We call D secure against nonadaptive quantum chosen-message attacks if it has completeness
error ≤ 1/3 and negligible soundness error.
10 We indulge in slight abuse of notation, since if Sign is randomized then the signature need not be a function of k
private and x.
11 Actually, for our security proofs, it suffices to consider a weaker attack model, in which C only receives k
public at the same
time as it receives w1 , . . . , wm . This model was called “existential unforgeability under static chosen-message attacks” by Cash
et al. [20]. We thank an anonymous reviewer for this observation.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 360
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Intuitively, we call a signature scheme “secure” if no quantum counterfeiter with nonadaptive,
classical access to a signing oracle O can forge a signature for any message that it did not submit to O.
Depending on the application, one might want to generalize Definition 2.1 in various ways: for example,
by giving the counterfeiter adaptive or quantum access to O, or by letting KeyGen, Sign, and Ver be
quantum algorithms themselves. For this paper, however, Definition 2.1 provides all we need.
Do signature schemes secure against quantum attack exist? Naturally, signature schemes based on
RSA or other number-theoretic problems can all be broken by a quantum computer. However, building on
earlier work by Naor and Yung [35] (among many others), Rompel [40] showed that a secure public-key
signature scheme can be constructed from any one-way function—not necessarily a trapdoor function.
Furthermore, Rompel’s security reduction, from breaking the signature scheme to inverting the one-way
function, is black-box: in particular, nothing in it depends on the assumption that the adversary is classical
rather than quantum. We therefore get the following consequence:
Theorem 2.2 (Quantum-Secure Signature Schemes [40]). If there exists a (classical) one-way function f
secure against quantum attack, then there also exists a digital signature scheme secure against quantum
chosen-message attacks.
Recently, Boneh et al. [17] proved several results similar to Theorem 2.2, and they needed nontrivial
work to do so. However, a crucial difference is that Boneh et al. were (justifiably) concerned with quantum
adversaries who can make quantum queries to the signing oracle O. By contrast, as mentioned earlier, for
our application it suffices to consider adversaries who query O classically—and in that case, the standard
security reductions go through essentially without change.
Let us state another consequence of Theorem 2.2, which will be useful for our oracle construction in
Section 5.
Theorem 2.3 (Relativized Quantum-Secure Signatures). Relative to a suitable oracle A, there exists a
digital signature scheme secure against quantum chosen-message attacks.
Proof sketch. It is easy to give an oracle A : {0, 1}∗ → {0, 1} relative to which there exists a one-way
function fn : {0, 1}n → {0, 1} p(n) secure against quantum adversaries. Indeed, we can let A be a random
oracle, and then define
fn (x) := A (x, 1) . . . A (x, p (n))
directly in terms of A. Assume p (n) ≥ n. Then the lower bound on the quantum query complexity of
function inversion, proved by Bennett et al. [13] and Ambainis [9], straightforwardly
√ implies that any
quantum algorithm to invert fn , with success probability ε > 0, must make Ω(2n/2 ε) quantum queries
to A.
Now, the security reduction of Rompel [40] is not only black-box but relativizing: that is, it goes
through if all legitimate and malicious parties have access to the same oracle A. So by Theorem 2.2,
starting from { fn } one can construct a digital signature scheme relative to the same oracle A, which is
secure against quantum chosen-message attacks.
2.2 Quantum information
Let us collect a few facts about quantum pure and mixed states that are used in the paper. We assume
basic familiarity with the formalism of bras, kets, density matrices, etc.; see Nielsen and Chuang [36] for
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 361
S COTT A ARONSON AND PAUL C HRISTIANO
a good overview.
Given two mixed states ρ and σ , their trace distance is defined as
1 N
D (ρ, σ ) := ∑ |λi | ,
2 i=1
where λ1 , . . . , λN are the eigenvalues of ρ − σ . Trace distance is a metric and satisfies 0 ≤ D (ρ, σ ) ≤ 1.
Also, the fidelity 0 ≤ F (ρ, σ ) ≤ 1 is defined, in this paper, as the maximum of |hψ|ϕi| over all purifications
|ψi of ρ and |ϕi of σ .12 By extension, given a subspace S, we let F (ρ, S) be the maximum of |hψ|ϕi|
over all purifications |ψi of ρ and all unit vectors |ϕi ∈ S. Trace distance and fidelity are related as
follows [36]:
Proposition 2.4. For all mixed states ρ, σ ,
q
D (ρ, σ ) ≤ 1 − F (ρ, σ )2 ,
with equality if ρ or σ is pure.
While fidelity is not a metric, it does satisfy the following inequality, which will be helpful in
Section 5.
Lemma 2.5 (“Triangle Inequality” for Fidelity). Suppose hψ| ρ |ψi ≥ 1 − ε and hϕ| σ |ϕi ≥ 1 − ε. Then
F (ρ, σ ) ≤ |hψ|ϕi| + 2ε 1/4 .
Proof. By Proposition 2.4, p √
D (ρ, |ψi) ≤ 1 − hψ| ρ |ψi ≤ ε ,
√
and likewise D (σ , |ϕi) ≤ ε. Thus, since trace distance satisfies the triangle inequality,
D (ρ, σ ) ≥ D (|ψi , |ϕi) − D (ρ, |ψi) − D (σ , |ϕi)
√
q
≥ 1 − |hψ|ϕi|2 − 2 ε .
Then
q
F (ρ, σ ) ≤ 1 − D (ρ, σ )2
s
√ 2
q
2
≤ 1− 1 − |hψ|ϕi| − 2 ε
√
q
≤ |hψ|ϕi|2 + 4 ε
≤ |hψ|ϕi| + 2ε 1/4 .
12 Some authors instead define “fidelity” as the maximum of |hψ|ϕi|2 .
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 362
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Finally, the following lemma of Aaronson [2] will imply that, as long as a quantum money scheme
has small completeness error (i.e., small probability of rejecting a valid banknote), the banknotes can be
reused many times.
Lemma 2.6 (“Almost As Good As New Lemma” [2]). Suppose a measurement on a mixed state ρ yields
√ with probability 1 − ε. Then after the measurement, one can recover a state ρ such
a particular outcome e
that kρe − ρktr ≤ ε.
2.3 Quantum search
In our security proof for quantum money, an important step will be to amplify a counterfeiter who copies
a banknote $ with any non-negligible fidelity to a counterfeiter who copies $ almost perfectly. Taking the
contrapositive, this will imply that to rule out the former sort of counterfeiter, it suffices to rule out the
latter.
In this section, we first review two variants of Grover’s search algorithm [27] that are useful for
amplifying the fidelity of quantum states. We then introduce a variant that combines the advantages of
both.
Assume we are given a pure initial state |Initi, in some Hilbert space H. Our goal is to map |Initi to a
final state |Ψi that lies in (or close to) a “good subspace” G ≤ H. We have oracle access to two unitary
transformations:
• UInit , which maps |Initi to − |Initi, and acts as the identity on all |vi orthogonal to |Initi.
• UG , which maps |vi to − |vi for all |vi ∈ G, and acts as the identity on all |vi orthogonal to G.
We are promised that the fidelity of the initial state with G,
F (|Initi , G) = max hInit |ψi ,
|ψi∈G
is at least some ε > 0.
In this scenario, provided F (|Initi , G) is known, the amplitude amplification framework of Brassard,
Høyer, Mosca, and Tapp [19] lets us prepare a state close to G using only Θ(1/ε) iterations:
Lemma 2.7 (Amplitude Amplification [19]). Write |Initi as sin θ |Goodi + cos θ |Badi, where |Goodi
is the unit vector formed by projecting |Initi onto G, and |Badi is orthogonal to |Goodi. Then by using
O (T ) oracle calls to UInit and UG , we can prepare the state
|ΦT i := sin [(2T + 1) θ ] |Goodi + cos [(2T + 1) θ ] |Badi .
Note that Grover’s algorithm is simply a special case of Lemma 2.7, where |Initi is the uniform
superposition over N basis states |1i , . . . , |Ni, and G is the subspace spanned by “marked” states.
However, Lemma 2.7 has an annoying drawback, which it shares with ordinary Grover search.
Namely, the algorithm does not converge monotonically toward the target subspace G, but could instead
“wildly overshoot it,” cycling around the 2-dimensional subspace spanned by |Badi and |Goodi. If we
know the fidelity F(| Initi, G) in advance (rather than just a lower bound on the fidelity), or if we can
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 363
S COTT A ARONSON AND PAUL C HRISTIANO
prepare new copies of |Initi “free of charge” in case of failure, then this overshooting is not a serious
problem. Alas, neither of those conditions will hold in our application.
Fortunately, for independent reasons, in 2005 Tulsi, Grover, and Patel [41] introduced a new quantum
search algorithm that does guarantee monotonic convergence toward G, by alternating unitary trans-
formations with measurements. (Their algorithm was later simplified and improved by Chakraborty,
Radhakrishnan, and Raghunathan [21].)
Lemma 2.8 (Fixed-Point Quantum Search [41, 21]). By using T oracle calls to UInit and UG , we can
prepare a state |Ψi such that F (|Ψi , G) ≥ 1 − exp(−T ε 2 ).
Rearranging, Lemma 2.8 lets us prepare a state |Ψi such that F(|Ψi, G) ≥ 1 − δ using
1 1
T = O 2 log
ε δ
iterations. On the positive side, the dependence on 1/δ in this bound is logarithmic: we get not only
monotonic convergence toward G, but exponentially-fast convergence. On the negative side, notice
that the dependence on ε has worsened from 1/ε to 1/ε 2 —negating the quadratic speedup that was the
original point of quantum search!
In the rest of this section, we give a “hybrid” quantum search algorithm that combines the advantages
of Lemmas 2.7 and 2.8—i.e., it converges monotonically toward the target subspace G (rather than
“overshooting” G), but also achieves a quadratic speedup. In the context of our security proof for quantum
money, this hybrid algorithm will lead to a quadratically-better (and in fact, tight) lower bound on
the number of queries that a counterfeiter needs to make, compared to what we would get from using
Lemma 2.8 alone. While this quadratic improvement is perhaps only of moderate interest, we include the
algorithm in the hope that it will find other applications.
We first give a technical lemma needed to analyze our algorithm.
Lemma 2.9. For all L, β , η, γ, there are at most (L/β + 1) (2η + 1) integers T ∈ {0, . . . , L} such that
|T − (β n + γ)| < η for some integer n.
Proof. The real interval [0, L] can intersect at most L/β + 1 intervals (β n + γ − η, β n + γ + η), and each
such interval can contain at most 2η + 1 integer points.
We now give our hybrid of Lemmas 2.7 and 2.8.
Theorem 2.10 (Faster Fixed-Point Search). Let δ ≥ 2ε. Then by using
log 1/δ
O
εδ 2
oracle calls to UInit and UG , we can prepare a state ρ such that F (ρ, G) ≥ 1 − δ .
Proof. Let ξ := arcsin ε; note that ε ≤ ξ ≤ π2 ε. Also let L := d100/ξ e and R := (25/δ 2 ) (2 + log(1/δ )).
Then the algorithm is as follows:
(1) Choose an integer T ∈ {0, . . . , L} uniformly at random.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 364
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
(2) Apply T iterations of amplitude amplification with |Initi as the initial state and G as the target
subspace (as in Lemma 2.7), to obtain a state |ΦT i.
(3) Apply R iterations of fixed-point quantum search with |ΦT i as the initial state and G as the target
subspace (as in Lemma 2.8), to obtain a state |ΨT i.
The final output of the above algorithm is
ρ= E |ΨT i hΨT | .
T ∈{0,...,L}
Also, the total number of oracle calls to UInit and UG is
log 1/δ
O (T R) = O .
εδ 2
(The reason this number scales like T R rather than T + R is that, in step (3), each time we reflect about
the initial state |ΦT i we need to rerun step (2). Thus, we need Θ (T ) oracle calls within each of the R
iterations.)
By Lemma 2.7, after step (2) we have a state |ΦT i such that
F |ΦT i , G = hΦT | Goodi = sin [(2T + 1) ξ ] .
So for any α ∈ (0, 1),
Pr F (|ΦT i , G) < α = Pr |sin [(2T + 1) ξ ]| < α
T ∈{0,...,L} T ∈{0,...,L}
= Pr ∃n ∈ Z : |(2T + 1) ξ − πn| < arcsin α
T ∈{0,...,L}
L arcsin α
π/2ξ
+ 1 ξ
+ 1
≤
L+1
2 2ξ arcsin α ξ
≤ arcsin α + + +
π π 100 100
≤ 1.02 (α + ε) ,
where the third line uses Lemma 2.9.
Now assume F(|ΦT i, G) ≥ α. Then by Lemma 2.8, after step (3) we have a state |ΨT i such that
F(|ΦT i, G) ≥ 1 − exp −Rα 2 .
Let us now make the choice α := δ /5. Then by the union bound, the “average” output ρ = ET [|ΨT i hΨT |]
satisfies
1 − F (ρ, G) ≤ 1.02 (α + ε) + exp −Rα 2
Rδ 2
≤ 0.204δ + 0.51δ + exp −
25
<δ.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 365
S COTT A ARONSON AND PAUL C HRISTIANO
Note that our hybrid loses the property of exponentially-fast convergence toward the target subspace
G, but that property will not be important for us anyway. We leave as an open problem whether there
exists a hybrid algorithm with exponentially-fast convergence.
3 Formalizing quantum money
In this section, we first give a formal cryptographic definition of public-key quantum money schemes.
Our definition is similar to that of Aaronson [3]. However, following [32, 24], we next define the notion
of a quantum money mini-scheme, which is easier to construct and analyze than a full-blown quantum
money scheme. A mini-scheme is basically a quantum money scheme where each banknote includes a
classical serial number; where the only security requirement is that producing a second banknote with
the same serial number is intractable; and where there is no public or private key (since given the lax
security requirement, there is no need for one). We then prove two general results: the amplification of
weak counterfeiters into strong ones (Theorem 3.5), and the construction of full-blown quantum money
schemes from mini-schemes together with quantumly-secure digital signature schemes (Theorem 3.6).
3.1 Quantum money schemes
Intuitively, a public-key quantum money scheme is a scheme by which
(1) a trusted “bank” can feasibly generate an unlimited number of quantum banknotes,
(2) anyone can feasibly verify a valid banknote as having come from the bank, but
(3) no one besides the bank can feasibly map q = poly (n) banknotes to r > q banknotes with any
non-negligible success probability.13
We now make the notion more formal.
Definition 3.1 (Quantum Money Schemes). A public-key quantum money scheme S consists of three
polynomial-time quantum algorithms:
• KeyGen, which n
takes as input a security parameter 0 , and probabilistically generates a key pair
kprivate , kpublic .
• Bank, which takes as input kprivate , and probabilistically generates a quantum state $ called a
banknote. (Usually $ will be an ordered pair (s, ρs ), consisting of a classical serial number s and
a quantum money state ρs , but this is not strictly necessary.)
• Ver, which takes as input kpublic and an alleged banknote /c, and either accepts or rejects.
13 Previously, Aaronson [3] required only that no polynomial-time counterfeiter could increase its expected number of valid
banknotes. However, the stronger condition required here is both achievable, and seemingly more natural from the standpoint of
security proofs.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 366
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
We say S has completeness error ε if Ver kpublic , $ accepts with probability at least 1 − ε for all
public keys kpublic and valid banknotes $. If ε = 0 then S has perfect completeness.
Let Count (the money counter) take as input kpublic as well as a collection of (possibly-entangled)
alleged banknotes /c1 , . . . , /cr , and output the number of indices i ∈ [r] such that Ver kpublic
, /ci accepts.
Then we say S has soundness error δ if, given any quantum circuit C kpublic , $1 , . . . , $q of size poly (n)
(called the counterfeiter), which maps q = poly (n) valid banknotes $1 , . . . , $q to r = poly (n) (possibly-
entangled) alleged banknotes /c1 , . . . , /cr ,
Pr Count kpublic ,C kpublic , $1 , . . . , $q > q ≤ δ .
Here the probability
is over the key pair kprivate , kpublic , valid banknotes $1 , . . . , $q generated by
Bank kprivate , and the behavior of Count and C.
We call S secure if it has completeness error ≤ 1/3 and negligible soundness error.
In Appendix A, we show that the completeness error in any quantum money scheme can be amplified
to 1/2poly(n) , at the cost of only a small increase in the soundness error. Note that, by Lemma 2.6 (the
“Almost As Good As New Lemma”), once we make the completeness error exponentially small in n,
we can also give our scheme the property that any banknote $ can be verified exp (n) times, before $
gets “worn out” by repeated measurements. This observation is part of what justifies our use of the term
“money.”14
In this paper, we will often consider relativized quantum money schemes, which simply means that
the three procedures KeyGen, Bank, Ver—as well as the counterfeiter C—all get access to exactly the
same oracle A : {0, 1}∗ → {0, 1}. We will also consider relativized digital signature schemes, etc., which
are defined analogously.
A private-key quantum money scheme is the same as a public-key scheme, except that the counter-
feiter C no longer gets access to kpublic . (Thus, we might as well set k := kpublic = kprivate , since the public
and private keys no longer play separate roles.) We call a private-key scheme query-secure—a notion
“intermediate” between private-key and public-key—if the counterfeiter C is allowed to interact repeatedly
with the bank. Given any alleged banknote σ , the bank runs the verification procedure Ver (k, σ ), then
returns to C both the classical result (i.e., accept or reject) and the post-measurement quantum state σe .
3.2 Mini-schemes
While Definition 3.1 captures our intuitive requirements for a public-key quantum money scheme,
experience has shown that it is cumbersome to work with in practice. So following Lutomirski et al. [32]
and Farhi et al. [24], in this section we define a simpler primitive called mini-schemes. We also prove
an amplification theorem for a large class of mini-schemes. Then, in Section 3.3, we will explain how
mini-schemes can be generically combined with conventional digital signature schemes to create full
public-key quantum money schemes.
Definition 3.2 (Mini-Schemes). A (public-key) mini-scheme M consists of two polynomial-time quan-
tum algorithms:
14 By contrast, BBBW [15] introduced the term “subway tokens” for quantum money states that get destroyed immediately
upon verification.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 367
S COTT A ARONSON AND PAUL C HRISTIANO
• Bank, which takes as input a security parameter 0n , and probabilistically generates a banknote
$ = (s, ρs ), where s is a classical serial number, and ρs is a quantum money state.
• Ver, which takes as input an alleged banknote /c, and either accepts or rejects.
We say M has completeness error ε if Ver ($) accepts with probability at least 1 − ε for all valid
banknotes $. If ε = 0 then M has perfect completeness. If, furthermore, ρs = |ψs i hψs | is always a pure
state, and Ver simply consists of a projective measurement onto the rank-1 subspace spanned by |ψs i,
then we say M is projective.15
Let Ver2 (the double verifier) take as input a single serial number s as well as two (possibly-entangled)
states σ1 and σ2 , and accept if and only Ver (s, σ1 ) and Ver (s, σ2 ) both accept. We say M has soundness
error δ if, given any quantum circuit C of size poly (n) (the counterfeiter), Ver2 (s,C ($)) accepts with
probability at most δ . Here the probability is over the banknote $ output by Bank (0n ), as well as the
behavior of Ver2 and C.
We call M secure if it has completeness error ≤ 1/3 and negligible soundness error.
We observe a simple relationship between Definitions 3.1 and 3.2:
Proposition 3.3. If there exists a secure public-key money scheme S = (KeyGenS , BankS , VerS ), then
there also exists a secure mini-scheme M = (BankM , VerM ).
Proof. Each banknote output by BankM (0n ) will have the form
kpublic , BankS kprivate ,
where kprivate , kpublic is a key pair output by KeyGenS (0n ). Then VerM (s, ρs ) will accept if and only
if VerS (s, ρs ) does. Any counterfeiter CM against M can be converted directly into a counterfeiter CS
against S.
Call a mini-scheme M = (Bank, Ver) secret-based if Bank works by first generating a uniformly-
random classical string r, and then generating a banknote $r := (sr , ρr ). Intuitively, in a secret-based
scheme, the bank can generate many identical banknotes by simply reusing r, while in a non-secret-based
scheme, not even the bank might be able to generate two identical banknotes. Here is an interesting
observation:
Proposition 3.4. If there exists a secure, secret-based mini-scheme, then there also exists a one-way
function secure against quantum attack.
Proof. The desired OWF is SerialNum (r) := sr . If there existed a polynomial-time quantum algorithm
to recover r given sr , then we could use that algorithm to produce an unlimited number of additional
banknotes $r .
15 We similarly call a full quantum money scheme projective, if Ver ($) consists of a measurement on one part of $ in the
computational basis, followed by a rank-1 projective measurement on the remaining part.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 368
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
All of the mini-schemes developed in this paper will be secret-based. By contrast, the earlier schemes
of Lutomirski et al. [32] and Farhi et al. [24] are non-secret-based, since the serial number s is only
obtained as the outcome of a quantum measurement.
The following result is one of the most useful in the paper. Intuitively, it says that in projective
mini-schemes, a counterfeiter that copies a banknote with any non-negligible fidelity can be “amplified”
to a counterfeiter that copies the banknote almost perfectly—or conversely, that to rule out the former
sort of counterfeiter, it suffices to rule out the latter. The proof makes essential use of the amplitude
amplification results from Section 2.3.
Theorem 3.5 (Amplification of Counterfeiters). Let M = (Bank, Ver) be a projective mini-scheme, and
let $ = (s, ρ) be a valid banknote in M. Suppose there exists a counterfeiter C that copies $ with
probability ε > 0: that is,
Pr [Ver2 (s,C ($)) accepts] ≥ ε.
Then for all δ > 0, there is also a modified counterfeiter C0 (depending only on ε and δ , not $), which
makes !
log 1/δ
O √ √
ε ε +δ2
queries to C, C−1 , and Ver and which satisfies
Pr Ver2 s,C0 ($) accepts ≥ 1 − δ .
Proof. Write $ as a mixture of pure states:
$ = ∑ pi |ψi i hψi | .
By linearity, clearly it suffices to show that
Pr Ver2 s,C0 (|ψi i) accepts ≥ 1 − δ
for all i such that pi > 0. We focus on |ψi := |ψ1 i without loss of generality.
By assumption, there exists a subspace S such that
Pr [Ver (ρ) accepts] = F (ρ, S)2
for all ρ. Then F ($, S) = F (|ψi , S) = 1.
Now, just as Ver is simply a projector onto S, so Ver2 is a projector onto S⊗2 . Thus
√
F C (|ψi) , S⊗2 ≥ ε.
So consider performing a fixed-point Grover search, with C (|ψi) as the initial state and S⊗2 as the
target subspace. By Lemma 2.8, this will produce a state ρ such that F ρ, S⊗2 ≥ 1 − δ using
O ((1/ε) log(1/δ )) Grover iterations. Each iteration requires a reflection about C (|ψi) and a reflec-
tion about S⊗2 , which can be implemented using O (1) queries to C,C−1 and Ver respectively. Therefore
the number of queries to C,C−1 and Ver is O ((1/ε) log(1/δ )) as well.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 369
S COTT A ARONSON AND PAUL C HRISTIANO
If δ is large
compared to ε, then we can instead use Theorem 2.10, which produces a state ρ such
that F ρ, S⊗2 ≥ 1 − δ using
1 1
O √ 2 log
εδ δ
iterations. Taking the minimum of the two bounds gives us the claimed bound on query complexity.
Theorem 3.5 is unlikely to hold for arbitrary (non-projective) mini-schemes, for the simple reason
that we can always create a mini-scheme where Ver accepts any state with some small nonzero probability
ε. We leave it as an open problem to find the largest class of mini-schemes for which Theorem 3.5 holds.
3.3 The standard construction
Following Lutomirski et al. [32] and Farhi et al. [24], we can now define a “standard construction” of
public-key quantum money schemes from mini-schemes and digital signature schemes. Given a mini-
scheme M = (BankM , VerM ), and a signature D = (KeyGenD , SignD , VerD ), we define the quantum
money scheme S = (KeyGenS , BankS , VerS ) as follows:
• KeyGenS is simply KeyGenD from the digital signature scheme.
• BankS first calls BankM from the mini-scheme to obtain a banknote (s, ρ). It then outputs (s, ρ)
together with a digital signature of the serial number s:
BankS kprivate := s, SignD kprivate , s , ρ .
• VerS accepts an alleged banknote (s, w, σ ), if and only if VerM (s, σ ) and VerD kpublic , s, w both
accept.
We now prove the above construction’s security.
Theorem 3.6 (Security of the Standard Construction). Suppose M is a secure mini-scheme, and D is a
digital signature scheme secure against quantum chosen-message attacks. Then S is a secure public-key
quantum money scheme.
Proof. The intuition behind the proof is extremely simple: by requiring digital signatures for the serial
numbers, we can force a counterfeiter to copy one of its existing banknotes, rather than creating a new
banknote with a new serial number. In this way, we force the counterfeiter to break the underlying
mini-scheme M, rather than doing an “end run” around M.
To formalize this intuition, suppose there exists a counterfeiter CS against S: that is, a polynomial-time
quantum algorithm such that
1
Pr Count kpublic ,CS kpublic , $1 , . . . , $q > q ≥ .
p (n)
Here $i := (si , wi , ρi ) is a valid banknote, Count is the money counter from Definition 3.1, and p is some
polynomial. Also, the probability is over the key pair kprivate , kpublic , the valid banknotes $1 , . . . , $q , and
the behavior of Count and CS . Suppose further that D is secure. Then it suffices to show that, by using
CS , we can construct a counterfeiter CM against the underlying mini-scheme M.
Let New kpublic , $1 , . . . , $q be an algorithm that does the following:
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 370
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
(1) Records the serial numbers s1 , . . . , sq of $1 , . . . , $q , and lets U := s1 , . . . , sq .
(2) Runs CS kpublic , $1 , . . . , $q , and examines the output states /c1 , . . . , /cr .
(3) Returns the number of i ∈ [r] such that VerS (/ci ) accepts, and /ci ’s serial number s0i does not belong
to U.
Then we claim that Pr New kpublic , $1 , . . . , $q > 0 is negligibly small, where the probability is over
the same variables as before. The proof is simply that, if this were not so, then we could easily create
a counterfeiter CD against the digital signature scheme D. With non-negligible probability, CD would
generate a valid signature SignD kprivate , s0i , for a message s 0 for which C had never before seen a
i D
valid signature, by running CS kpublic , $1 , . . . , $q , then measuring /ci = (s0i , w0i , ρi0 ) for a uniformly random
i ∈ [r]. (Note that CD can generate q money states $1 , . . . , $q , without knowledge of kprivate , by generating
the si and the ρi on its own, then calling the signing oracle O to get the wi .)
But now we can define a counterfeiter CM against the mini-scheme M, which works as follows:
(i) Run KeyGenD (0n ), to generate a new key pair kprivate 0 0
, kpublic .
(ii) Label the banknote to be copied (s` , ρ` ), for some ` ∈ [q] chosen uniformly at random.
(iii) Repeatedly call BankM (0n ) to generate q − 1 serial numbers and quantum money states, labeled
(si , ρi ) for all i ∈ [q] \ {`}. Let U := s1 , . . . , sq .
(iv) Generate a digital signature wi := SignD kprivate 0 , si for each i ∈ [q]. Let $i := (si , wi , ρi ).
(v) Run
the counterfeiter
CS kpublic , $1 , . . . , $q , to obtain r > q alleged banknotes /c1 , . . . , /cr where
/c j = s0j , w0j , ρ 0j .
(vi) Choose j, k ∈ [r] uniformly at random without replacement, and output ρ 0j , ρk0 as a candidate for
two copies of ρ` .
Suppose that Count > q, as happens with probability at least 1/p(n). Also suppose that New = 0,
as happens all but a negligible fraction of the time. Then by the pigeonhole principle, there must exist
indices j 6= k such that s0j = s0k . With probability at least 1/ 2r , the counterfeiter CM will find such a ( j, k)
pair. Therefore CM succeeds with overall probability Ω (1/ poly (n)).
Theorem 3.6 reduces the construction of a public-key quantum money scheme to two “smaller”
problems: constructing a mini-scheme, and constructing a signature scheme secure against quantum
attacks. In practice, however, the situation is even better, since in this paper, all of our constructions of
mini-schemes will also yield signature schemes “free of charge”! The following proposition explains
why:
Proposition 3.7. If there exists a secure, secret-based mini-scheme M, then there also exists a secure
public-key quantum money scheme S.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 371
S COTT A ARONSON AND PAUL C HRISTIANO
Proof. Starting from M, we can get a one-way function secure against quantum attack from Proposi-
tion 3.4, and hence a digital signature scheme D secure against quantum chosen-message attack from
Theorem 2.2. Combining M and D now yields S by Theorem 3.6.
Finally, let us make explicit what Theorem 3.6 means for oracle construction.
Corollary 3.8. Suppose there exists a mini-scheme M that is provably secure relative to some oracle AM
(i.e., any counterfeiter CM against M must make superpolynomially many queries to AM ). Then there
exists a public-key quantum money scheme S that is provably secure relative to some other oracle AS .
Proof. By Theorem 2.3, relative to a suitable oracle AD (in fact, a random oracle suffices), there
exists a signature scheme D, such that any quantum chosen-message attack against D must make
superpolynomially many queries to AD . The oracle AS will simply be a concatenation of AM with AD .
Relative to AS , we claim that the mini-scheme M and signature scheme D are both secure—and therefore,
by Theorem 3.6, we can construct a secure public-key quantum money scheme S.
The only worry is that a counterfeiter CM against M might gain some advantage by querying AD ;
or conversely, a counterfeiter CD against D might gain some advantage by querying AM . However, this
worry is illusory, for the simple reason that the oracles AD and AM are generated independently. Thus, if
CM can break M by querying AD , then it can also break M by querying a randomly-generated “mock-up”
A0D of AD ; and conversely, if CD can break D by querying AM , then it can also break D by querying
a randomly-generated mock-up A0M of AM . Regardless of the computational cost of generating these
mock-ups, they give us a break against D or M that makes only poly (n) oracle queries, thereby giving
the desired contradiction.
4 Inner-product adversary method
At least in the black-box setting, our goal is to create quantum money (mini-)schemes that we can
prove are secure—by showing that any counterfeiter would need to make exponentially many queries to
some oracle. Proving security results of this kind turns out to require interesting quantum lower bound
machinery. In this section, we introduce the inner-product adversary method, a new variant of Ambainis’s
quantum adversary method [9] that is well-adapted to proving the security of quantum money schemes,
and that seems likely to find other applications.
Let us explain the difficulty we need to overcome. In a public-key quantum money scheme, a
counterfeiter C has two powerful resources available:
(1) One or more copies of a “legitimate” quantum money state |ψi.
(2) Access to a verification procedure V , which accepts |ψi and rejects every state orthogonal to |ψi.
Indeed, for us, the situation is even better for C (i.e., worse for us!), since C can query not only the
verification procedure V itself, but also an underlying classical oracle U that the legitimate buyers and
sellers use to implement V . But let us ignore that issue for now.
As a first step, of course, we should understand how to rule out counterfeiting given (1) or (2)
separately. If C has a copy of |ψi, but no oracle access to V , then the impossibility of preparing |ψi |ψi
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 372
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
essentially amounts to the No-Cloning Theorem. Conversely, if C has oracle access to V , but no copy
of |ψi, then given unlimited time, C can prepare as many copies of |ψi as it wants, by using Grover’s
algorithm to search for a quantum state that V accepts. The problem is “merely” that, if |ψi has n qubits,
then Grover’s algorithm requires Θ(2n/2 ) iterations, and the BBBV hybrid argument [13] shows that
Grover’s algorithm is optimal.
What we need, then, is a theorem showing that any counterfeiter needs exponentially many queries
to V to prepare |ψi |ψi, even if the counterfeiter has a copy of |ψi to start with. Such a theorem would
contain both the No-Cloning Theorem and the BBBV hybrid argument as special cases. Aaronson [3]
called the desired generalization the Complexity-Theoretic No-Cloning Theorem, and sketched a proof
of it using Ambainis’s adversary method. Based on that result, Aaronson also argued that there exists a
quantum oracle (i.e., a black-box unitary transformation V ) relative to which secure public-key quantum
money is possible. However, the details were never published.
In this section, we prove a result—Theorem 4.2—that is much more general than Aaronson’s previous
Complexity-Theoretic No-Cloning Theorem [3]. Then, in Section 5, we apply Theorem 4.2 to prove
the security of public-key quantum money relative to a classical oracle. In Appendix B, we also apply
Theorem 4.2 to prove the “original” Complexity-Theoretic No-Cloning Theorem [3], which involves
Haar-random n-qubit states |ψi, rather than superpositions |Ai over subspaces A ≤ Fn2 .16
4.1 Idea of method
So, what is the inner-product adversary method? In Ambainis’s adversary method [9]—like in the BBBV
hybrid argument [13] from which it evolved—the basic idea is to upper-bound how much “progress” a
quantum algorithm Q can make at distinguishing pairs of oracles, as the result of a single query. Let
ΨU t be Q’s state after t queries, assuming that the oracle is U. Then normally, before any queries have
been made, we can assume that ΨU0 = ΨV0 for all oracles U and V . By contrast, after the final query
T , for all oracle pairs (U,V ) that Q is trying to distinguish, we must have (say) ΨUT |ΨVT ≤ 1/2. Thus,
if we can show that the inner product ΨU V
t |Ψt can decrease by at most ε as the result of a single query,
then it follows that Q must make Ω (1/ε) queries.
But when we try to apply the above framework to quantum money, we run into serious difficulties.
Most obviously, it is no longer true that ΨU0 = ΨV0 for all oracles U,V . Indeed, before Q makes even a
single query to its oracle V , it already has a great deal of information about V , in the form of a legitimate
money state |ψi that V accepts. The task is “merely” to prepare a second copy of a state that Q already
has! Worse yet, once we fix two oracles U and V , we find that Q generally can exploit the “head start”
provided by its initial state to decrease the inner product ΨU V
t |Ψt by a constant amount, by making
just a single query to U or V respectively.
Our solution is as follows. We first carefully choose a distribution D over oracle pairs (U,V ). We
then analyze how much the expected inner product
ΨU V
E t |Ψt
(U,V )∼D
16 For whatever it is worth, we get a lower bound of Ω(2n/2 ) on the number of queries needed to copy a Haar-random state,
which is quadratically better than the Ω(2n/4 ) that we get for subspace states.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 373
S COTT A ARONSON AND PAUL C HRISTIANO
can decrease as the result of a single query to U or V . We will find that, even if Q can substantially
decrease the inner product between ΨU t and ΨVt for some (U,V ) pairs by making a single query, it
cannot do so for most pairs.
To illustrate, let |ψi and |ϕi be two possible quantum money states, which satisfy (say) hψ|ϕi = 1/2.
Then if a counterfeiting algorithm succeeds perfectly, it must map |ψi to |ψi⊗2 , and |ϕi to |ϕi⊗2 . Since
1
hψ|⊗2 |ϕi⊗2 = (hψ|ϕi)2 = ,
4
this means that the counterfeiter must decrease the corresponding inner product by at least 1/4. However,
we will show that the average inner product can decrease by at most 1/ exp (n) as the result of a single
query. From this it will follow that the counterfeiter needs to make 2Ω(n) queries.
Let us mention that today, there are several “sophisticated” versions of the quantum adversary
method [10, 29], which can yield lower bounds for quantum state generation tasks not unlike the ones
we consider. However, a drawback of these methods is that they are extremely hard to apply to concrete
problems: doing so typically requires eigenvalue bounds, and often the use of representation theory. For
this reason, even if one of the “sophisticated” adversary methods (or a variant thereof) could be applied to
the quantum money problem, our approach might still be preferable.
4.2 The method
We now introduce the inner-product adversary method. Let O be a set of quantum oracles acting on n
n
qubits each. For each U ∈ O, assume there exists a subspace SU ≤ C2 such that
(i) U |ψi = − |ψi for all |ψi ∈ SU , and
(ii) U |ηi = |ηi for all |ηi ∈ SU⊥ .
Let R ⊂ O × O be a symmetric binary relation on O, with the properties that
/ R for all U ∈ O, and
(i) (U,U) ∈
(ii) for every U ∈ O there exists a V ∈ O such that (U,V ) ∈ R.
Suppose that for all U ∈ O and all |ηi ∈ SU⊥ , we have
h i
E F (|ηi , SV )2 ≤ ε ,
V : (U,V )∈R
where F (|ηi , SV ) = max|ψi∈SV |hη|ψi| is the fidelity between |ηi and SV . Let Q be a quantum oracle
algorithm, and let QU denote Q run with the oracle U ∈ O. Suppose QU begins in the state ΨU0 (possibly
already dependent on U). Let ΨU t denote the state of QU immediately after the t th query. Also, define
a progress measure pt by
ΨU V
pt := E t |Ψt .
U,V : (U,V )∈R
The following lemma bounds how much pt can decrease as the result of a single query.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 374
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Lemma 4.1 (Bound on Progress Rate).
√
pt ≥ pt−1 − 4 ε.
Proof. Let ΦUt denote the state of QU immediately before the t th query. Then for all t, it is clear that
Φt |Φt = Ψt−1 |ΨVt−1 : in other words, the unitary transformations that Q performs in between query
U V U
steps have no effect on the inner products. So to prove the lemma, it suffices to show the following
inequality: √
ΦU V
ΨU V
E t |Φt − E t |Ψt ≤4 ε. (*)
U,V : (U,V )∈R U,V : (U,V )∈R
Let {|ii}i∈[B] be an arbitrary orthonormal basis for Q’s workspace register. Then we can write
ΦU
t
U
= ∑ αt,i |ii ΦU
t,i
i∈[B]
U U U U
= ∑ |ii βt,i ηt,i + γt,i ψt,i ,
i∈[B]
E E 2 2 2
U ∈ S⊥ and ψ U ∈ S . (By normalization, β U + γ U = α U .) A query transforms the
where ηt,i U t,i U t,i t,i t,i
above state to
ΨU U U U U
t = ∑ |ii βt,i ηt,i − γt,i ψt,i .
i∈[B]
So for all U,V ∈ O,
U
ΦU V U V U U U
∑ t,i t,i t,i t,i βt,iV ηt,iV + γt,iV ψt,iV
t |Φt − Ψt |Ψt = β η + γ ψ
i∈[B]
U
U
− γU U V V V V
− ∑ β t,i ηt,i t,i ψt,i βt,i ηt,i − γt,i ψt,i
i∈[B]
U
V U V
= 2 ∑ β t,i γt,i ηt,i |ψt,i + γU β V
t,i t,i ψ U V
|η
t,i t,i .
i∈[B]
By Cauchy-Schwarz, the above implies that
ΦU V
t |Φt − ΨU V
t |Ψt
U
≤ 2 max ηt,i V
|ψt,i U V
+ 2 max ψt,i |ηt,i .
i∈[B] i∈[B]
Now fix U ∈ O and i ∈ [B]. Then again applying Cauchy-Schwarz,
s D
U V E 2
E ηt,i |ψt,i ≤ E U V
ηt,i |ψt,i
V : (U,V )∈R V : (U,V )∈R
s D E 2
≤ E max U |ψ
ηt,i
V : (U,V )∈R |ψi∈SV
√
≤ ε.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 375
S COTT A ARONSON AND PAUL C HRISTIANO
Hence √
U V
E ηt,i |ψt,i ≤ ε
U,V : (U,V )∈R
as well, and likewise √
U V
E ψt,i |ηt,i ≤ ε
U,V : (U,V )∈R
by symmetry. Putting everything together,
ΦU V
− ΨU V
pt−1 − pt = E t |Φt t |Ψt
U,V : (U,V )∈R
U V U V
≤2 E max ηt,i |ψt,i +2 E max ψt,i |ηt,i
U,V : (U,V )∈R i∈[B] U,V : (U,V )∈R i∈[B]
√
≤4 ε.
This proves inequality (*) and hence the lemma.
From Lemma 4.1 we immediately deduce the following.
Theorem 4.2 (Inner-Product Adversary Method). Suppose that initially ΨU0 |ΨV0 ≥ c for all (U,V )√
∈ R,
whereas by the end we need ΨUT |ΨVT ≤ d for all (U,V ) ∈ R. Then Q must make T = Ω((c − d)/ ε)
oracle queries.
5 Classical oracle scheme
In this section, we construct a mini-scheme, called the Hidden Subspace Mini-Scheme, that requires
only a classical oracle. We then use the inner-product adversary method from Section 4 to show that our
mini-scheme is secure—indeed, that any counterfeiter must make Ω 2 n/4 queries to copy a banknote.
By the results of Sections 3.3 and 2.1, our mini-scheme will automatically imply a full-blown public-key
quantum money scheme, which requires only a classical oracle and is unconditionally secure.
5.1 The hidden subspace mini-scheme
We identify n-bit strings x ∈ {0, 1}n with elements of the vector space Fn2 in the standard way. Then in
our mini-scheme, each n-qubit money state will have the form
1
|Ai := p ∑ |xi ,
|A| x∈A
where A is some randomly-chosen subspace of Fn2 (i.e., a set of codewords of a linear code), with
dim A = n/2. Let A⊥ be the orthogonal complement of A, so that dim A⊥ = n/2 as well. Notice that we
can transform |Ai to A⊥ and vice versa by simply applying H2⊗n : a Hadamard gate on each of the n
qubits, or equivalently a quantum Fourier transform over Fn2 .
The basic idea of the mini-scheme is as follows: the bank can easily prepare the quantum money state
|Ai, starting from a classical description hAi of A (e. g., a list of n/2 generators). The bank distributes the
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 376
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
state |Ai, but keeps the classical description hAi secret. Along with |Ai itself, the bank also publishes
details of how to verify |Ai by querying two classical oracles, UA and UA⊥ . The first oracle, UA , decides
membership in A: for all n-qubit basis states |xi,
(
− |xi if x ∈ A,
UA |xi =
|xi otherwise.
The second oracle, UA⊥ , decides membership in A⊥ in the same way.
Using UA , it is easy to implement a projector PA onto the set of basis states in A. To do so, simply
initialize a control qubit to
|0i + |1i
|+i = √ ,
2
then apply UA conditioned on the control qubit being in state |1i, then measure the control qubit in the
{|+i , |−i} basis, and postselect on getting the outcome |−i. Likewise, using UA⊥ , it is easy to implement
a projector PA⊥ onto the set of basis states in A⊥ . Then VA , the public verification algorithm for the
money state |Ai, will simply consist of PA , then a Fourier transform, then PA⊥ , and finally a second
Fourier transform to return the legitimate money state back to |Ai:
VA := H2⊗n PA⊥ H2⊗n PA .
We show in Lemma 5.1 that VA is just a projector onto |Ai. This means, in particular, that VA |Ai = |Ai,
and that VA accepts an arbitrary state |ψi with probability |hψ|Ai|2 . Thus, our mini-scheme is projective
and has perfect completeness.
But what about security? Intuitively, a counterfeiter could query UA or UA⊥ to find a generating set
for A or A⊥ —but that would require an exponentially-long Grover search, since |A| = A⊥ = 2n/2 2n .
Alternatively, the counterfeiter could measure |Ai in the standard or Hadamard bases—but that would
reveal just one random element of A or A⊥ . Neither ability seems useful for copying |Ai, let alone
recovering a full classical description of A.17
And indeed, using the inner-product adversary method plus some other tools, we will prove the
following tight lower bound (Theorem 5.5): even if given a single copy of |Ai, as well as oracle access to
UA and UA⊥ , a counterfeiter still needs Ω ε2n/4 queries to prepare a state that has fidelity ε with |Ai⊗2 .
This will imply that our mini-scheme has 1/ exp(n) soundness error.
5.2 Formal specification
We are not quite done, since we never explained how the bank provides access to UA and UA⊥ . Thus, in
our “final” mini-scheme M = (BankM , VerM ), the bank, verifier, and counterfeiter will all have access to
a single classical oracle U, which consists of four components:
17 Obviously, if the counterfeiter had Ω(n) copies of |Ai, then it could recover a generating set for A, by simply measuring
each copy independently in the standard basis. That is why, in our full quantum money scheme, the counterfeiter will not have
Ω(n) copies of |Ai. Instead, each banknote will involve a completely different subspace As ≤ Fn2 (parameterized by its unique
serial number s), so that measuring one banknote reveals nothing about the others.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 377
S COTT A ARONSON AND PAUL C HRISTIANO
• A banknote generator G (r), which takes as input a random string r ∈ {0, 1}n , and outputs a set of
linearly independent generators hAr i = {x1 , . . . , xn/2 } for a subspace Ar ≤ Fn2 , as well as a unique
3n-bit serial number sr ∈ {0, 1}3n . The function G is chosen uniformly at random, subject to the
constraint that the serial numbers are all distinct.18
• A serial number checker H (s), which outputs 1 if s = sr is a valid serial number for some hAr i,
and 0 otherwise.
• A primal subspace tester Tprimal , which takes an input of the form |si |xi, applies UAr to |xi if
s = sr is a valid serial number for some hAr i, and does nothing otherwise.
• A dual subspace tester Tdual , identical to Tprimal except that it applies UA⊥r instead of UAr .
Then M = (BankM , VerM ) is defined as follows:
• BankM (0n ) chooses r ∈ {0, 1}n uniformly at random. It then looks up G (r) = (sr , hAr i), and
outputs the banknote |$r i = |sr i |Ar i.
• VerM (/c) first uses H to check that /c has the form (s, ρ), where s = sr is a valid serial number. If
so, then it uses Tprimal and Tdual to apply VAr = H2⊗n PA⊥r H2⊗n PAr , and accepts if and only if VAr (ρ)
accepts.
5.3 Analysis
We now analyze the mini-scheme defined in Sections 5.1 and 5.2. For convenience, we assume for most
of the proof that the subspace A ≤ Fn2 is fixed, and that the counterfeiter (who does not know A) only has
access to the oracles UA and UA⊥ . Then, at the end, we will explain how to generalize the conclusions to
the “final” mini-scheme M.
It will be convenient to consider the subset A∗ ⊂ {0, 1}n+1 , defined by
A∗ := (0, A) ∪ (1, A⊥ ) .
n+1
Let SA∗ be the subspace of C2 that is spanned by basis states |xi such that x ∈ A∗ . Then we can
think of the pair of oracles (UA ,UA⊥ ) as being a single oracle UA∗ , which satisfies UA∗ |ψi = − |ψi for all
n+1
|ψi ∈ SA∗ , and UA∗ |ηi = |ηi for all |ηi ∈ SA⊥∗ (where here ⊥ means the orthogonal complement in C2 ,
not the orthogonal complement in Fn2 !).
Recall the definition of the verifier VA :
VA := H2⊗n PA⊥ H2⊗n PA ,
where PA and PA⊥ denote projective measurements that accept a basis state |xi if and only if x belongs to
A or A⊥ respectively. The following lemma shows that VA “works,” and indeed that it gives us a projective
mini-scheme.
18 Note that one can implement G using an ordinary random oracle. In that case, the requirement that the serial numbers are
distinct will be satisfied with probability 1 − O 2−n .
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 378
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Lemma 5.1. VA = |Ai hA| is simply a projector onto |Ai. So in particular,
Pr [VA (|ψi) accepts] = |hψ|Ai|2 .
Proof. It suffices to show that VA |Ai = |Ai and that VA |ψi = 0 for all |ψi orthogonal to |Ai. First,
VA |Ai = H2⊗n PA⊥ H2⊗n PA |Ai
= H2⊗n PA⊥ H2⊗n |Ai
= H2⊗n PA⊥ |A⊥ i
= H2⊗n |A⊥ i
= |Ai .
Second, if hψ|Ai = 0 then we can write
|ψi = ∑ cx |xi
x∈2n
where ∑x∈A cx = 0. Then
VA |ψi = H2⊗n PA⊥ H2⊗n PA ∑ cx |xi
x∈2n
= H2⊗n PA⊥ H2⊗n ∑ cx |xi
x∈A
1
= √ H2⊗n PA⊥ ∑ cx ∑ |yi
2n x∈A y⊥x
1
= √ H2⊗n ∑ |yi ∑ cx
2n y∈A⊥ x∈A
= 0.
We now show that perfect counterfeiting requires exponentially many queries to UA∗ .
Theorem 5.2 (Lower Bound for Perfect Counterfeiting). Given one copy of |Ai, as well as oracle access
to UA∗ , a counterfeiter needs Ω(2n/4 ) queries to prepare |Ai⊗2 with certainty (for a worst-case |Ai).
Proof. We will apply Theorem 4.2. Let the set O contain UA∗ for every possible subspace A ≤ Fn2 with
dim A = n/2. Also, put (UA∗ ,UB∗ ) ∈ R if and only if dim (A ∩ B) = n/2 − 1. Then given UA∗ ∈ O and
|ηi ∈ SA⊥∗ , let
|ηi = ∑ αx |xi .
x∈{0,1}n+1 \A∗
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 379
S COTT A ARONSON AND PAUL C HRISTIANO
We have
" #
h i
E F (|ηi , SB∗ )2 = E ∑ |αx |2
UB∗ : (UA∗ ,UB∗ )∈R B : dim(B)=n/2,dim(A∩B)=n/2−1 x∈B∗ \A∗
∗
≤ max Pr [x ∈ B ]
x∈{0,1}n+1 \A∗ B : dim(B)=n/2,dim(A∩B)=n/2−1
= max Pr [x ∈ B]
x∈{0,1}n \A B : dim(B)=n/2,dim(A∩B)=n/2−1
|B \ A|
= (for dim (B) = n/2, dim (A ∩ B) = n/2 − 1)
|{0, 1}n \ A|
2n/2−1
=
2n − 2n/2
1
≤ n/2 .
2
Here the first line uses the definition of fidelity, the second line uses the easy direction of the minimax
theorem, the third line uses the symmetry between A and A⊥ , and the fourth line uses the symmetry
among all 2n − 2n/2 strings x ∈ {0, 1}n \ A. The conclusion is that we can set ε := 2−n/2 .
Fix (UA∗ ,UB∗ ) ∈ R. Then |hA|Bi| = 1/2. On the other hand, if the counterfeiter succeeds, it must map
|Ai to some state | fA i := |Ai |Ai |garbageA i, and |Bi to some state | fB i := |Bi |Bi |garbageB i. Therefore
|h fA | fB i| ≤ 1/4. So setting c = 1/2 and d = 1/4, Theorem 4.2 tells us that the counterfeiter must make
c−d
Ω √ = Ω 2n/4
ε
queries to UA∗ .
A simple modification to the proof of Theorem 5.2 shows that even to counterfeit money almost
perfectly, one still needs exponentially many queries to UA∗ .
Corollary 5.3 (Lower Bound for Small-Error Counterfeiting). Given one copy of |Ai, as well as oracle
access to UA∗ , a counterfeiter needs Ω(2n/4 ) queries to prepare a state ρ such that hA|⊗2 ρ |Ai⊗2 ≥ 0.9999
(for a worst-case |Ai).
Proof. Let |hA|Bi| = c, and let ε = 0.0001. If the counterfeiter succeeds, it must map |Ai to some state
ρA , and |Bi to some state ρB , such that hA|⊗2 ρA |Ai⊗2 and hB|⊗2 ρB |Bi⊗2 are both at least 1 − ε. So
letting | fA i and | fB i be purifications of ρA and ρB respectively, we have
|h fA | fB i| ≤ F (ρA , ρB )
≤ hA|⊗2 |Bi⊗2 + 2ε 1/4
= c2 + 2ε 1/4
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 380
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
where the second line follows from Lemma 2.5. So setting d := c2 + 2ε 1/4 , Theorem 4.2 tells us that the
counterfeiter must make !
c − c2 − 2ε 1/4
Ω √
2−n/2
queries to UA∗ . Fixing c := 1/2, the above is Ω 2n/4 .
Since the verifier VA is projective, we can now combine Corollary 5.3 with Theorem 3.5 to obtain the
following “amplified” lower bound.
Corollary 5.4 (Lower Bound for High-Error Counterfeiting). Let 1/ε = o 2n/2 . Given one copy of |Ai,
√
as well as oracle access to UA∗ , a counterfeiter needs Ω ε2n/4 queries to prepare a state ρ such that
hA|⊗2 ρ |Ai⊗2 ≥ ε (for a worst-case |Ai).
√
Proof. Suppose we have a counterfeiter C that makes o ε2n/4 queries to UA∗ , and prepares a state
σ such that hA|⊗2 σ |Ai⊗2 ≥ ε. Let δ := 0.00001. Then by Theorem 3.5, there exists an amplified
counterfeiter C0 that makes !
log 1/δ 1
O √ √ =O √
ε ε +δ2 ε
calls C and VA , and that prepares a state ρ such that hA|⊗2 ρ |Ai⊗2 ≥ 1 − δ . Now, counting the
√ ton/4
o ε2 queries from each C invocation and O (1) queries from each VA invocation, the total number
of queries that C0 makes to UA∗ is
h √ i 1
n/4
o ε2 + O (1) · O √ = o 2n/4 .
ε
But this contradicts Corollary 5.3.
So far, we have only made statements about the worst case for a would-be counterfeiter. But such
guarantees are clearly not enough: it could be that most money states |Ai are easy to duplicate, without
contradicting any of the results we have seen so far.
We will show that the problem faced by a counterfeiter is random self-reducible: if a counterfeiter
could duplicate a uniformly-random money state |Ai, then it could duplicate any |Ai. Thus the bank can
ensure security by creating uniformly-random money states.
In what follows, let S be the set of all subspaces A ≤ Fn2 such that dim A = n/2. Also, let VA⊗2 =
(|Ai hA|)⊗2 be the projector onto |Ai⊗2 .
Theorem 5.5 (Lower Bound for Average-Case Counterfeiting). Let A ≤ Fn2 be a uniformly-random
element
√ n/4of S. Then given one copy of |Ai, as well as oracle access to UA∗ , a counterfeiter C needs
Ω ε2 queries to prepare a 2n-qubit state ρ that VA⊗2 accepts with probability at least ε, for all
1/ε = o 2n/2 . Here the probability is taken over the choice of A ∈ S, as well as the behavior of C and
VA⊗2 .
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 381
S COTT A ARONSON AND PAUL C HRISTIANO
Proof. Suppose we had a counterfeiter C that violated the above. Using C as a black box, we will show
how to construct a new counterfeiter C0 that violates Corollary 5.4.
Given a (deterministically-chosen) money state |Ai and oracle access to UA∗ , first choose an invertible
linear map f : Fn2 → Fn2 uniformly at random. Then f (A), the image of A under f , is a uniformly-random
element of S. Furthermore, the state |Ai can be transformed into | f (A)i straightforwardly, the oracle
U f (A) can be simulated by composing f with UA , and the oracle U f (A)⊥ can likewise be simulated by
composing f −T with UA (where f −T denotes the inverse transpose of f ). So by using the counterfeiter C
for uniformly-random states, we can produce a state ρ f that V f⊗2
(A) accepts with probability at least ε. By
applying f −1 to both registers of ρ f , we can then obtain a state ρ that VA⊗2 accepts with probability at
least ε, thereby contradicting Corollary 5.4.
We are now ready to prove security for the “final” mini-scheme M defined in Section 5.2.
Theorem 5.6 (Security of Mini-Scheme). The mini-scheme M = (BankM , VerM ), which is defined
relative to the classical oracle U, has perfect completeness and 1/ exp (n) soundness error.
Proof. That M has perfect completeness follows from its definition and from Lemma 5.1. That M has
1/ exp (n) soundness error essentially follows from Theorem 5.5. We only need to show that, given a
banknote of the form |$r i = |sr i |Ar i, a polynomial-time counterfeiter C can gain no additional advantage
by querying the “full” oracles G, H, Tprimal , Tdual , beyond what it gains from querying UA∗r = (UAr ,UA⊥r ).
Let r ∈ {0, 1}n be the random string chosen by the bank, so that G (r) = (sr , hAr i). Then observe
that, even conditioned on sr and Ar , as well as complete descriptions of Tprimal , Tdual , and H, the string
r remains uniformly random. Nor can querying G (r0 ) for r0 6= r reveal any information about r, since
the values of G are generated independently. So suppose we modify G by setting G (r) := (s0 , hA0 i), for
some new 3n-bit serial number s0 and list of generators hA0 i chosen uniformly at random. Then the
BBBV hybrid argument [13] tells us that, in expectation over r, this can alter the final state output by
the counterfeiter C (|$r i) by at most poly (n) /2n/2 in trace distance. So in particular, if C succeeded with
non-negligible probability before, then C must still succeed with non-negligible probability after we set
G (r) := (s0 , hA0 i).
However, once we make this modification, an adversary trying to counterfeit |Ai given UA and UA⊥
can easily “mock up” a serial number s, as well as the oraclesG, H, Tprimal and Tdual , for itself. For s, G,
and H are now drawn from a distribution completely independent of A. The oracles Tprimal and Tdual are
likewise independent of A, except that Tprimal |si |vi = |siUA |vi and Tdual |si |vi = |siUA⊥ |vi—behaviors
that an adversary can easily simulate using UA and UA⊥ , together with its knowledge of s. Just like in
Corollary 3.8, since our security guarantees are query complexity bounds, we do not care about the
computational complexity of creating the mock-ups.
By using the mock-ups, one can convert any successful attack on M into successful counterfeiting of
|Ai, given oracle access to UA and UA⊥ only. But the latter contradicts Theorem 5.5.
Finally, using Theorem 5.6 together with Corollary 3.8, we can obtain a secure public-key quantum
money scheme, relative to a classical oracle.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 382
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Theorem 5.7 (Security of Hidden Subspace Money). By combining the mini-scheme M with a digital
signature scheme, it is possible to construct a public-key quantum money scheme
S = (KeyGenS , BankS , VerS ) ,
defined relative to some classical oracle U 0 , which has perfect completeness and 1/ exp(n) soundness
error.
6 Explicit quantum money scheme
We have shown how to construct a provably-secure public-key quantum money scheme, when an
appropriate classical oracle is available. In this section, we propose a way to obtain the same functionality
without an oracle. The key challenge is this:
Given a subspace A ≤ Fn2 , how can a bank distribute an “obfuscated program” PA , which
legitimate buyers and sellers can use to decide membership in both A and A⊥ , but which
does not reveal anything else about A that might facilitate counterfeiting?
Note that, aside from the detail that we need security against quantum adversaries, the above challenge
is purely “classical”; it and its variants seem interesting even apart from our quantum money application.
We will suggest a candidate protocol to achieve the challenge, based on multivariate polynomial
cryptography. Given a collection p1 , . . . , pm : Fn2 → F2 of multivariate polynomials over F2 , it is generally
hard to find a point v ∈ Fn2 on which all of vanish. On the other hand, it is easy to check whether a
particular point v has that property. To “hide” a subspace A, we will provide uniformly-random low-
degree polynomials p1 , . . . , pm that vanish on each point of A. This information is sufficient to decide
membership in A. On the other hand, there is no known efficient algorithm to find A given the polynomials,
and current techniques seem unlikely to yield even a quantum algorithm.
We can also introduce a constant fraction of noise into our scheme without interfering with its
completeness. In other words, if only (1 − ε) m of the polynomials p1 , . . . , pm are chosen to vanish on A,
and the remaining εm are random, then counting the pi that vanish at a point v still suffices to determine
whether v ∈ A. Although we know of no attack even against our noise-free scheme, adding noise in this
way might improve security.
Crucially, we will state a “classical” conjecture about the security of multivariate polynomial cryptog-
raphy, and show that the conjecture implies the security of our explicit money scheme. For the benefit of
cryptographers, let us now state an “abstract” version of our conjecture, which implies what we need, and
which might hold even if our concrete conjecture about multivariate polynomials fails.
Conjecture 6.1 (Subspace-Hiding Conjecture, Sufficient for Quantum Money). There exists a polynomial-
time algorithm that takes as input a description of a uniformly-random subspace A ≤ Fn2 with dim (A) =
n/2, and that outputs circuits CA and CA⊥ , such that the following holds.
(i) CA (v) decides whether v ∈ A, and CA⊥ (v) decides whether v ∈ A⊥ , for all v ∈ Fn2 .
(ii) Given descriptions of CA and CA⊥ , no polynomial-time quantum algorithm can find a generating
set for A with success probability Ω 2−n/2 .
Later, Conjecture 6.7 will specialize Conjecture 6.1 to the setting of multivariate polynomials.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 383
S COTT A ARONSON AND PAUL C HRISTIANO
6.1 Useful facts about polynomials
By viewing elements of Fn2 as n-tuples (x1 , . . . , xn ), we can evaluate a polynomial p (x1 , . . . , xn ) on points
of Fn2 .
Given a subspace A ≤ Fn2 and a positive integer d, let Id,A be the set of degree-d polynomials (not
necessarily homogeneous) that vanish on A. Since we are working over F2 , note that xi2 = xi , so it suffices
to consider multilinear polynomials (in which no xi is ever raised to a higher power than 1).
Before presenting our scheme, we need to establish some basic properties of polynomials over Fn2 .
First, we observe that the set of polynomials does not depend on the choice of basis.
Proposition 6.2. Let L be any invertible linear transformation on Fn2 . Then the map p (v) 7→ p (Lv)
defines a permutation on the set of degree-d polynomials, which maps Id,A to Id,L−1 A .
Implementing our scheme will require sampling uniformly from Id,A , which the next lemma shows is
possible.
Lemma 6.3. It is possible to sample a uniformly-random element of Id,A in time O(nd ).
Proof. By Proposition 6.2, we can instead sample from the space of polynomials which vanish on
span x1 , . . . , xn/2 , and then apply an appropriate change of basis to obtain a sample from Id,A . So assume
without loss of generality that A = span(x1 , . . . , xn/2 ).
We claim that a polynomial p vanishes on A if and only if every monomial of p intersects the set
d
{xn/2+1 , . . . , xn }. This will immediately give an O n -time sampling algorithm, because we can consider
each of the O nd degree-d monomials in turn, and include each one independently with probability 1/2
if it intersects {xn/2+1 , . . . , xn }.
To prove the claim: first, if every monomial intersects {xn/2+1 , . . . , xn }, then clearly p vanishes on
A. Otherwise, let m be a minimal monomial that does not intersect {xn/2+1 , . . . , xn }. Consider the vector
v = (v1 , . . . , vn ) with vi = 1 if and only if xi ∈ m. Since m does not intersect {xn/2+1 , . . . , xn }, clearly v ∈ A.
Also, since m is minimal, every other monomial must evaluate to 0 on v. Thus p(v) = m(v) = 1, so p is
not identically zero on A.
In addition to sampling polynomials that vanish on A, we would like to guarantee that a sufficiently
large system of such polynomials uniquely determines the space A, so that such a system can be effectively
used as a membership oracle.
Lemma 6.4. Fix A ≤ Fn2 and β > 1, and choose β n polynomials p1 , . . . , pβ n uniformly and independently
from Id,A . Let Z be the set of v ∈ Fn2 such that pi (v) = 0 for all i ∈ [β n]. Then A ⊆ Z, and Pr [Z = A] =
1 − 2−Ω(n) .
Proof. A ⊆ Z is clear. For the probabilistic part, fix a point v ∈/ A. Then by the union bound, it suffices to
show that Pr [v ∈ Z] < c−n for some c > 2.
There must be some w ∈ A⊥ such that w · v = 1. Then the map p (v) 7→ p (v) + w · v defines an
involution of Id,A , such that exactly one of p (v) and p (v) + w · v is zero. This means that exactly half of
the polynomials in Id,A vanish at v. Hence
Pr p1 (v) = · · · = pβ n (v) = 0 = 2−β n
and we are done.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 384
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
As mentioned earlier, we would also like to allow sampling from noisy systems of equations, defined
as follows: let Rd,A,m,ε be the probability distribution over m-tuples (p1 , . . . , pm ) that sets exactly (1 − ε) m
of the polynomials pi (chosen uniformly at random) to be uniformly-random samples from Id,A , and
that sets the remaining εm of the polynomials pi to be uniformly-random samples from Id,A0 , for a
uniformly-random subspace A0 ≤ Fn2 of dimension dim (A). (Note that a different A0 is chosen for every
such pi .) Then using a Chernoff bound, it is not hard to show that, provided m is large enough compared
to n, a sample from Rd,A,m,ε also uniquely defines the subspace A with overwhelming probability.
Lemma 6.5. Fix A ≤ Fn2 and ε < 1/2, let β ≥ 3/(1 − 2ε)2 , and choose polynomials p1 , . . . , pβ n from
βn
Rd,A,β n,ε . Let w (v) := ∑i=1 pi (v), and let Z be the set of v ∈ Fn2 such that w (v) ≤ εβ n. Then A ⊆ Z, and
Pr [Z = A] = 1 − 2−Ω(n) .
Proof. Again, A ⊆ Z is clear. For the probabilistic part, fix v ∈
/ A. Then by the union bound, it suffices to
show that Pr [v ∈ Z] < α −n for some α < 1/2.
Observe that v is a zero of little more than half the polynomials p1 , . . . , pβ n . If pi was chosen to
vanish on A, then E [pi (v)] = 1/2, by the argument of Lemma 6.4. If pi was chosen to vanish on a
uniformly-random A0 , then
1
− Pr v ∈ A0
E [pi (v)] ≥
2
1 1
= − n/2 .
2 2
Hence
1 1
E p1 (v) + · · · + pβ n (v) ≥ β n − .
2 2n/2
Furthermore, the pi are chosen independently, up to an irrelevant ordering. Choose δ = 1 − 2ε to satisfy
(1 − δ )/2 = ε. Then by a Chernoff bound,
Pr [v ∈ Z] = Pr p1 (v) + · · · + pβ n (v) ≤ εβ n
1 βn 2
≤ exp − 1 − n/2 δ 2
2 2 2
3n 2
≤ exp − 1 − n/2
4 2
n
< 0.48
for large enough n, and we are done.
6.2 Explicit hidden-subspace mini-scheme
In our explicit mini-scheme, the bank chooses a subspace A randomly and publishes sets of polynomials
drawn from Rd,A,β n,ε and Rd,A⊥ ,β n,ε , along with the quantum money state |Ai. By Lemma 6.5, a user
can use these polynomials to test membership in A and A⊥ , and can therefore implement the oracle
mini-scheme in Section 5.1.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 385
S COTT A ARONSON AND PAUL C HRISTIANO
Formally, the mini-scheme E is defined as follows. Parameters ε ∈ [0, 1/2), β ≥ 3/(1 2
− 2ε) , and
d ≥ 4 are fixed. The complexity of the verification procedure will grow like O β n d+1 , but security
might also improve for larger ε and d. Then:
• Bank (0n ) selects an n/2-dimensional subspace A ≤ Fn2 uniformly at random, say by selecting n/2
random linearly-independent generators. It then sets s := (sA , sA⊥ ), where sA and sA⊥ are lists of
polynomials drawn from Rd,A,β n,ε and Rd,A⊥ ,β n,ε respectively. It prepares the money state |Ai and
outputs the banknote |$s i := |si |Ai.
• Ver (/c) first checks that /c has the form (sA , sA⊥ , ρ) where sA = p1 , . . . , pβ n and sA⊥ = q1 , . . . , qβ n
are lists of β n polynomials over Fn2 . If not, it rejects. If so, then it defines Z and Z ⊥ to be the sets
of points v ∈ Fn2 such that
βn βn
∑ pi (v) ≤ εβ n and ∑ qi (v) ≤ εβ n
i=1 i=1
respectively. (Recall that with overwhelming probability, Z = A and Z ⊥ = A⊥ . Also, while Ver will
not have explicit listings of the exponentially-large sets Z and Z ⊥ , all that matters for us is that it can
efficiently apply the projections PZ and PZ ⊥ .) It then applies the operation VZ := H2⊗n PZ ⊥ H2⊗n PZ
to ρ, and accepts /c if and only if VZ (ρ) accepts.
6.3 Analysis
We first observe that the mini-scheme E has perfect completeness.
Theorem 6.6. E has perfect completeness.
Proof. This follows from Lemmas 6.4 and 6.5, and particularly from the fact that A ⊆ Z and A⊥ ⊆ Z ⊥
with certainty. From this it follows that VZ := H2⊗n PZ ⊥ H2⊗n PZ accepts the state |Ai with probability 1.
Let us remark that, if we want the fraction ε of “decoy” polynomials to be even greater than 1/2, then
we can define a variant of our scheme that works for all ε < 1. In this variant scheme, Ver will guess that
v ∈ A (i.e., put v ∈ Z) if
(1 + ε) β n
p1 (v) + · · · + pβ n (v) ≤ ,
4
and will guess that v ∈/ A (i.e., put v ∈
/ Z) otherwise. By direct analogy with Lemma 6.5, one ⊥can prove
−Ω(n) , and likewise Pr Z = A⊥ =
using a Chernoff bound that this rule will guarantee Pr [Z = A] = 1 − 2
1 − 2−Ω(n) , provided we set β ≥ 12/(1 − ε)2 . However, the disadvantage is that if ε ≥ 1/3, then we lose
the property that A ⊆ Z and A⊥ ⊆ Z ⊥ with probability 1, since ε ≥ (1 + ε)/4. This means, in particular,
that we lose perfect completeness, and can only ensure a completeness error of 2−Ω(n) .
We now wish to argue about E’s soundness. Naturally, we can only hope to prove soundness assuming
some computational hardness conjecture. What is nice, though, is that we can base E’s soundness on a
conjecture that talks only about the hardness of a “classical” cryptographic problem (i.e., a problem with
classical inputs and outputs). Let us now state that conjecture, which is simply the abstract Conjecture 6.1
specialized to the setting of multivariate polynomials.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 386
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Conjecture 6.7 (Direct Product for Finding Subspace Elements). Let ε < 1/2 and β := 3/(1 − 2ε)2 .
Given samples from Rd,A,β n,ε and Rd,A⊥ ,β n,ε , no polynomial-time quantum algorithm can find a complete
list of generators for A with success probability Ω(2−n/2 ).
Note that it is easy to find one nonzero element of A with success probability 2−n/2 , by choosing
x ∈ Fn2 randomly. Conjecture 6.7 asserts both that it is impossible to do too much better using Rd,A,β n,ε
and Rd,A⊥ ,β n,ε , and that finding multiple elements of A is significantly harder than finding one element.
The security of mini-scheme E follows easily from Conjecture 6.7, despite the fact that a would-
be counterfeiter has access to a valid quantum banknote, whereas Conjecture 6.7 involves no such
assumption.
Theorem 6.8 (Security Reduction for Explicit Mini-Scheme). If Conjecture 6.7 holds, then E is secure.
Proof. Let CE be a counterfeiter against E. Then we need to show that, using CE , we can find a complete
list of generators for A with Ω 2−n/2 success probability.
Given A ≤ Fn2 with dim (A) = n/2, let s := (sA , sA⊥ ) where sA and sA⊥ are samples from Rd,A,β n,ε
and Rd,A⊥ ,β n,ε respectively. Recall from Lemma 6.5 that Pr [A = Z] = 1 − 2−Ω(n) and Pr A⊥ = Z ⊥ =
1 − 2−Ω(n) . Provided both of these events occur, we can use s to decide membership in A, and can
therefore apply the projective measurement PA . So let us prepare the uniform superposition over all 2n
elements of Fn2 , and then apply PA to it. With probability 2−n/2 , this produces the state |Ai.
Once we have s and |Ai, we can then form the banknote |$i := |si |Ai, and provide this banknote to
the counterfeiter CE . By hypothesis, CE outputs a (possibly-entangled) state ρ on two registers, such
that hA|⊗2 ρ |Ai⊗2 ≥ ∆ for some ∆ = Ω (1/ poly (n)). But now, because the mini-scheme E is projective,
Theorem 3.5 applies, and we can amplify ρ to increase its fidelity with |Ai⊗2 . After O(log(n)/∆2 ) calls
to CE , this gives us a state σ such that
1
hA|⊗2 σ |Ai⊗2 ≥ 1 − .
n2
More generally, by alternating counterfeiting steps and amplification steps, we can produce as many
registers as we like that each have large overlap with |Ai. In particular, we can produce a state ξ such that
hA|⊗n ξ |Ai⊗n ≥ 1 − o (1) .
If we now run Ver on each of the registers of ξ , the probability that every invocation accepts is 1 − o (1).
Furthermore, supposing that happens, the state we are left with is simply |Ai⊗n .
Finally, we measure each register of |Ai⊗n in the standard basis. This gives us n elements x1 , . . . , xn ∈ A,
which are independent and uniformly random. So by standard estimates, the probability that x1 , . . . , xn do
not contain a complete generating set for A is 1/ exp (n).
Overall, the procedure above succeeded with probability 2−n/2 (1 − o (1)), thereby giving us the
desired contradiction with Conjecture 6.7.
Using the standard construction of quantum money schemes, we can now produce a complete explicit
money scheme, whose security follows from Conjecture 6.7.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 387
S COTT A ARONSON AND PAUL C HRISTIANO
Theorem 6.9 (Security Reduction for Explicit Scheme). Assuming Conjecture 6.7, there exists a public-
key quantum money scheme with perfect completeness and soundness error 2−Ω(n) .
Proof. We apply the standard construction of Theorem 3.6 with the mini-scheme E, whose completeness
and soundness follow from Theorems 6.6 and 6.8 respectively, assuming Conjecture 6.7.
6.4 Justifying our hardness assumption
Though our hardness assumption is new, it is closely related to standard assumptions in multivariate
polynomial cryptography. Given a system of multivariate quadratics over F2 , finding a common zero is
known to be NP-hard; moreover, it is strongly believed that the problem remains hard even for random
systems of multivariate polynomials, and cryptosystems based on this hardness assumption are considered
promising candidates for post-quantum cryptography [22]. Therefore, if Conjecture 6.7 fails, it will
almost certainly be because some additional structure in this problem facilitates a new attack.
There are several ways in which Conjecture 6.7 is stronger than the assumption that solving random
systems of multivariate polynomials is hard. First, our systems have large, well-structured solution spaces
A and A⊥ . Systems with many solutions are not normally considered in the literature, and while there
seem to be no known attacks that exploit this structure, the possibility is not ruled out. Second, we
provide two related systems, one with zeroes in A and one with zeroes in A⊥ . Again, this is a very specific
structural property which has not been considered, and there might be unexpected attacks exploiting
it. Third, Conjecture 6.7 asserts that no adversary can succeed with probability 2−n/2 , which seems
significantly easier than succeeding with non-negligible probability.
On the other hand, Conjecture 6.7 is weaker than typical assumptions in multivariate polynomial
cryptography in at least one respect: a would-be counterfeiter needs to solve a system of polynomial
equations with a constant fraction of noise. Solving noisy systems of linear equations over F2 is called the
learning parity with noise problem, and is generally believed to be hard even for quantum computers [39].
If true, this suggests that Gaussian elimination is fundamentally hard to adapt to the presence of noise.
But computing a Gröbner basis is a strict generalization of Gaussian elimination to higher degree, and
involves a nearly identical process of elimination. It therefore seems unlikely that these approaches can
be efficiently adapted to the setting with noise. The problem of solving polynomials with noise has
been studied recently, and the best-known approaches involve performing an exponential time search to
determine which equations are noisy [7].
But if solving linear systems with noise is already hard, why do we even use higher-degree polynomials
in our scheme? The reason is that, alas, the “dual” structure of our money scheme facilitates a simple
attack in the case d = 1.
Claim 6.10. For all ε < 1/2, there exists a β such that one can recover A efficiently given samples from
Rd,A,β n,ε and Rd,A⊥ ,β n,ε .19
Proof. Let p1 , . . . , pm and q1 , . . . , qm be homogeneous linear polynomials, of which a 1 − ε fraction
vanish on A and A⊥ respectively. Then the key observation is that each pi vanishes on A if and only if
it has the form pi (v) = ui · v for some ui ∈ A⊥ , while each qi vanishes on A⊥ if and only if it has the
19 This claim also goes through, with no essential changes, for the variant of our scheme discussed earlier with ε ∈ [1/2, 1)
(i.e., the variant without perfect completeness).
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 388
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
form qi (v) = wi · v for some wi ∈ A. But by Lemma 6.5, if β > 3/(1 − 2ε)2 , then for each i ∈ [m], we
can efficiently decide whether ui ∈ A⊥ by counting those values j for which q j (ui ) = 0, and can likewise
decide whether wi ∈ A by counting those values j for which p j (wi ) = 0. Thus we can learn Θ (n) random
elements of A or A⊥ , and thereby recover a basis for A.
There might be a more sophisticated attack for higher degrees, but this is suggested only weakly
by the existence of an attack in the linear case. Indeed, the relation between the complementary linear
subspaces A and A⊥ is precisely the sort of structure that should be preserved by linear maps, but not by
higher-degree polynomials!
For degree-2 polynomials, it is possible to obtain a similar attack which recovers A from only a single
sample. This attack relies on the observation that quadratics have an easily-computed canonical form [18],
from which a basis for A can be extracted in polynomial time. The essential problem is that quadratic
polynomials are very closely related to bilinear forms, and that powerful methods from linear algebra can
therefore be applied to them.
Fortunately, the linear structure seems to be computationally obscured when d ≥ 3. This phenomenon
is related to the sharp discontinuity in the difficulty of tensor problems with order 3 and higher. More
concretely, the coefficients of a degree-d polynomial can be viewed as the entries of an order-d tensor, and
the existence of an attack in the degree d = 2 case corresponds to the possibility of efficient operations on
order-2 tensors. Basic operations on order-3 tensors are NP-hard [28], however, and this suggests that
analogous attacks might not exist against degree-3 polynomials.
This state of affairs is reflected in existing attacks on a standard cryptographic assumption called
polynomial isomorphism with one secret. Here we are given two polynomials p, q which are related by an
unknown linear change of coordinates L, and the task is to find such an L. For degree-2 polynomials,
this problem can be easily solved in polynomial time [18], but already for degree-3 polynomials the
best known attacks take exponential time [38, 26, 18]. However, if an attacker is given n bits of partial
information about the linear transformation, then even in the d = 3 case, it becomes possible to find
the linear transformation that relates the polynomials [18]. This does not directly facilitate an attack on
our assumption, but it suggests that a similar attack might be possible when d = 3, since an attacker is
only required to succeed with 2−n/2 probability. Fortunately, this attack seems to rely on the particular
structure of degree 2 and 3 polynomials. Of course it is possible that similar algorithms may be discovered
for higher-degree polynomials, but this would represent an advance in algebraic cryptanalysis.
7 Private-key quantum money
Recall that a private-key quantum money scheme is one where only the bank itself is able to verify
banknotes, using an n-bit key k = kprivate = kpublic that it keeps a closely-guarded secret. Compensating
for this disadvantage, private-key schemes are known with much stronger security guarantees than seem
possible for public-key schemes.
In particular, as mentioned in Section 1.1, already forty years ago Wiesner [42] described how to
create private-key quantum money that is information-theoretically secure. In Wiesner’s scheme, each
banknote consists of n unentangled qubits together with a classical serial number s. Wiesner’s scheme also
requires a giant database of serial numbers maintained by the bank, or in our setting, access to a random
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 389
S COTT A ARONSON AND PAUL C HRISTIANO
oracle R. But in followup work, BBBW [15] pointed out that we can replace R by any pseudorandom
function family { fk }k , to obtain a private-key quantum money scheme that is computationally secure,
unless a polynomial-time algorithm can distinguish the fk from random functions.
Strangely, we are unaware of any rigorous proof of the security of Wiesner’s scheme until recently.
However, answering a question by one of us,20 Molina, Vidick and Watrous [33] have now supplied the
key ingredient for a security proof. Specifically they show that, if a counterfeiter tries to copy an n-qubit
banknote |$i in Wiesner’s scheme, then the output can have squared fidelity at most (3/4)n with |$i⊗2 .
(They also show that this is tight: there exists a non-obvious counterfeiting strategy that succeeds with
(3/4)n probability.)
To complete the security proof, one needs to show that, even given q banknotes |$1 i , . . . , $q , a
counterfeiter cannot prepare an additional banknote with non-negligible probability (even with a new
serial number). In a forthcoming paper [4], we will show how to adapt the methods of Section 3 to
prove that claim. Briefly, one can first define a notion of private-key mini-schemes, in close analogy to
public-key mini-schemes. The work of Molina et al. [33] then directly implies the security of what we
call the “Wiesner mini-scheme.” Next, one can give a general reduction, showing how to construct a
full-blown private-key quantum money scheme S starting from
(1) any private-key mini-scheme M, and
(2) any random or pseudorandom function family R.
Though the details turn out to be more complicated in the private-key case, the proof of correctness
for this reduction is conceptually similar to the proof of Theorem 3.6. Namely, one shows that any
counterfeiter would yield either a break of the underlying mini-scheme M, or else a way to distinguish R
from a random function. Notice that the analysis is completely unified: if R is a “true” random oracle,
then we get information-theoretic security (as in Wiesner’s scheme), while if R is pseudorandom, then we
get computational security (as in the BBBW scheme).
Unfortunately, as pointed out by Lutomirski [30] and Aaronson [3], the Wiesner and BBBW schemes
both have a serious security hole. Namely, suppose a counterfeiter C can repeatedly submit alleged
banknotes to a “naïve and trusting bank” for verification. Given a quantum state σ , such a bank not
only tells C whether the verification procedure accepted or rejected, but also, in either case, gives the
post-measurement state σe back to C. Then starting from a single valid banknote |$i, we claim that C can
recover a complete classical description of |$i, using O (n log n) queries to the bank. Once it has such a
description, C can of course prepare as many copies of |$i as it likes.
The attack is simple: let |$i = |θ1 i · · · |θn i (we omit the classical serial number s, since it plays no
role here). Then for each i ∈ [n], the counterfeiter tries “swapping out” the ith qubit |θi i and replacing
it with |bi, for each of the four possibilities |bi ∈ {|0i , |1i , |+i , |−i}. It then uses O (log n) queries to
the bank, to estimate the probability that the state |θ1 i · · · |θi−1 i |bi |θi+1 i · · · |θn i passes the verification
test. By doing so, C can learn a correct value of |θi i with success probability 1 − o (1/n). The crucial
point is that none of these queries damage the qubits not being investigated ( θ j for j 6= i), since the
bank measures those qubits in the correct bases. Therefore C can reuse the same banknote for each query.
20 See http://theoreticalphysics.stackexchange.com/questions/370/rigorous-security-proof-for-wiesners-quantum-money
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 390
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
More generally, recall from Section 3.1 that we call a private-key quantum money scheme query-
secure, if it remains secure even assuming the counterfeiter C can make adaptive queries to Ver (k, ·).
Then we saw that the Wiesner and BBBW schemes are not query-secure. Recently, Farhi et al. [23]
proved a much more general “no-go” theorem—which says intuitively that, if we want query-secure
quantum money, then the banknotes must hide information in the “global correlations” between large
numbers of qubits.
Theorem 7.1 (Adaptive Attack on Wiesner-Like Schemes [23]). No quantum money scheme can be
query-secure, if
(i) the banknotes have the form |$s i = |si |ψs i,
(ii) verification of (s, ρ) consists of projecting ρ onto |ψs i hψs |, and
(iii) |ψs i can be reconstructed uniquely from the statistics of T = poly (n) efficiently-implementable
measurements M1 , . . . , MT , each of which has at most poly (n) possible outcomes.
On the positive side, any public-key quantum money scheme—for example, our multivariate poly-
nomial scheme from Section 6—immediately yields a query-secure scheme with the same security
guarantee. This is because a counterfeiter who knows the code of Ver can easily simulate oracle access
to Ver. But can we do any better than that, and construct a query-secure money scheme whose security
is unconditional (as in Wiesner’s scheme), or else based on a pseudorandom function (as in the BBBW
scheme)?
In the forthcoming paper [4], we will answer this question in the affirmative, by directly adapting the
hidden subspace scheme from Section 5 (i.e., the scheme based on a classical oracle). Since the idea is an
extremely simple one, let us sketch it here.
Theorem 7.2 (Query-Secure Variant of Wiesner’s Scheme). Relative to a random oracle R,21 there exists
a private-key quantum money scheme, with perfect completeness and 2−Ω(n) soundness error, that is
information-theoretically query-secure. One can also replace the random oracle R by a pseudorandom
function family { fk }k , to obtain a private-key quantum money scheme, with no oracle, that is query-secure
assuming that the fk cannot be distinguished from random in quantum polynomial time.
Proof sketch. For each key k and a serial number s, we will think of the random oracle R as encod-
ing a classical description R (k, s) of a subspace Ak,s ≤ Fn2 , which is uniformly random subject to
dim (Ak,s ) = n/2. Let |Ak,s i be a uniform superposition over Ak,s . Then the private-key money scheme
S = (KeyGen, Bank, Ver) is defined as follows:
• KeyGen (0n ) generates an n-bit key k uniformly at random.
• Bank (k) outputs a banknote |$s i := |si |Ak,s i, for a random serial number s ∈ {0, 1}n .
• Ver (k, (s, ρ)) applies a projective measurement that accepts ρ with probability hAk,s |ρ|Ak,s i.
21 Or alternatively, assuming the bank has access to a giant random number table, as in Wiesner’s original setup [42].
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 391
S COTT A ARONSON AND PAUL C HRISTIANO
Now, suppose it were possible to break S (i.e., to counterfeit |Ak,s i), using poly (n) adaptive queries
to Ver (k, ·). Then we claim that it would also be possible to break our public-key scheme from Section 5,
and thereby contradict the unconditional security proof for the latter! The reason is simply that any query
to Ver, of the form Ver (k, (s, ρ)), can easily be simulated using queries to UAk,s and UA⊥ , the membership
k,s
oracles for Ak,s and A⊥
k,s respectively that are available to a counterfeiter against the public-key scheme.
Finally, suppose we replace R (k, s) by a pseudorandom function fk (s). Then just like with the original
BBBW scheme [15], we can argue as follows. Since we already showed that S is information-theoretically
secure when instantiated with a “true” random function, any break of S in the pseudorandom case would
thereby distinguish the function fk from random.
8 Open problems
The “obvious” problem is to better understand the security of our explicit scheme based on polynomials.
Are there nontrivial attacks, for example using Gröbner-basis algorithms? Can we base the security of our
scheme—or a related scheme—on some cryptographic assumption that does not involve exponentially-
small success probabilities? What happens as we change the field size or polynomial degree? Does
“hiding” a subspace A ≤ Fn2 in the way we suggest, as the set of common zeroes of multivariate polynomials
p1 , . . . , pm : Fn2 → F2 , have other cryptographic applications, for example to program obfuscation [11]?
Of course, there is also tremendous scope for inventing new schemes, which might be based on
different assumptions and have different strengths and weaknesses.
Let us move on to some general questions about public-key quantum money. First, is there an
unconditionally-secure public-key quantum money scheme relative to a random oracle R? (Recall that
Wiesner’s original scheme [42] was unconditionally-secure and used only a random oracle, but was
private-key. Meanwhile, our scheme from Section 5 is unconditionally-secure and public-key, but requires
a non-random oracle.) Second, is there a public-key quantum money scheme where the banknotes consist
of single, unentangled qubits, as in Wiesner’s scheme? Note that the results of Farhi et al. [23] imply that,
if such a scheme exists, then it cannot be projective. Third, is there a general way to amplify soundness
error in quantum money schemes?22 (We show how to amplify completeness error in Appendix A.)
8.1 Quantum copy-protection and more
Quantum money is just one novel cryptographic use for the No-Cloning Theorem. Given essentially
any object of cryptographic interest, one can ask whether quantum mechanics lets us make the object
uncloneable. Section 1.4 already discussed one example—uncloneable signatures—but there are many
others, such as commitments and proofs.23
Along those lines, Aaronson [3] proposed a task that, if achievable, would arguably be an even
more dramatic application of the No-Cloning Theorem than quantum money: namely, quantum software
copy-protection. He gave explicit schemes—which have not yet been broken—for copy-protecting a
22 Theorem 3.5 gives some soundness amplification for projective schemes: namely, from constant to 1/ poly (n). Here we
are asking whether one can do anything better.
23 Even within complexity theory, it would be interesting to study the class QMA (Quantum Merlin-Arthur) subject to the
constraint that witnesses must be hard to clone—or alternatively, that witnesses must be easy to clone!
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 392
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
restricted class of functions, namely the point functions. In these schemes, given a “password” s ∈ {0, 1}n ,
a software vendor can prepare a quantum state |ψs i, which allows its holder to recognize s: in other words,
to decide whether x = s given x ∈ {0, 1}n as input. On the other hand, given |ψs i, it seems intractable not
only to find s for oneself, but even to prepare a second quantum state with which s can be recognized.
Admittedly, recognizing passwords is an extremely restricted functionality. However, relative to a
quantum oracle, Aaronson [3] also described a scheme to quantumly copy-protect arbitrary programs,
just as well as if the software vendor were able to hand out uncloneable black boxes.24 In the spirit of
this paper, we can now ask: is there likewise a way to quantumly copy-protect arbitrary programs relative
to a classical oracle? We conjecture that the answer is yes, and in fact we have plausible candidate
constructions, which are directly related to the hidden-subspace money scheme of Section 5. However,
the security of those constructions seems to hinge on the following conjecture.
Conjecture 8.1 (Direct Product for Finding Black-Box Subspace Elements). Let A be a uniformly-
random subspace of Fn2 satisfying dim (A) = n/2. Then given membership oracles for both A and A⊥ ,
Ω(n) queries to find two distinct nonzero elements x, y ∈ A, with success
any quantum algorithm
−n/2
needs 2
probability Ω 2 .
Besides its applications for copy-protection, a proof of Conjecture 8.1 would be an important piece of
formal evidence for Conjecture 6.7, on which we based the security of our explicit money scheme.
Appendix A Reducing completeness error
When we defined quantum money schemes and mini-schemes in Section 3, we allowed the verifier
to reject a legitimate money state with probability up to 1/3. But of course, a money scheme with
completeness error ε = 1/3 is not very useful in practice! So in this appendix, we prove that the
completeness error ε can be made exponentially small in n, at the cost of only a modest increase in the
soundness error δ (i.e., the probability of successful counterfeiting).
Theorem A.1 (Completeness Amplification for Mini-Schemes). Let M = (Bank, Ver) be a quantum
money mini-scheme with completeness error ε < 1/2 and soundness error δ < 1 − 2ε. Then for all
polynomials p and all δ 0 > δ /(1 − 2ε), we can construct an amplified mini-scheme M0 = Bank0 , Ver0
with completeness error 1/2 p(n) and soundness error δ 0 .
Proof. Let k = poly (n) and η > 0 be parameters to be determined later. Our construction of M0 is the
“obvious” one based on repetition:
• Bank0 (0n ) outputs a composite banknote $0 := (s1 . . . sk , ρs1 . . . ρsk ), where (s1 , ρs1 ) , . . . , (sk , ρsk )
are banknotes output independently by Bank (0n ).
• Ver0 (/c) runs Ver (/c1 ) , . . . , Ver (/ck ), where /c1 , . . . , /ck are the (s, ρs ) pairs in the alleged composite
banknote /c, and accepts if and only if at least (1 − ε − η) k invocations accept.
24 As usual, full details have not yet appeared yet.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 393
S COTT A ARONSON AND PAUL C HRISTIANO
Note that Ver02 , the amplified double verifier, then takes as input a state of the form
(s1 . . . sk , σ1 . . . σk , ξ1 . . . ξk ) ,
and accepts if and only if Ver0 (s1 . . . sk , σ1 . . . σk ) and Ver0 (s1 . . . sk , ξ1 . . . ξk ) both accept. By choosing
k sufficiently large and applying a Chernoff bound, it is clear that we can make the completeness error
1/2 p(n) for any polynomial p.
Meanwhile, suppose M0 has soundness error δ 0 : in other words, there exists a counterfeiter C0 such
that Ver02 (s1 . . . sk ,C0 ($0 )) accepts with probability δ 0 , given a valid composite banknote $0 . Then to
prove the theorem, it suffices to construct a counterfeiter C for the original mini-scheme M, such that
Ver2 (s,C ($)) accepts with probability δ ≥ (1 − 2ε − η) δ 0 , given a valid banknote $ = (s, ρs ).
This C works as follows:
(1) By calling Bank0 (0n ), generate a new composite banknote $0 = ($1 , . . . , $k ).
(2) Let $0new be the result of starting with $0 , then swapping out $i for the banknote $ to be copied, for
some i ∈ [k] chosen uniformly at random.
(3) Let (s1 . . . sk , σ1 . . . σk , ξ1 . . . ξk ) := C0 ($0new ).
(4) Output (si , σi , ξi ).
By assumption,
Pr Ver02 (s1 . . . sk , σ1 . . . σk , ξ1 . . . ξk ) accepts ≥ δ 0 .
Now, suppose Ver02 does accept. Then by the definition of Ver02 , at least (1 − ε − η) k of
Ver (s1 , σ1 ) , . . . , Ver (sk , σk )
must have accepted, along with at least (1 − ε − η) k of
Ver (s1 , ξ1 ) , . . . , Ver (sk , ξk ) .
So there must be at least (1 − 2ε − 2η) k indices j ∈ [k] such that Ver (s j , σ j ) and Ver (s j , ξ j ) both
accepted. Therefore
Pr [Ver2 (si , σi , ξi ) accepts] = Pr [Ver (si , σi ) and Ver (si , ξi ) accept]
≥ (1 − 2ε − 2η) δ 0 .
Taking η > 0 sufficiently small now yields the theorem.
A direct counterpart of Theorem A.1, with exactly the same parameters, can be proved for public-
key quantum money schemes. Once again, the main idea is to consider “composite banknotes” $0 =
($1 , . . . , $k )—and this time, to associate with each $i a different, independently-chosen public/private
key pair. Another counterpart of Theorem A.1 can be proved for digital signature schemes, indeed with
slightly better parameters (δ 0 > δ /(1 − ε) instead of δ 0 > δ /(1 − 2ε)). We omit the details.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 394
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Appendix B Complexity-theoretic no-cloning theorem
In Section 5, we applied the inner-product adversary method to show that a uniform superposition |Ai over
a random subspace A ≤ Fn2 requires Ω(2n/4 ) quantum queries to duplicate, even if we are given access to
an oracle that decides membership in both A and A⊥ . For completeness, in this appendix we present a
simpler application of the inner-product adversary method: namely, we show that a Haar-random n-qubit
state |ψi requires Ω(2n/2 ) queries to duplicate, if we are given access to an oracle Uψ that accepts |ψi
and that rejects every state orthogonal to |ψi. The latter is the original result that Aaronson [3] called the
“Complexity-Theoretic No-Cloning Theorem,” though a proof has not appeared until now.
In Section 5, we used the lower bound for copying subspace states to construct a quantum money
mini-scheme that was provably secure relative to a classical oracle. In the same way, one can use the
Complexity-Theoretic No-Cloning Theorem to construct a mini-scheme that is provably secure relative
to a quantum oracle. We omit the details of that construction, not only because it is superseded by the
classical oracle construction in Section 5, but because the two constructions are essentially the same.
The one real difference is that the quantum oracle construction benefits from a quadratically better lower
bound on the number of queries needed to counterfeit: Ω(2n/2 ) rather than Ω(2n/4 ).
Choose an n-qubit pure state |ψi uniformly from the Haar measure, and fix |ψi in what follows. Let
Uψ be a unitary transformation such that Uψ |ψi = − |ψi and Uψ |ηi = |ηi for all |ηi orthogonal to |ψi.
The following is the direct analogue of Theorem 5.2.
Theorem B.1 (Complexity-Theoretic No-Cloning). Given one copy of |ψi, as well as oracle access to
Uψ , a counterfeiter needs Ω(2n/2 ) queries to prepare |ψi⊗2 with certainty (for a worst-case |ψi).
Proof. We will apply Theorem 4.2. Let the set O contain Uψ for every possible n-qubit
state |ψi. Then
SUψ is just the 1-dimensional subspace corresponding to |ψi. Also, put Uψ ,Uϕ ∈ R if and only if
|hψ|ϕi| = c, for some 0 < c < 1 to be specified later. Then for all Uψ ∈ O and |ηi ∈ SU⊥ψ , we have
h i h i
2 2
E |hη|ϕi| = E |hη|ϕi|
Uϕ : (Uψ ,Uϕ )∈R |ϕi : |hψ|ϕi|=c
p 2
= E 2
hη| c |ψi + 1 − c |vi
|vi∈SU⊥ψ
h i
= 1 − c2 |hη|vi|2
E
|vi∈SU⊥ψ
1 − c2
= .
2n − 1
So set ε := (1 − c2 )/(2n − 1). If the counterfeiter succeeds, it must map
E
|ψi to some state fψ := |ψi |ψi garbageψ ,
and E
|ϕi to some state fϕ := |ϕi |ϕi garbageϕ .
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 395
S COTT A ARONSON AND PAUL C HRISTIANO
Note that | fψ | fϕ | ≤ c2 . So setting d := c2 , Theorem 4.2 tells us that the counterfeiter must make
r !
2
2n − 1
Ω c−c
1 − c2
queries to Uψ . Fixing (say) c = 1/2, this is Ω 2n/2 .
Like Theorem 5.2, Theorem B.1 is easily seen to be tight, since one can use the
amplitude amplification
⊗2 n/2
algorithm (Lemma 2.7) to find |ψi, and thereby prepare |ψi , using O 2 queries to Uψ .
For completeness, we observe the following generalization of Theorem B.1.
√
Theorem B.2. Given k copies of |ψi, as well as oracle access to Uψ , a counterfeiter needs Ω(2n/2 / k)
queries to prepare |ψi⊗k+1 with certainty (for a worst-case |ψi).
Proof. If the counterfeiter succeeds, it must map
E
|ψi⊗k to some state fψ := |ψi⊗k+1 garbageψ ,
and E
|ϕi⊗k to some state fϕ := |ϕi⊗k+1 garbageϕ .
Note that fψ | fϕ ≤ ck+1 . So setting d := ck+1 , Theorem 4.2 tells us that the counterfeiter must make
!
r 2n − 1
k k+1
Ω c −c
1 − c2
√
queries to Uψ . Fixing c := 1 − 1/k, the above is Ω(2n/2 / k).
We end this appendix by stating, without proof, three stronger lower bounds that are the direct
analogues of Corollary 5.3, Corollary 5.4, and Theorem 5.5 respectively.
Corollary B.3. Given one copy of |ψi, as well as oracle access to Uψ , a counterfeiter needs Ω 2n/2
queries to prepare a state ρ such that hψ|⊗2 ρ |ψi⊗2 ≥ 0.9999 (for a worst-case |ψi).
Corollary B.4. Let 1/ε = o (2n ). Given one copy of |ψi, as well as oracle access to Uψ , a counterfeiter
√
needs Ω ε2n/2 queries to prepare a state ρ such that hψ|⊗2 ρ |ψi⊗2 ≥ ε (for a worst-case |ψi).
Theorem B.5. Let |ψi be an n-qubit pure state chosen uniformly from the √ Haar measure. Given one
copy of |ψi, as well as oracle access to Uψ , a counterfeiter C needs Ω ε2n/2 queries to prepare a
2n-qubit state ρ that a projector Vψ⊗2 onto |ψi⊗2 accepts with probability at least ε, for all 1/ε = o (2n ).
Here the probability is taken over the choice of |ψi, as well as the behavior of C and Vψ⊗2 .
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 396
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Acknowledgments
We thank Andris Ambainis, Boaz Barak, Dmitry Gavinsky, Daniel Gottesman, Aram Harrow, Yuval Ishai,
Shelby Kimmel, Shaunak Kishore, Greg Kuperberg, Andy Lutomirski, Abel Molina, Rafi Ostrovsky,
Amit Sahai, Peter Shor, and John Watrous for helpful discussions and correspondence; and the anonymous
reviewers and ToC editors for their comments.
References
[1] S COTT A ARONSON: Quantum lower bound for the collision problem. In Proc. 34th STOC, pp.
635–642. ACM Press, 2002. Preprint at arXiv. [doi:10.1145/509907.509999] 354
[2] S COTT A ARONSON: Limitations of quantum advice and one-way communication. The-
ory of Computing, 1(1):1–28, 2005. Preliminary version in CCC’04. Preprint at arXiv.
[doi:10.4086/toc.2005.v001a001] 363
[3] S COTT A ARONSON: Quantum copy-protection and quantum money. In Proc. 24th IEEE
Conf. on Computational Complexity (CCC’09), pp. 229–242. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/CCC.2009.42] 353, 355, 356, 357, 366, 373, 390, 392, 393, 395
[4] S COTT A ARONSON: On the security of private-key quantum money, 2013. In preparation. 390, 391
[5] S COTT A ARONSON AND G REG K UPERBERG: Quantum versus classical proofs and advice.
Theory of Computing, 3(7):129–157, 2007. Preliminary version in CCC’07. Preprint at arXiv.
[doi:10.4086/toc.2007.v003a007] 360
[6] S COTT A ARONSON AND YAOYUN S HI: Quantum lower bounds for the collision and the element
distinctness problems. J. ACM, 51(4):595–605, 2004. [doi:10.1145/1008731.1008735] 354
[7] M ARTIN R. A LBRECHT AND C ARLOS C ID: Cold boot key recovery by solving polynomial systems
with noise. In Proc. 9th Internat. Conf. on Applied Cryptography and Network Security (ACNS’11),
pp. 57–72. Springer, 2011. Available in preprint. [doi:10.1007/978-3-642-21554-4_4] 388
[8] N OGA A LON , M ICHAEL K RIVELEVICH , AND B ENNY S UDAKOV: Finding a large hidden clique in
a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998. Preliminary version in
SODA’98. [doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W] 353
[9] A NDRIS A MBAINIS: Quantum lower bounds by quantum arguments. J. Comput. Sys-
tem Sci., 64(4):750–767, 2002. Preliminary version in STOC’00. Preprint at arXiv.
[doi:10.1006/jcss.2002.1826] 354, 355, 361, 372, 373
[10] A NDRIS A MBAINIS , L OÏCK M AGNIN , M ARTIN ROETTELER , AND J ÉRÉMIE ROLAND: Symmetry-
assisted adversaries for quantum state generation. In Proc. 26th IEEE Conf. on Computa-
tional Complexity (CCC’11), pp. 167–177. IEEE Comp. Soc. Press, 2011. Preprint at arXiv.
[doi:10.1109/CCC.2011.24] 354, 374
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 397
S COTT A ARONSON AND PAUL C HRISTIANO
[11] B OAZ BARAK , O DED G OLDREICH , RUSSELL I MPAGLIAZZO , S TEVEN RUDICH , A MIT S AHAI ,
S ALIL P. VADHAN , AND K E YANG: On the (im)possibility of obfuscating programs. J. ACM,
59(2):6, 2012. Preliminary versions in CRYPTO’01 and ECCC. [doi:10.1145/2160158.2160159]
392
[12] ROBERT B EALS , H ARRY B UHRMAN , R ICHARD C LEVE , M ICHELE M OSCA , AND RONALD
DE W OLF : Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary
version in FOCS’98. Preprint at arXiv. [doi:10.1145/502090.502097] 354
[13] C HARLES H. B ENNETT, E THAN B ERNSTEIN , G ILLES B RASSARD , AND U MESH V. VAZIRANI:
Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997.
Preprint at arXiv. [doi:10.1137/S0097539796300933] 361, 373, 382
[14] C HARLES H. B ENNETT AND G ILLES B RASSARD: Quantum cryptography: public key distribution
and coin tossing. In Proc. IEEE Internat. Conf. on Computers, Systems and Signal Processing, pp.
175–179, 1984. 353, 358
[15] C HARLES H. B ENNETT, G ILLES B RASSARD , S ETH B REIDBART, AND S TEPHEN W IESNER:
Quantum cryptography, or unforgeable subway tokens. In Proceedings of CRYPTO, pp. 267–275.
Plenum Press, 1982. 353, 356, 367, 390, 392
[16] N IELS B OHR: Atomic Physics and Human Knowledge. Dover, 2010. First published 1961. 359
[17] DAN B ONEH , Ö ZGÜR DAGDELEN , M ARC F ISCHLIN , A NJA L EHMANN , C HRISTIAN S CHAFFNER ,
AND M ARK Z HANDRY: Random oracles in a quantum world. In 17th Internat. Conf. on the Theory
and Application of Cryptology and Information Security (ASIACRYPT’11), pp. 41–69, 2011. Preprint
at arXiv. [doi:10.1007/978-3-642-25385-0_3] 361
[18] C HARLES B OUILLAGUET, J EAN -C HARLES FAUGÈRE , P IERRE -A LAIN F OUQUE , AND L UDOVIC
P ERRET: Practical cryptanalysis of the identification scheme based on the isomorphism of poly-
nomial with one secret problem. In 14th Internat. Conf. on Practice and Theory in Public Key
Cryptography (PKC’11), pp. 473–493. Springer, 2011. [doi:10.1007/978-3-642-19379-8_29] 358,
389
[19] G ILLES B RASSARD , P ETER H ØYER , M ICHELE M OSCA , AND A LAIN TAPP: Quantum amplitude
amplification and estimation. In J R . S AMUEL J. L OMONACO AND H OWARD E. B RANDT, editors,
Quantum Computation and Information, Contemporary Mathematics Series. AMS, 2002. Preprint
at arXiv. 363
[20] DAVID C ASH , D ENNIS H OFHEINZ , E IKE K ILTZ , AND C HRIS P EIKERT: Bonsai trees, or how
to delegate a lattice basis. J. Cryptology, 25(4):601–639, 2012. Preliminary version in EURO-
CRYPT’10. [doi:10.1007/s00145-011-9105-2] 360
[21] S OURAV C HAKRABORTY, JAIKUMAR R ADHAKRISHNAN , AND NANDAKUMAR R AGHUNATHAN:
Bounds for error reduction with few quantum queries. In Proc. 9th Internat. Workshop on Random-
ization and Computation (RANDOM’05), pp. 245–256. Springer, 2005. [doi:10.1007/11538462_21]
364
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 398
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
[22] J INTAI D ING AND B O -Y IN YANG: Multivariate public key cryptography. In DANIEL J. B ERN -
STEIN , J OHANNES B UCHMANN , AND E RIK DAHMEN , editors, Post-Quantum Cryptography, pp.
193–241. Springer, 2009. [doi:10.1007/978-3-540-88702-7_6] 388
[23] E DWARD FARHI , DAVID G OSSET, AVINATAN H ASSIDIM , A NDREW L UTOMIRSKI , DANIEL
NAGAJ , AND P ETER S HOR: Quantum state restoration and single-copy tomography for
ground states of Hamiltonians. Phys. Rev. Lett., 105(19):190503, 2010. Preprint at arXiv.
[doi:10.1103/PhysRevLett.105.190503] 354, 355, 391, 392
[24] E DWARD FARHI , DAVID G OSSET, AVINATAN H ASSIDIM , A NDREW L UTOMIRSKI , AND P ETER W.
S HOR: Quantum money from knots. In Proc. 3rd Innovations in Theoretical Comput. Sci. (ITCS’12),
pp. 276–289. ACM Press, 2012. Preprint at arXiv. [doi:10.1145/2090236.2090260] 353, 354, 355,
356, 357, 366, 367, 369, 370
[25] D MITRY G AVINSKY: Quantum money with classical verification. In Proc. 27th IEEE Conf. on
Computational Complexity (CCC’12), pp. 42–52. IEEE Comp. Soc. Press, 2012. Preprint at arXiv.
[doi:10.1109/CCC.2012.10] 353
[26] W ILLI G EISELMANN , W ILLI M EIER , AND R AINER S TEINWANDT: An attack on the isomorphisms
of polynomials problem with one secret. Int. J. Inf. Sec., 2(1):59–64, 2003. [doi:10.1007/s10207-
003-0025-5] 358, 389
[27] L OV K. G ROVER: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC,
pp. 212–219. ACM Press, 1996. Preprint at arXiv. [doi:10.1145/237814.237866] 363
[28] C HRISTOPHER J. H ILLAR AND L EK -H ENG L IM: Most tensor problems are NP-hard. Technical
report, 2009. [arXiv:0911.1393] 389
[29] T ROY L EE , R AJAT M ITTAL , B EN W. R EICHARDT, ROBERT S PALEK , AND M ARIO S ZEGEDY:
Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp.
Soc. Press, 2011. Preprint at arXiv. [doi:10.1109/FOCS.2011.75] 374
[30] A NDREW L UTOMIRSKI: An online attack against Wiesner’s quantum money. Technical report,
2010. [arXiv:1010.0256] 353, 354, 356, 357, 390
[31] A NDREW L UTOMIRSKI: Component mixers and a hardness result for counterfeiting quantum
money. Technical report, 2011. [arXiv:1107.0321] 354
[32] A NDREW L UTOMIRSKI , S COTT A ARONSON , E DWARD FARHI , DAVID G OSSET, J ONATHAN A.
K ELNER , AVINATAN H ASSIDIM , AND P ETER W. S HOR: Breaking and making quantum money:
Toward a new quantum cryptographic protocol. In Proc. Innovations in Comput. Sci. (ICS’10), pp.
20–31. Tsinghua University Press, 2010. ICS’10. Preprint at arXiv. 353, 354, 355, 356, 357, 366,
367, 369, 370
[33] A BEL M OLINA , T HOMAS V IDICK , AND J OHN WATROUS: Optimal counterfeiting attacks and
generalizations for Wiesner’s quantum money. In Proc. 7th Conf. Theory of Quantum Computation,
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 399
S COTT A ARONSON AND PAUL C HRISTIANO
Communication, and Cryptography (TQC’12), pp. 45–64, 2012. Preprint at arXiv. [doi:10.1007/978-
3-642-35656-8_4] 352, 353, 390
[34] M ICHELE M OSCA AND D OUGLAS S TEBILA: Quantum coins. In Error-Correcting Codes, Finite
Geometries and Cryptography, volume 523, pp. 35–47. Amer. Math. Soc., 2010. Preprint at arXiv.
353
[35] M ONI NAOR AND M OTI Y UNG: Universal one-way hash functions and their cryptographic applica-
tions. In Proc. 21st STOC, pp. 33–43. ACM Press, 1989. [doi:10.1145/73007.73011] 361
[36] M ICHAEL N IELSEN AND I SAAC C HUANG: Quantum Computation and Quantum Information.
Cambridge University Press, 2000. [ACM:544199] 361, 362
[37] F ERNANDO PASTAWSKI , N ORMAN Y. YAO , L IANG J IANG , M IKHAIL D. L UKIN , AND J. I GNACIO
C IRAC: Unforgeable noise-tolerant quantum tokens. Technical report, 2011. [arXiv:1112.5456]
353
[38] JACQUES PATARIN , L OUIS G OUBIN , AND N ICOLAS C OURTOIS: Improved algorithms for isomor-
phisms of polynomials. In Proc. Internat. Conf. on the Theory and Application of Cryptographic
Techniques (EUROCRYPT’98), pp. 184–200. Springer, 1998. [doi:10.1007/BFb0054126] 358, 389
[39] O DED R EGEV: On lattices, learning with errors, random linear codes, and cryptography. J. ACM,
56(6):34, 2009. Preliminary version in STOC’05. [doi:10.1145/1568318.1568324] 388
[40] J OHN ROMPEL: One-way functions are necessary and sufficient for secure signatures. In Proc.
22nd STOC, pp. 387–394. ACM Press, 1990. [doi:10.1145/100216.100269] 361
[41] TATHAGAT T ULSI , L OV K. G ROVER , AND A POORVA PATEL: A new algorithm for fixed point
quantum search. Quantum Inf. Comput., 6(6):483–494, 2006. QIC. [ACM:2011693] 356, 364
[42] S TEPHEN W IESNER: Conjugate coding. SIGACT News, 15(1):78–88, 1983. Original manuscript
written circa 1970. [doi:10.1145/1008908.1008920] 352, 356, 389, 391, 392
AUTHORS
Scott Aaronson
associate professor
Massachusetts Institute of Technology, Cambridge, MA
aaronson csail mit edu
http://www.scottaaronson.com
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 400
Q UANTUM M ONEY FROM H IDDEN S UBSPACES
Paul Christiano
Ph. D. student
University of California, Berkeley
paulfchristiano gmail com
ABOUT THE AUTHORS
S COTT A ARONSON received his bachelor’s degree from Cornell University and his Ph. D.
from UC Berkeley. He is known for his blog and for founding the Complexity Zoo. He
publishes often in Theory of Computing.
PAUL C HRISTIANO is a Ph. D. student at UC Berkeley. He obtained a bachelor’s in math-
ematics from MIT in 2012. As an undergraduate his research was scattered between
combinatorial optimization, data structures, and quantum cryptography.
T HEORY OF C OMPUTING, Volume 9 (9), 2013, pp. 349–401 401