Infinite Randomness Expansion with a Constant Number of Devices

Speaker: Matthew Coudron , MIT

Date: Thursday, January 23, 2014

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host:

Contact: Ilya Razenshteyn, ilyaraz@csail.mit.edu

Relevant URL: http://mittheory.wordpress.com/2013/12/25/can-you-tell-if-a-bit-is-random/

Speaker URL: None

Speaker Photo:
None

Reminders to: compalgsem@lists.csail.mit.edu, theory-seminars@lists.csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Ilya Razenshteyn at Tuesday, January 21, 2014 at 10:58 AM.