Robust randomness amplifiers: upper and lower bounds

DOI10.1007/978-3-642-40328-6_33MaRDI QIDQ2851878zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Matthew Coudron, Thomas Vidick, Henry C. Yuen

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.6626, https://authors.library.caltech.edu/65492/

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: A recent sequence of works, initially motivated by the study of the nonlocal properties of entanglement, demonstrate that a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short random seed and the ability to ensure that two black-box devices do not communicate (i.e. are non-signaling). We call protocols achieving such certified amplification of a short random seed randomness amplifiers. We introduce a simple framework in which we initiate the systematic study of the possibilities and limitations of randomness amplifiers. Our main results include a new, improved analysis of a robust randomness amplifier with exponential expansion, as well as the first upper bounds on the maximum expansion achievable by a broad class of randomness amplifiers. In particular, we show that non-adaptive randomness amplifiers that are robust to noise cannot achieve more than doubly exponential expansion. Finally, we show that a wide class of protocols based on the use of the CHSH game can only lead to (singly) exponential expansion if adversarial devices are allowed the full power of non-signaling strategies. Our upper bound results apply to all known non-adaptive randomness amplifier constructions to date.

Recommendations

• Infinite randomness expansion with a constant number of devices
• Private randomness expansion with untrusted devices
• Universal security for randomness expansion from the spot-checking protocol

Cited in

(5)

• Efficient amplification of the security of weak pseudo-random function generators
• Low-End Uniform Hardness versus Randomness Tradeoffs for AM
• Amplification and Derandomization without Slowdown
• Universal security for randomness expansion from the spot-checking protocol
• Increased certification of semi-device independent random numbers using many inputs and more post-processing

This page was built for publication: Robust randomness amplifiers: upper and lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851878)