8

What level of trust in the bank is needed in "Quantum Money from Hidden Subspaces" of Aaronson and Christiano (arXiv)?

The bank's mint works by first generating a uniformly random classical secret string $r$, and then generating a banknote $\\\$_r=(S_r,\rho_r)$. The authors state that the bank can generate many identical banknotes by simply reusing the secret $r$.

  • But after the currency is distributed, is $r$ needed, either by the bank or by the users, ever again? If so, does the bank need to keep it safe and secure? If not, should the bank "forget" or destroy the secret $r$ used in the mini-scheme, lest it fall into a forger's hand?

  • Can the mint use $r$ to produce many coins with a specific serial number $S_r$, potentially targeting a specific holder of currency for devaluation?

  • Can the users of the currency know how many coins are actively in circulation, without having to trust the mint?

The authors of Hidden Subspaces note that in "Quantum Money from Knots" of Farhi, Gosset, Hassidim, Lutomirski, and Shor (arXiv), not even the mint is likely able to generate two identical banknotes.

But I think that the inability of banks to copy their own currency is a feature, not a bug, of "Quantum Money from Knots", because the actions of the mint are public and known. The total amount of currency is known; no secret $r$ is needed to be kept safe or destroyed; the mint can "destroy" a coin by removing it from the public list of serial numbers (Alexander polynomials,) but cannot target a coin for devaluation by minting many copies.

Frederik vom Ende
  • 4,163
  • 3
  • 12
  • 49
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83

1 Answers1

4

Aaronson and Christiano proved the security of their scheme in an oracle model, where they assume the verifier has access to a membership oracle to some subspace $A$. In order to turn this into actual quantum money, it is "sufficient" to implement "such an oracle".

How would one do that? And what is "such an oracle"? Well, the simplest question is to implement the oracle as a bank which would answer queries for you, that is, to implement private quantum money. If someone would manage to create a classical program they could give you, such that whatever you could learn from inspecting the program you could also learn just by querying it, this would constitute a full blown black box. This is the notion of Virtual Black Box (VBB), and it is known to be impossible under a variety of assumptions.

Thus, a weaker notion is required. AC tried an ad-hoc approach, where they suggested a specific subspace obfuscator (a sufficiently large list of random low degree polynomials which vanish on the hidden subspace), which were famously broken shortly after.

In a yet to be published work, Mark Zhandry has shown how an appropriate obfuscator could be constructed under the assumption of indistinguishability obfuscators and the existence of one way bijections (cf. chapter 5), which is considerably milder than the black box assumption but is still quite stronger than, say, one way functions.

So the state of the art for AC's construction is that it can be made public under the assumption of indistinguishability obfuscation (and one way bijections).

Edit: After reading the comment I realized that I've missed some of the nuance on the question.

In ACs scheme $r$ is a basis for the vector space used to construct the money state. $S_r$ is a membership oracle for that space and its dual. The basis itself is no longer required for verification. Yes, holding on to r allows to create many bills with identical serial numbers, though don't understand their incentive to do so. Also note that in the AC schemes, a small amount of identical bills (linear in the security parameter) suffices to learn how to create infinitely many identical bills without ever being told $r$ (because if you measure, say $n$ random vectors from an $n/2$-dimensional space, you get a spanning set with overwhelming probability).

Also, as far as I understand, neither of the two schemes you mentioned allows for users to know how many coins were minted without trusting the mint.

Shai Deshe
  • 176
  • 4