Certifiable Quantum Dice
Speaker: Thomas Vidick , CSAIL, MIT
Date: February 21 2012
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Costis Daskalakis, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: Motivation for the field of pseudorandomness stems from a fundamental
observation: since no statistical test can distinguish a uniformly
random string from one that has been carefully crafted to pass that
specific test, no physical process can be trusted to produce truly
random bits -- hence the need for pseudorandom bits.
While quantum mechanics trivially allows for the generation of
randomness, when combined with the no-signaling principle it allows
for a much more remarkable effect: a physical device whose output is
certifiably random as long as it passes a simple statistical test. The
guarantee that the device's outputs are random (that is, any
particular n-bit output has probability close to 2^{-n}) is
independent of the validity of quantum mechanics, and follows only
from the statistical test and the fact that a no-signaling condition
is met between two parts of the device (such a condition may follow,
for instance, from the speed of light limit imposed by special
relativity).
We describe such a device that stretches an initial (log n)-bit random
string into n random bits, thereby realizing an exponential expansion
of randomness. The underlying statistical test is based on a simple
Bell inequality, the CHSH inequality. In addition we show that the
random bits produced by the device may be used in post-quantum
cryptography by proving that they are random even from the point of
view of a quantum adversary, who may have prior entanglement with the
very device used to generate the random bits. This answers a question
left open since the introduction of quantum randomness-generating
devices by Colbeck in 2009.
Based on joint work with Umesh Vazirani.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in February 2012
