Two announcements
Tomorrow, at 9AM EST (or an hour before teatime in Britain), I’ll be giving an online talk on Quantum Money from Hidden Subspaces (see here for PowerPoint slides) at the Q+ hangout on Google+. To watch the talk, go here, then click the “Play” button on the video that will be there tomorrow. Abstract:
Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a “classical” hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the “black-box” version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner’s original setting — quantum money that can only be verified by the bank — we are able to use our techniques to patch a major security hole in Wiesner’s scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis — matching the original intuition for quantum money, based on the existence of complementary observables. Our security proofs use a new variant of Ambainis’s quantum adversary method, and several other tools that might be of independent interest. Joint work with Paul Christiano.
Update: Here’s a YouTube video of the talk.
In unrelated news, Alistair Sinclair asked me to announce that UC Berkeley’s new Simons Institute for Theoretical Computer Science—you know, the thing Berkeley recently defeated MIT (among others) to get—is soliciting proposals for programs. The deadline is July 15, so be sure to get your proposal in soon.
Follow
Comment #1 June 18th, 2012 at 12:15 pm
The last link to simons.berkeley.edu/cfp_summer2012.html is incorrect.
Comment #2 June 18th, 2012 at 12:33 pm
Woo Hoo
Sounds fun! I will make sure to attend it.
Comment #3 June 18th, 2012 at 4:08 pm
Quantum money does not buy happiness.
Comment #4 June 18th, 2012 at 5:04 pm
Wim: Thanks!! I fixed it after someone emailed me about it.
Comment #5 June 19th, 2012 at 3:18 am
I would love to see this talk, but 6:00 am is far too early.
Comment #6 June 19th, 2012 at 9:11 am
Very nice talk. Thanks!
Comment #7 June 19th, 2012 at 9:43 am
Thanks, Joe! As I said, I don’t expect this to be the next YouTube sensation, but hopefully it can find a few niche viewers. 🙂
Comment #8 June 20th, 2012 at 9:56 pm
Would this scheme allow to trace quantum money? If so it won’t be popular with the tin-foil crowd.
Comment #9 June 21st, 2012 at 10:08 pm
It seems to me that another application of this scheme could be tamper prove voting. I.e. no ballot stuffing is possible if the ballots are marked in this fashion, and created based on the eligible voter registry. (You still need a small amount of ballots in reserve for eligible non-registered voters, but those will be at the margin, and irregularities in this area should be fairly easy to spot).
Comment #10 June 22nd, 2012 at 8:07 am
Scott,
Off topic but, well, is this ever off topic? 🙂
“A quantum algorithm for solving the 3-SAT problem”
http://arxiv.org/abs/1206.4747
Comment #11 June 23rd, 2012 at 1:08 pm
Mike: Obvious crap, but you didn’t need me to tell you that, did you? 🙂
Hard to tell exactly what the authors are doing, but it looks like they might just be rescaling the energies to make the running time falsely appear “constant,” one of the oldest tricks in the book.
Comment #12 June 23rd, 2012 at 1:11 pm
Henning Dekant #8: Excellent question!
Well, since my and Paul’s scheme involves serial numbers, it would have all the traceability properties that classical money has in virtue of having serial numbers on each bill. But it wouldn’t have additional traceability—e.g., there would be no way to tell, by measuring a valid bill, who or how many people had measured that bill in the past.
In my earlier CCC’2009 paper, I also considered quantum money schemes with no serial numbers, where each bill is literally the same quantum state. But those sorts of schemes tend to be much harder to construct, and it’s not even obvious that they’re preferable (maybe you want serial numbers!).
Comment #13 June 23rd, 2012 at 10:33 pm
Thanks Scott! BTW very enjoyable talk.
Comment #14 June 26th, 2012 at 12:09 pm
Hey Scott,
what’s your take on Dr. Z’s newest opinion for Turing’s 100th anniversary :>
http://www.math.rutgers.edu/~zeilberg/Opinion125.html
Comment #15 June 28th, 2012 at 6:43 am
Anyone with an opinion on this paper?
http://arxiv.org/abs/1206.6224
Comment #16 June 28th, 2012 at 6:23 pm
Peter #14: Like most of Zeilberger’s “opinions,” that one strikes me as so egregiously wrong that one wonders to what extent he himself believes it, and to what extent he just likes throwing bombs at the “mathematical establishment.”
Let M be a Turing machine that enumerates all ZF proofs, and halts iff it finds a proof of 0=1.
Then “M never halts” is a perfectly-meaningful statement (it even makes a falsifiable prediction about an actual computer program—what more could you want?), which happens not to be provable in ZF assuming ZF’s consistency.
By contrast, “M tastes like chicken” is a meaningless statement.
Putting both of these statements into the same category (“meaningless”) strikes me as a bizarre twisting of language in the service of an ideology (something I don’t like even for good ideologies!). Indeed, a moment’s thought reveals that, if Zeilberger’s suggestion were adopted, mathematicians would immediately start working around it with circumlocutions (“meaningless in the sense of not provable in ZF” vs. “meaningless in the sense of meaningless”).
Comment #17 June 28th, 2012 at 6:57 pm
Jonas #15: I have to say that, from what I understand of that paper, I find it extremely unsatisfying. The authors are not proposing an actual modification to QM: everything they discuss, including weak measurements, is easily accommodated in standard QM. But standard QM doesn’t involve any backwards-in-time causation, or any superluminal communication, or any restrictions on the experimenters’ free will. From this, it would seem to follow that their experiment must be describable in standard QM without invoking any of those things. Crucially, this argument is completely insensitive to the details of their experiment.
If I’m right, then the authors have a high burden to meet: they have to explain why backwards-in-time causation provides a better way of talking about their experiment than standard QM. But their attempt to meet that burden, on pages 10-12, seems woefully inadequate. They describe some particular ways one could “try” to describe their experiment in standard QM, and find various ad hoc grounds for ridiculing those ways. But they never grapple with the general argument for why such an experiment has to be describable in standard QM: namely, if it weren’t so describable, then we’d have an experimental deviation from QM on our hands! This strongly suggests to me that, contrary to the authors’ protestations, standard QM is never getting a fair hearing in this paper.
Comment #18 June 28th, 2012 at 7:30 pm
Peter #14, please allow me to offer a contrasting opinion regarding Doron Zeilberger’s opinion #125. Namely, if we focus upon Doron’s concrete recommendations for research directions, in particular the recommendation to pursue oracle-independent proof methods, then we appreciate that Doron’s opinions are very much in the tradition of Juris Hartmanis. And please let me mention also, that oracle-independent formalisms are reasonably congenial to engineers too.
Comment #19 July 4th, 2012 at 9:31 pm
Thanks for this wow seminar 🙂
Is it possible that verifying money state is also by itself a procedure to correct for potential noise?
Comment #20 July 6th, 2012 at 11:47 am
My previous question has been jammed for a couple of days, but let’s keep hopes high and try another one.
At the end of the talk you mentionned your scheme could help protecting softeware copyright. Could it also provide a way to securize cloud computing?
Comment #21 July 6th, 2012 at 7:26 pm
Hi Scott,
I had not heard of this until recently, but there is this idea of a topological quantum computer that is quite different from the “decorherence prone” “ordinary” quantum computer. I’ve never seen you blog about it. And the braid-based logic circuits appear to be quite cool—probably involves some nicer math there. 🙂
I would love to learn more about TQC, if you will explain it to me.
Thank you.
SB
Comment #22 July 7th, 2012 at 5:16 pm
Jiav: Yes, in “projective” schemes (like ours), where the verification just consists of a projective measurement, the verification procedure can itself correct noise! It’s similar to what’s called the “Quantum Zeno Effect” or better, “Watched Pot Never Boils” effect, wherein you can prevent a quantum state from “drifting” by continually applying a projective measurement to it. You’re absolutely right about that.
And yes, our recent unpublished work, on quantum obfuscation and quantum copy-protection, should have applications to secure cloud computing. However, I should mention that secure cloud computing is in some sense an “easier” problem than obfuscation and copy-protection—indeed, the recent breakthroughs on fully homomorphic encryption let you do secure cloud computing under a plausible classical cryptographic assumption, with no quantum needed. And conversely, the recent breakthroughs on blind quantum computing let you do secure cloud computing with quantum and no cryptographic assumptions. By contrast, to get obfuscation of arbitrary programs, or copy-protection of any programs, you seem to need both quantum and cryptographic assumptions.
Comment #23 July 7th, 2012 at 6:16 pm
Thx Scott. This is an exciting time!
Comment #24 July 8th, 2012 at 4:14 pm
Jiav, a paradox that you can use to assess your understanding of quantum noise and measurement is as follows:
• noise is equivalent to measurement,
• measurement suppresses decay,
• the interior of a star is noisy,
• so nuclear lifetimes are longer in stars.
But this is not observed. Why?
Comment #25 July 8th, 2012 at 10:36 pm
Or… we could encode money into bit strings of size X, where the average market cost of storing X is estimated to match the encoded value.
For example, $100 would be encoded as a bit string of 1 terabyte. This would be analogous to gold based currency – it’s currency backed by server storage.
Can you come up with a way to encode currency such that it’s backed by the average market cost of CPU time?
Comment #26 July 13th, 2012 at 1:22 pm
Scott@16: it even makes a falsifiable prediction about an actual computer program—what more could you want?
You could want a falsifiable prediction about an actual computer. DZ is quite explicit about this: infinite tapes don’t exist. It’s one thing to respond “They do too make sense,” but to respond “They do too exist” is not only wrong, but seems to me to be an unfair response.
That is not to say I can extract a consistent position from DZ. He seems to be willing to quantify over all sizes of machine, which does not seem to me very different from allowing infinite sizes. (At least, it is easy to translate Turing’s results into this language. It is probably possible to formally translate all of TCS, including oracles, into this language, which ought to adequate to define the meaning to DZ’s satisfaction. But some uses of infinity by mathematicians probably cannot be translated. Actually, the random oracle hypothesis probably cannot be so translated.)
Comment #27 July 28th, 2012 at 1:41 pm
Can someone comment on how this would effect, improve or replace the Bitcoin protocol?
Comment #28 July 30th, 2013 at 4:34 am
Thanks for every other informative web site.
Where else could I get that kind of information written in
such an ideal manner? I’ve a mission that I am just now operating on, and I’ve been on the look out
for such info.