8
$\begingroup$

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

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, 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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Aside: Have you seen this question I asked about time entangled quantum blockchains? $\endgroup$
    – user820789
    Commented Jul 13, 2018 at 3:56
  • 1
    $\begingroup$ @meowzz, yes thanks - this is helpful. Is your question more along the engineering challenges vs. the theoretical challenges? Also, the "Quantum Bitcoin" paper of Jorgenson does a good job of summarizing the state of the art, but I think I would disagree that FGHLS requires a "centralized" bank. Any mint in FGHLS can publish, in the open, the list of serial numbers. Such a mint cannot overproduce without having to update the list of serial numbers. But because, as far as I can tell, the mint in Aaronson and Chistiano "hides" the secret $r$... $\endgroup$
    – Mark Spinelli
    Commented Jul 13, 2018 at 12:01
  • 1
    $\begingroup$ as such, we need to trust this mint? (I'll be honest, I understand FGHLS better than Aaronson and Christiano at the moment.) $\endgroup$
    – Mark Spinelli
    Commented Jul 13, 2018 at 12:03
  • 1
    $\begingroup$ While this is somewhat orthogonal to the question, the Aaronson-Christiano quantum money protocol has been broken. And Daniel Kane has a new quantum money protocol based on modular forms. $\endgroup$
    – Peter Shor
    Commented Nov 11, 2019 at 0:49

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
14
  • $\begingroup$ I'm confused why AC needs $r$ in the first place. When they instantiate their black-box with the (quasi-polynomially broken) obfuscation, they seem to use $r$ for both the obfuscation and the digital signing. Their mint can generate currencies having the same serial number. This seems different from the FGHLS knots coins, or Kane's modular form approach. Also, Nakamoto taught that there's a risk in having the bank even keep secret the total amount of currency that actually has been produced, and there are advantages to having a public list, in the open, of all transactions. $\endgroup$
    – Mark Spinelli
    Commented Dec 21, 2019 at 18:24
  • $\begingroup$ I edited my answer $\endgroup$
    – Shai Deshe
    Commented Dec 22, 2019 at 13:45
  • $\begingroup$ As for knots/modular forms, I don't see why the entirety of the list of serial numbers (say Alexander polynomials) be made public and in plaintext, say in a database that is replicated amongst users of the coin. The number of entries in the database would correspond to the total number of coins produced. $\endgroup$
    – Mark Spinelli
    Commented Dec 22, 2019 at 13:58
  • 1
    $\begingroup$ No, that was a mistake which I will leave for posterity, here is the actual link: eprint.iacr.org/2017/1080.pdf $\endgroup$
    – Shai Deshe
    Commented Dec 23, 2019 at 10:31
  • 1
    $\begingroup$ @Shai Deshe: you can prove that the only states which are perfectly fixed by the Markovian process in our paper are the quantum money states. But if the Markov chain mixes slowly, then you might get states which are close enough to fixed to pass the verification test (but I don't see why creating these states shouldn't be as hard as forging the money in the first place). I'd say the most problematic assumption is that there's no easy way to create a superposition of an arbitrary Alexander polynomial. $\endgroup$
    – Peter Shor
    Commented Dec 27, 2019 at 4:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.