Best abstract ever. Sadly, the quantum money scheme it's based on is insecure [1]. (IIRC the concrete version was broken earlier using quantum state restoration [2] -- shameless plug!)
The concept is extremely cool, though, and I hope they find an alternate construction for it. I suspect it will be very hard to base it on the Farhi et al. money [3] because that scheme has no secrets at all, which means that the public key doesn't naturally map onto it. On the other hand, it just might be possible to shoehorn it in by using the list of valid serial numbers as the (rather long but very compressible) public key. In essence, you'd be proving both possession and consumption of a token that has a completely known state that happens to be very difficult to generate. I'll sleep on it.
As an exercise for the reader, prove that their notion of "everlasting security" is impossible if the attacker is allowed to know the public key. :)
We report on this attack in Section 7.2, and propose how to fix it in Section 7.3. We prove security based on some strong form of Virtual Black Box (VBB) obfuscation, and conjecture that it is secure (and provide some supporting arguments) under the assumption of indisitnguishability obfuscation.
Regarding your second comment: we definitely tried to base it on the "money from knots" scheme, and more generally, assuming arbitrary public QM scheme. We failed. "In essence, you'd be proving both possession and consumption of a token that has a completely known state that happens to be very difficult to generate." The procedure should depend on the document's content. There seems nothing that can be done other than "measuring in the standard basis" which is not document dependent, and furthermore, unclear whether it reveals any "hard to generate" information (given a public key - an Alexander polynomial - it's probably easy to find a knot with that polynomial. This is not the case in Aaronson & Christiano's construction). I hope this comment makes sense. If you have some ideas, I'll be more than happy to hear them.
The conversion into a classical check bit sounds kind of trivial, since the bank has to do the verification of the check. Just add some EPR pairs to the token and use them for teleportation. The measurement results of the teleportation are the classical check.
Edit: Ah, you can verify the signature without the bank. Instead of teleporting you sign a message like "I give this token to Bob. Bank please generate a replacement token for him because signing this message destroyed mine.".
> The conversion into a classical check bit sounds kind of trivial, since the bank has to do the verification of the check. Just add some EPR pairs to the token and use them for teleportation. The measurement results of the teleportation are the classical check.
Be very, very careful doing things like this. For example, if the bank knows a secret, uses it to verify your token, and returns the token back to you even if it was invalid, you get a nice oracle to use to attack the bank's secret. See, for example:
The protocol from the paper already includes a 'verify token' function. I don't see how teleporting the token, vs using a more typical quantum channel like a fiber optic line, would increase any of the risks.
...
...
Maybe there are situations where an attacker could substitute their own EPR pairs into your token? EPR pairs aren't separately verifiable, so you wouldn't realize. And if the attacker intercepted the classical channel you used to send the measurement results for the teleportation then you would accidentally be sending the token to the attacker instead of the bank. Even if the attacker just listened in, and you or the bank realized the attack was happening when the verify failed, the protocol doesn't require checking with the bank before accepting a token and so the attacker can still spend the token.
What I meant was: be careful when applying an operation involving secrets to untrusted input. It's very easy to leak your secrets.
This doesn't matter with this scheme because verification doesn't use any secrets. (Well, sort of. If you're taking advantage of "everlasting security", then the public key is secret.)
The concept is extremely cool, though, and I hope they find an alternate construction for it. I suspect it will be very hard to base it on the Farhi et al. money [3] because that scheme has no secrets at all, which means that the public key doesn't naturally map onto it. On the other hand, it just might be possible to shoehorn it in by using the list of valid serial numbers as the (rather long but very compressible) public key. In essence, you'd be proving both possession and consumption of a token that has a completely known state that happens to be very difficult to generate. I'll sleep on it.
As an exercise for the reader, prove that their notion of "everlasting security" is impossible if the attacker is allowed to know the public key. :)
[1] http://www.scottaaronson.com/blog/?p=2903 [2] https://arxiv.org/abs/0912.3823 [3] https://arxiv.org/abs/1004.5127 [and yes, I'm part of "et al"]