Broken Glass Everywhere. If it Ain't About Quantum Money, I Just Don't Care

Note the new location (updated 9/28/09)

The Optimizer is coming to town, which is always fun:

TIME: 1:30-2:30 pm, Tuesday, September 29, 2009

PLACE: CSE 305

SPEAKER: Scott Aaronson (MIT)

TITLE: Quantum Money

ABSTRACT:
Ever since there's been money, there have been people trying to counterfeit it, and governments trying to stop them. In a remarkable 1969 manuscript, Stephen Wiesner raised the possibility of money whose authenticity would be guaranteed by the laws of quantum physics. However, Wiesner's money can only be verified by the bank that printed
it -- and the natural question of whether one can have secure quantum money that *anyone* can check has remained open for forty years. In this talk, I'll tell you about progress on the question over the last year.

- I'll show that no "public-key" quantum money scheme can have security based on quantum physics alone: like in most cryptography, one needs a computational hardness assumption.

- I'll show that one can have quantum money that remains hard to counterfeit, even if a counterfeiter gains black-box access to a device for checking the money.

- I'll describe a candidate quantum money scheme I proposed last spring, and how that scheme was broken a few weeks ago by myself, Farhi, Gosset, Hassidim, Kelner, Lutomirski, and Shor.

- I'll describe a new quantum money scheme we propose in the same work. Our new scheme has the strange property that not even the bank can prepare the same bill twice.

Reference for the first two results: S. Aaronson, "Quantum copy-protection and quantum money," in Proceedings of CCC'2009, http://www.scottaaronson.com/papers/noclone-ccc.pdf. The "AFGHKLS" paper should be posted to the arXiv soon.

The last line makes me ask: has anyone every written a paper with all of the letters of the alphabet for last names (and no duplicate uses!)