Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Trading Isolation for Certifiable Randomness Expansion

Matthew Coudron

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

A source of bits is an important resource in modern cryptography, algorithms and statistics. Can one ever be sure that a random source is truly random, or in the case of cryptography, secure against potential adversaries or eavesdroppers? Recently the study of non-local properties of entanglement has produced an interesting new perspective on this question, which we will refer to broadly as Certifiable Randomness Expansion (CRE). CRE refers generally to a process by which a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short seed and the ability to ensure that two or more black-box devices do not communicate (i.e. are non-signaling). In this work we make progress on a conjecture of [Col09] which proposes a method for indefinite certifiable randomness expansion using a growing number of devices (we actually prove a slight modification of the original conjecture in which we use the CHSH game as a subroutine rather than the GHZ game as originally proposed). The proof requires a technique not used before in the study of randomness expansion, and inspired by the tools developed in [RUV12]. The result also establishes the existence of a protocol for constant factor CRE using a finite number of devices (here the constant factor can be much greater than 1). While much better expansion rates (polynomial, and even exponential) have been achieved with only two devices, our analysis requires techniques not used before in the study of randomness expansion, and represents progress towards a protocol which is provably secure against a quantum eavesdropper who knows the input to the protocol.

Related papers

Robust Randomness Amplifiers: Upper and Lower Bounds

Matthew Coudron, Thomas Vidick, Henry Yuen

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.

arXiv:1305.6626•May 28, 2013•10 citations

Infinite Randomness Expansion and Amplification with a Constant Number of Devices

