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

arXiv:1402.0974 · Physical Review A

Device-independent randomness extraction from an arbitrarily weak min-entropy source

Jan Bouda, Marcin Pawłowski, Matej Pivoluska, Martin Plesch

Published Sep 12, 2014• 26 citations
arXivHTMLPDF

Abstract

Expansion and amplification of weak randomness play a crucial role in many security protocols. Using quantum devices, such procedure is possible even without trusting the devices used, by utilizing correlations between outcomes of parts of the devices. We show here how to extract random bits with an arbitrarily low bias from single arbitrarily weak min-entropy block source in a device independent setting. To do this we use Mermin devices that exhibit superclassical correlations. The number of devices used scales polynomially in the length of the random sequence $n$. Our protocol is robust; it can tolerate devices that malfunction with probability decreasing polynomially in $n$ at the cost of minor increase in the number of devices used.

DOI
10.1103/physreva.90.032313

Related papers

Device-independent Randomness Extraction for Arbitrarily Weak Min-entropy Source

Jan Bouda, Marcin Pawłowski, Matej Pivoluska +1 more

In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.

Leibniz international proceedings in informatics•Jan 1, 2014•0 citations

Device-independent randomness extraction for arbitrarily weak min-entropy source

Jan Bouda, Marcin Pawłowski, Matej Pivoluska +1 more

In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Oct 13, 2014•6 citations

Finite Device-Independent Extraction of a Block Min-Entropy Source against Quantum Adversaries

Ravishankar Ramanathan

The extraction of randomness from weakly random seeds is a problem of central importance with multiple applications. In the device-independent setting, this problem of quantum randomness amplification has been mainly restricted to specific weak sources of Santha-Vazirani type, while extraction from the general min-entropy sources has required a large number of separated devices which is impractical. In this paper, we present a device-independent protocol for amplification of a single min-entropy source (consisting of two blocks of sufficiently high min-entropy) using a device consisting of two spatially separated components and show a proof of its security against general quantum adversaries.

arXiv:2304.09643•Apr 19, 2023•0 citations

Amplifying the Randomness of Weak Sources Correlated With Devices

Hanna Wojewódka–Ściążko, Fernando G. S. L. Brandão, Andrzej Grudka +6 more

The problem of device-independent randomness amplification against no-signaling adversaries has so far been studied under the assumption that the weak source of randomness is uncorrelated with the (quantum) devices used in the amplification procedure. In this paper, we relax this assumption, and reconsider the original protocol of Colbeck and Renner using a Santha-Vazirani (SV) source. To do so, we introduce an SV-like condition for devices, namely that any string of SV source bits remains weakly random conditioned upon any other bit string from the same SV source and the outputs obtained when this further string is input into the devices. Assuming this condition, we show that a quantum device using a singlet state to violate the chained Bell inequalities leads to full randomness in the asymptotic scenario of a large number of settings, for a restricted set of SV sources (with$0 \leq \varepsilon < (2^{(1/12)} - 1)/(2(2^{(1/12)} + 1)) \approx 0.0144$). We also study a device-independent protocol that allows for correlations between the sequence of boxes used in the protocol and the SV source bits used to choose the particular box from whose output the randomness is obtained. Assuming the SV-like condition for devices, we show that the honest parties can achieve amplification of the weak source, for the parameter range$0 \leq \varepsilon <0.0132$, against a class of attacks given as a mixture of product box sequences, made of extremal no-signaling boxes, with additional symmetry conditions. Composable security proof against this class of attacks is provided.

arXiv:1601.06455•IEEE Transactions on Information Theory•Aug 10, 2017•8 citations

Device-Independent Randomness Amplification and Privatization

Max Kessler, Rotem Arnon-Friedman

Secret and perfect randomness is an essential resource in cryptography. Yet, it is not even clear that such exists. It is well known that the tools of classical computer science do not allow us to create secret and perfect randomness from a single weak public source. Quantum physics, on the other hand, allows for such a process, even in the most paranoid cryptographic sense termed “device-independent quantum cryptography”. We propose and prove the security of a new device-independent protocol that takes any single public Santha-Vazirani source as input and creates a secret close to uniform string in the presence of a quantum adversary. Our work is the first to achieve randomness amplification with all the following properties: (1) amplification and “privatization” of a public Santha-Vazirani source with arbitrary bias (2) the use of a device with only two components (3) non-vanishing extraction rate and (4) maximal noise tolerance. In particular, this implies that our protocol is the first protocol that can possibly be implemented with reachable parameters. We achieve these by combining three new tools: a particular family of Bell inequalities, a proof technique to lower bound entropy in the device-independent setting, and a framework for quantum-proof multi-source extractors.

arXiv:1705.04148•IEEE Journal on Selected Areas in Information Theory•Jul 31, 2020•61 citations

Deterministic randomness extraction for quantum random number generation with partial trust

Pablo Tikas Pueyo, Tomás Fernández Martos, Gabriel Senno

