Infinite Randomness Expansion and Amplification with a Constant Number of Devices

Abstract

We present a device-independent randomness expansion protocol, involving only a constant number of non-signaling quantum devices, that achieves \emph{infinite expansion}: starting with $m$ bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is $\exp (-\Omega (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 a long-standing open problem in the area of randomness expansion and device-independence. The analysis of our protocols involves overcoming fundamental challenges in the study of \emph{adaptive} device-independent protocols. Our primary technical contribution is the design and analysis of device-independent protocols which are \emph{Input Secure}; that is, their output is guaranteed to be secure against a quantum eavesdropper, \emph{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.

36 pages; updated references, results unchanged

References in corpus (7)

• Fully device independent quantum key distribution
• Robust Self Testing of the Singlet
• The Bounded Storage Model in The Presence of a Quantum Adversary
• Robust Device-Independent Randomness Amplification with Few Devices
• Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
• Optimal robust quantum self-testing by binary nonlocal XOR games
• Robust Randomness Amplifiers: Upper and Lower Bounds

Cited by in corpus (7)

• Certified randomness in quantum physics
• Simple and tight device-independent security proofs
• Randomness in Quantum Mechanics: Philosophy, Physics and Technology
• Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
• Device-independent randomness generation from several Bell estimators
• Device-independent randomness amplification with a single device
• Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices