- Infinite Randomness Expansi...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in January 2014
Infinite Randomness Expansion with a Constant Number of Devices
Date: Thursday, January 23, 2014
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Contact: Ilya Razenshteyn, email@example.com
Relevant URL: http://mittheory.wordpress.com/2013/12/25/can-you-tell-if-a-bit-is-random/
Speaker URL: None
TALK: Infinite Randomness Expansion with a Constant Number of Devices
We present a device-independent randomness expansion protocol, involving only a constant number of non signaling quantum devices, that achieves in?nite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certi?ed randomness that is exp(??(m^1/3))-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in m). This settles an open problem in the area of randomness expansion and device-independence.
We also present a protocol that achieves in?nite randomness ampli?cation using a constant number of devices. The input seed is not necessarily uniform, but can be generated from a Santha-Vazirani source, a type of weak randomness. The output is still nearly uniform, secure against a quantum adversary, and can be arbitrarily long. In contrast, it is well known that classically one cannot extract even a single near-uniform bit from a Santha-Vazirani source.
The analysis of our protocols involves overcoming fundamental challenges in the study of adaptive device-independent protocols. Our primary technical contribution is the design and analysis of device-independent protocols which are Input Secure; that is, their output is guaranteed to be secure against a quantum eavesdropper, even if the input randomness was generated by that same eavesdropper!
The notion of Input Security may be of independent interest to other areas such as device independent quantum key distribution.
Join work with Henry Yuen.
Created by Ilya Razenshteyn at Tuesday, January 21, 2014 at 10:58 AM.