Matt Coudron: 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 infinite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified 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 infinite randomness amplification 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.