Matthew Coudron, Henry Yuen

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(-Ω(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.

arXiv:1310.6755•Oct 24, 2013•42 citations

Infinite randomness expansion with a constant number of devices

Matthew Coudron, Henry Yuen

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(--Ω(m1/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.

ACM Symposium on Theory of Computing (STOC)•May 31, 2014•47 citations

Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits

Matthew Coudron, Jalex Stark, Thomas Vidick

The generation of certifiable randomness is the most fundamental information-theoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be verified classically in linear time, and is guaranteed to contain a polynomial number of certified random bits assuming that the device used to generate the output operated using a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with the locality assumption used for randomness certification based on Bell inequality violation and more recent proposals for randomness certification based on computational assumptions. Furthermore, to demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our procedure is inspired by recent work of Bravyi et al. (Science 362(6412):308-311, 2018), who introduced a relational problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic depth. We develop the discovery of Bravyi et al. into a framework for robust randomness expansion. Our results lead to a new proposal for a demonstrated quantum advantage that has some advantages compared to existing proposals. First, our proposal does not rest on any complexity-theoretic conjectures, but relies on the physical assumption that the adversarial device being tested implements a circuit of sub-logarithmic depth. Second, success on our task can be easily verified in classical linear time. Finally, our task is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we are able to allow a small constant additive error in total variation distance between the sampled and ideal distributions.

arXiv:1810.04233•Communications in Mathematical Physics•Feb 1, 2021•36 citations

More Than One-bit Quantum Randomness Certification and Expansion

Amélie Piveteau, Alban Seguinard, Marcus Grünfeld +4 more

One of the striking properties of quantum mechanics is the occurrence of the Bell-type non-locality. They are a fundamental feature of the theory that allows two parties that share an entangled quantum system to observe correlations stronger than possible in classical physics. In addition to their theoretical significance, non-local correlations have practical applications, such as device-independent randomness generation, providing private unpredictable numbers even when obtained using devices delivered by an untrusted vendor. Thus, determining the quantity of certifiable randomness that can be produced using a specific set of non-local correlations is of significant interest. First, we present an experimental realization of recent Bell-type operators designed to provide private random numbers that are secure against adversaries with quantum resources. We use semi-definite programming to give lower bounds on the generated randomness in terms of both min-entropy and von Neumann entropy in a device-independent scenario. Our results demonstrate the first experiment that certifies nearly two bits of randomness from binary measurements of two parties [1], [2]. Apart from single-round certification, we provide an analysis of finite-key protocol for quantum randomness expansion using the Entropy Accumulation Theorem. Second, we present an efficient and practical method for certifying quantum randomness using generalized measurements. Indeed, we have derived a method for self-testing the presence of POVMs. We present the certification of more than one bit of min-entropy from a single POVM on one of the qubits of an entangled state using a variant of the elegant Bell inequality. We also obtain more than one bit of randomness in a prepare and measure scenario of a similar structure with a POVM on a single qubit [3]. We provide numerical simulations to demonstrate the effectiveness of our randomness certification and expansion.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•Jun 23, 2025•0 citations

Security of Semi-Device-Independent Random Number Expansion Protocols

Dandan Li, Qiaoyan Wen, Yukun Wang +2 more

Semi-device-independent random number expansion (SDI-RNE) protocols require some truly random numbers to generate fresh ones, with making no assumptions on the internal working of quantum devices except for the dimension of the Hilbert space. The generated randomness is certified by non-classical correlation in the prepare-and-measure test. Until now, the analytical relations between the amount of the generated randomness and the degree of non-classical correlation, which are crucial for evaluating the security of SDI-RNE protocols, are not clear under both the ideal condition and the practical one. In the paper, first, we give the analytical relation between the above two factors under the ideal condition. As well, we derive the analytical relation under the practical conditions, where devices' behavior is not independent and identical in each round and there exists deviation in estimating the non-classical behavior of devices. Furthermore, we choose a different randomness extractor (i.e., two-universal random function) and give the security proof.

Scientific Reports•Oct 27, 2015•9 citations
A source of bits is an important resource in
modern cryptography, algorithms and statistics. Can one ever be
sure that a random source is truly random, or in the case of
cryptography, secure against potential adversaries or
eavesdroppers? Recently the study of non-local properties of
entanglement has produced an interesting new perspective on this
question, which we will refer to broadly as Certifiable Randomness
Expansion (CRE). CRE refers generally to a process by which a
source of information-theoretically certified randomness can be
constructed based only on two simple assumptions: the prior
existence of a short seed and the ability to ensure that two
or more black-box devices do not communicate (i.e. are
non-signaling). In this work we make progress on a conjecture of
[Col09] which proposes a method for indefinite certifiable
randomness expansion using a growing number of devices (we actually
prove a slight modification of the original conjecture in which we
use the CHSH game as a subroutine rather than the GHZ game as
originally proposed). The proof requires a technique not used
before in the study of randomness expansion, and inspired by the
tools developed in [RUV12]. The result also establishes the
existence of a protocol for constant factor CRE using a finite
number of devices (here the constant factor can be much greater
than 1). While much better expansion rates (polynomial, and even
exponential) have been achieved with only two devices, our analysis
requires techniques not used before in the study of randomness
expansion, and represents progress towards a protocol which is
provably secure against a quantum eavesdropper who knows the input
to the protocol.
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.
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 mmm bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp⁡(−Ω(m1/3))\exp(-Ω(m^{1/3}))exp(−Ω(m1/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 mmm). 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.
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(--Ω(m1/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 generation of certifiable randomness is the most fundamental information-theoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be verified classically in linear time, and is guaranteed to contain a polynomial number of certified random bits assuming that the device used to generate the output operated using a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with the locality assumption used for randomness certification based on Bell inequality violation and more recent proposals for randomness certification based on computational assumptions. Furthermore, to demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our procedure is inspired by recent work of Bravyi et al. (Science 362(6412):308-311, 2018), who introduced a relational problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic depth. We develop the discovery of Bravyi et al. into a framework for robust randomness expansion. Our results lead to a new proposal for a demonstrated quantum advantage that has some advantages compared to existing proposals. First, our proposal does not rest on any complexity-theoretic conjectures, but relies on the physical assumption that the adversarial device being tested implements a circuit of sub-logarithmic depth. Second, success on our task can be easily verified in classical linear time. Finally, our task is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we are able to allow a small constant additive error in total variation distance between the sampled and ideal distributions.
One of the striking properties of quantum mechanics is the occurrence of the Bell-type non-locality. They are a fundamental feature of the theory that allows two parties that share an entangled quantum system to observe correlations stronger than possible in classical physics. In addition to their theoretical significance, non-local correlations have practical applications, such as device-independent randomness generation, providing private unpredictable numbers even when obtained using devices delivered by an untrusted vendor. Thus, determining the quantity of certifiable randomness that can be produced using a specific set of non-local correlations is of significant interest. First, we present an experimental realization of recent Bell-type operators designed to provide private random numbers that are secure against adversaries with quantum resources. We use semi-definite programming to give lower bounds on the generated randomness in terms of both min-entropy and von Neumann entropy in a device-independent scenario. Our results demonstrate the first experiment that certifies nearly two bits of randomness from binary measurements of two parties [1], [2]. Apart from single-round certification, we provide an analysis of finite-key protocol for quantum randomness expansion using the Entropy Accumulation Theorem. Second, we present an efficient and practical method for certifying quantum randomness using generalized measurements. Indeed, we have derived a method for self-testing the presence of POVMs. We present the certification of more than one bit of min-entropy from a single POVM on one of the qubits of an entangled state using a variant of the elegant Bell inequality. We also obtain more than one bit of randomness in a prepare and measure scenario of a similar structure with a POVM on a single qubit [3]. We provide numerical simulations to demonstrate the effectiveness of our randomness certification and expansion.
Semi-device-independent random number expansion (SDI-RNE) protocols require some truly random numbers to generate fresh ones, with making no assumptions on the internal working of quantum devices except for the dimension of the Hilbert space. The generated randomness is certified by non-classical correlation in the prepare-and-measure test. Until now, the analytical relations between the amount of the generated randomness and the degree of non-classical correlation, which are crucial for evaluating the security of SDI-RNE protocols, are not clear under both the ideal condition and the practical one. In the paper, first, we give the analytical relation between the above two factors under the ideal condition. As well, we derive the analytical relation under the practical conditions, where devices' behavior is not independent and identical in each round and there exists deviation in estimating the non-classical behavior of devices. Furthermore, we choose a different randomness extractor (i.e., two-universal random function) and give the security proof.