It is a well-known fact in classical information theory that no deterministic procedure can extract close-to-ideal randomness from an arbitrary entropy source. On the other hand, if additional knowledge about the source is available -- e.g., that it is a sequence of independent Bernoulli trials -- then deterministic extractors do exist. For quantum entropy sources, where in addition to classical random variables we consider quantum side information, the use of extra knowledge about their structure was pioneered in a recent publication [C. Foreman and L. Masanes, Quantum 9, 1654 (2025)]. In that work, the authors provide deterministic extractors for device-independent randomness generation with memoryless devices achieving a sufficiently high CHSH score. In this work, we port their construction to the prepare-and-measure scenario. Specifically, we prove that the considered functions are also extractors for memoryless devices in settings with partial trust, either in the state preparation or in the measurement, as well as in a semi-device-independent setting under an overlap assumption on the prepared quantum states. Within this last setting, we simulate the resulting randomness generation protocol on a novel and experimentally relevant family of behaviors, observing positive key rates already for $7\times 10^3$ rounds.

quant-pharXiv:2512.08900•Dec 10, 2025•0 citations
Expansion and amplification of weak randomness play a crucial role in many security protocols. Using quantum devices, such procedure is possible even without trusting the devices used, by utilizing correlations between outcomes of parts of the devices. We show here how to extract random bits with an arbitrarily low bias from single arbitrarily weak min-entropy block source in a device independent setting. To do this we use Mermin devices that exhibit superclassical correlations. The number of devices used scales polynomially in the length of the random sequence nnn. Our protocol is robust; it can tolerate devices that malfunction with probability decreasing polynomially in nnn at the cost of minor increase in the number of devices used.
In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.
In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.
The extraction of randomness from weakly random seeds is a problem of central importance with multiple applications. In the device-independent setting, this problem of quantum randomness amplification has been mainly restricted to specific weak sources of Santha-Vazirani type, while extraction from the general min-entropy sources has required a large number of separated devices which is impractical. In this paper, we present a device-independent protocol for amplification of a single min-entropy source (consisting of two blocks of sufficiently high min-entropy) using a device consisting of two spatially separated components and show a proof of its security against general quantum adversaries.
The problem of device-independent randomness amplification against no-signaling adversaries has so far been studied under the assumption that the weak source of randomness is uncorrelated with the (quantum) devices used in the amplification procedure. In this paper, we relax this assumption, and reconsider the original protocol of Colbeck and Renner using a Santha-Vazirani (SV) source. To do so, we introduce an SV-like condition for devices, namely that any string of SV source bits remains weakly random conditioned upon any other bit string from the same SV source and the outputs obtained when this further string is input into the devices. Assuming this condition, we show that a quantum device using a singlet state to violate the chained Bell inequalities leads to full randomness in the asymptotic scenario of a large number of settings, for a restricted set of SV sources (with0≤ε<(2(1/12)−1)/(2(2(1/12)+1))≈0.01440 \leq \varepsilon < (2^{(1/12)} - 1)/(2(2^{(1/12)} + 1)) \approx 0.01440≤ε<(2(1/12)−1)/(2(2(1/12)+1))≈0.0144). We also study a device-independent protocol that allows for correlations between the sequence of boxes used in the protocol and the SV source bits used to choose the particular box from whose output the randomness is obtained. Assuming the SV-like condition for devices, we show that the honest parties can achieve amplification of the weak source, for the parameter range0≤ε<0.01320 \leq \varepsilon <0.01320≤ε<0.0132, against a class of attacks given as a mixture of product box sequences, made of extremal no-signaling boxes, with additional symmetry conditions. Composable security proof against this class of attacks is provided.
Secret and perfect randomness is an essential resource in cryptography. Yet, it is not even clear that such exists. It is well known that the tools of classical computer science do not allow us to create secret and perfect randomness from a single weak public source. Quantum physics, on the other hand, allows for such a process, even in the most paranoid cryptographic sense termed “device-independent quantum cryptography”. We propose and prove the security of a new device-independent protocol that takes any single public Santha-Vazirani source as input and creates a secret close to uniform string in the presence of a quantum adversary. Our work is the first to achieve randomness amplification with all the following properties: (1) amplification and “privatization” of a public Santha-Vazirani source with arbitrary bias (2) the use of a device with only two components (3) non-vanishing extraction rate and (4) maximal noise tolerance. In particular, this implies that our protocol is the first protocol that can possibly be implemented with reachable parameters. We achieve these by combining three new tools: a particular family of Bell inequalities, a proof technique to lower bound entropy in the device-independent setting, and a framework for quantum-proof multi-source extractors.
It is a well-known fact in classical information theory that no deterministic procedure can extract close-to-ideal randomness from an arbitrary entropy source. On the other hand, if additional knowledge about the source is available -- e.g., that it is a sequence of independent Bernoulli trials -- then deterministic extractors do exist. For quantum entropy sources, where in addition to classical random variables we consider quantum side information, the use of extra knowledge about their structure was pioneered in a recent publication [C. Foreman and L. Masanes, Quantum 9, 1654 (2025)]. In that work, the authors provide deterministic extractors for device-independent randomness generation with memoryless devices achieving a sufficiently high CHSH score. In this work, we port their construction to the prepare-and-measure scenario. Specifically, we prove that the considered functions are also extractors for memoryless devices in settings with partial trust, either in the state preparation or in the measurement, as well as in a semi-device-independent setting under an overlap assumption on the prepared quantum states. Within this last setting, we simulate the resulting randomness generation protocol on a novel and experimentally relevant family of behaviors, observing positive key rates already for 7×1037\times 10^37×103 rounds.