[quantum-info] Q+ hangout: Scott Aaronson, June 19 @ 9am, RAC1 3004
Marco Piani
marcopiani at gmail.com
Thu Jun 14 13:55:38 EDT 2012
IQC, RAC1 3004
Tuesday, June 19
9:00am
Scott Aaronson, MIT
Title: Quantum Money from Hidden Subspaces
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. Based on http://arxiv.org/abs/1203.4740
Joint work with Paul Christiano
For more information about the Q+ hangouts visit http://qplus.burgarth.de/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.uwaterloo.ca/pipermail/quantum-info/attachments/20120614/e067a1c0/attachment.html>
More information about the quantum-info
mailing list