3 ms·
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 restorati
by amluto 10y ago
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. :)
[1] http://www.scottaaronson.com/blog/?p=2903 http://www.scottaaronson.com/blog/?p=2903
[2] https://arxiv.org/abs/0912.3823 https://arxiv.org/abs/0912.3823
[3] https://arxiv.org/abs/1004.5127 https://arxiv.org/abs/1004.5127 [and yes, I'm part of "et al"]
- sattath 10y agoHi Andy! It's Or. 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.