We just released a new note on the arXiv, titled Publicly Verifiable Quantum Money with Low Quantum Computational Resources. In this work, we define a new quantum money cryotographic scheme with the following properties:
- The scheme allows to define quantum bills, that is, cryptographical objects representing some monetary value;
- These bills can be remotely exchanged as you do for other forms of e-currency such as BTC;
- These bills can be publicly verified. This means that everyone can verify that a given bill is authentic. This is in stark contrast with many quantum money schemes where the user can verify the bill authenticity only if the bill comes directly from the original issuer (such as the mint), which effectively makes the bills useless as they are not spendable with a third party. This was also a limitation of our previous efforts on the topic, which we now successfully overcome.
- The scheme relies on very little quantum resources. Indeed, we only need quantum internet infrastructure and quantum memories to make it work. This is in stark contrast with many other works on the topic, which instead require significant quantum computational resources.
Dramatis Personae
The main technial innovation we propose is called a verifiable one-time program. If you are an habituée of this blog, you know we like one-time things, so this should not particularly surprise you. We won’t go over verifiable OTPs in detail here as we do not directly need them to talk about what we really wanna talk about, that is, quantum money. For now, all prerequisites we need can be summarized in the following cryptographic primitives:
- A cryptographic hashing scheme, that is, a function that allows you to map any kind of data into a fixed length string — nowadays usually 256 or 512 bits — in such a way that inverting the hash (finding some data that hashes to a pre-determined string) or finding collisions (two or more pieces of data that have the same hash) is computationally very hard.
- A public key signature scheme, that is, a cryptographic scheme where everyone has a private key — allowing them to sign something — and a public key — which is publicly known and allows other people to check that the signatures are authentic. Again, it should be computationally very hard to reconstruct the private key from the public key, otherwise everyone would be able to sign things on behalf of someone else.
- A one-time memory, that is, a cryptographic device that works like so: it has two bitstrings in memory; a user can specify a binary value, say 0 or 1; depending on the value specified, one of the two bitstrings is revealed, and the other is permanently destroyed.
With these primitives, we can build a quantum bill. We use the term “quantum bill”, originally introduced by Wiesner in his famous quantum money paper, as just a fancy way to describe a trivial verifiable one-time memory with memorized bitstrings of lenght zero. But please feel free to ignore the technical jargon if it sounds complicated!
Building quantum bills
Building a bill with the conceptual blocks highlighted above works like so: suppose you are the mint, or the issuance protocol, or whatever mechanism you want to use to issue money. You:
- Select $n$ pairs of random numbers. If you like math, we can denote these pairs as $(x_1,y_1), \dots, (x_n,y_n)$;
- Hash them and sign the hashes. Denoting our hash function with $H$, this gives us $\left(H(x_1),H(y_1)\right),$ $\dots,$ $\left(H(x_n),H(y_n)\right)$ and $\left(\sigma_{H(x_1)},\sigma_{H(y_1)}\right),$ $\dots,$ $\left(\sigma_{H(x_n)},\sigma_{H(y_n)}\right)$, where $\sigma_d$ denotes the signature on some piece of thata $d$ (in our case the hashes);
- Put each of your original pairs $(\sigma_{H(x_1)},\sigma_{H(y_1)})$ into an OTM, obtaining $\texttt{OTM}_1, \dots, \texttt{OTM}_n$.
That’s it! You don’t need anything more than that. Now you can take this bunch of data and give it to some happy spender.
Now suppose instead that you are said happy spender, and that you want to use this bill to pay some merchant. Said merchant wants indeed to be a happy merchant as well, and so he wants to verify that you are not scamming him with a fake bill. How does he do that?
- First, he verifies that the signatures over the hashes are authentic, that is, that the bill has been issued by a reputable source (the mint or whatnot).
- Then, the merchant selects $M < N$ OTMs at random and opens them on some random input. He will now verify that each input so obtained hashes to the corresponding signed hash provided with the bill.
- Finally, the merchant adds the opened inputs to data representing the bill.
Let’s see this again slowly, supposing that the merchant picks just one OTM — call it $i$ — among the bunch:
- Merchant verifies the signatures $\left(\sigma_{H(x_1)},\sigma_{H(y_1)}\right),$ $\dots,$ $\left(\sigma_{H(x_n)},\sigma_{H(y_n)}\right)$ against the hashes $\left(H(x_1),H(y_1)\right),$ $\dots,$ $\left(H(x_n),H(y_n)\right)$. If the signatures are correct, he goes on to the next step. Otherwise, he rejects the bill;
- Merchant opens $\texttt{OTM}_i$ on some random input: he flips a coin, and will read either $x_i$ or $y_i$ depending if he lands heads or tails;
- Suppose the merchant reads $x_i$; He now computes $H(x_i)$ and verifies that it coincides with the corresponding value among $\left(H(x_1),H(y_1)\right),$ $\dots,$ $\left(H(x_n),H(y_n)\right)$. If this holds, he goes on to the next step. Otherwise, he rejects the bill;
- The merchant accepts the bill. He removes $\texttt{OTM}_i$ from the data making up the bill — after all $\texttt{OTM}_i$ has been already opened, and by definition $y_i$ has been erased and will never be recoverable — and replaces it with $x_i$, the value he read.
Why this is secure
Now, let’s briefly cover why this protocol works. Suppose I am a malicious attacker. I own a bill, and I want to spend it twice. To do so, I need to copy it. The hashes $\left(H(x_1),H(y_1)\right),$ $\dots,$ $\left(H(x_n),H(y_n)\right)$ and their signatures $\left(\sigma_{H(x_1)},\sigma_{H(y_1)}\right),$ $\dots,$ $\left(\sigma_{H(x_n)},\sigma_{H(y_n)}\right)$ are copiable without problems, but the $\texttt{OTM}_i$ are not. Note that this is by definition: if an OTM was copiable, we could trivially extract both bitstrings from its memory by first making a copy, and then measuring each copy on a different bit.
Since I cannot copy any of the $\texttt{OTM}_i$s, I am forced to resort to tricks. I have no way to know both the bitstrings $x_i, y_i$ stored in $\texttt{OTM}_i$, but I can measure one of them, say $x_i$, and make the other one up, call it $y’_i$. I can now prepare $\texttt{OTM’}_i$, storing $x_i, y’_i$ within it. Since I know both $x_i$ and $y’_i$, I can make as many copies of $\texttt{OTM’}_i$ as I want by just preparing it multiple times.
Going back to our merchant, by following the protocol we realize that if some of the OTMs have already been opened and replaced with “fake” OTMs, this will be detected with overwhelming probability: if for instance $\texttt{OTM}_i$ was already opened, it could have returned $x_i$ if and only if the merchant chose to measure on the first bit. Otherwise, it would have returned $y’_i$, and $H(y’_i) \neq H(y_i)$ with overwhelming probability. So the merchant would have accepted the bill with only 50% probability. Iterate it over $k$ trials, and you see that the probability of passing the test when all OTMs have been opened is $\frac{1}{2^k}$. More generally — and I admit without shame that the last time I did combinatorics was probably in my 2nd year of uni — if $U$ OTMs are unopened, $O$ have already been opened and tampered with, and we choose $C$ OTMs at random, the probability of passing the verification should™ be:
\[\frac{\sum_{i=0}^C \frac{1}{2^i} \cdot \binom{U}{C-i}\binom{O}{i}}{\binom{U + O}{C}}\]where $\binom{n}{k}$ denotes the binomial coefficient.
Combinatorial estimates apart, as you may have already become aware, bills produced in this way can only be verified a finite number of times. At some point too many OTMs will have been opened, so that the amount of unopened OTMs remaining for verification will be too small for anyone to deem the bill secure. This means that after a while these bills need to be returned to the issuer to be renewed. This is akin to real currency, which degrades over time and at some point needs to be replaced, but as much as we like the nostalgic comparison, it is a problem we’re working hard to overcome.
Why quantum?
You may have noticed that the word “quantum” doesn’t really show up in the construction of our quantum bills. This is by design, as the only primitives we need are the ones reported above — hashes, signatures, OTMs. The point is that there is no classical way of producing one-time memories. We could obtain something similar using TEEs, with all the trust assumptions that this entails. On the other hand, we could use a mixture of conjugate-coding and TEEs to build OTMs — as we already did here, for instance. The reason why using quantum resources here is particularly appealing is that it allows to package OTMs that come endowed with a bunch of qubits that are absolutely needed to open them. As qubits cannot be copied, this entails that, pretty much because of physics™, you cannot duplicate OTMs. At best, you can choose between sending them to merchant or maliciously giving him opened/fake OTMs, but as we said this can be detected with overwhelming probability.
Can I play with this?
But of course!™ We implemented a proof-of-concept Rust library here. We abstracted the primitives used as Rust traits, so you are free to instantiate it with whatever crypto scheme you prefer. Clearly, if you want to use conjugate coding, you’ll need some quantum internet equipment to do so, but if you limit yourself to using TEEs (without any sort of quantum aid) then you should be fine with a much cheaper setup. We can’t wait to receive your feedback on this, so please open issues and PRs if you wanna contribute! We finally repeat once more that the paper can be found here, on the arXiv.