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:1303.5591 · Physical Review A

Free randomness amplification using bipartite chain correlations

Andrzej Grudka, Karol Horodecki, Michał Horodecki, Paweł Horodecki, Marcin Pawłowski, Ravishankar Ramanathan

Published Sep 22, 2014• 31 citations
arXivHTMLPDF

Abstract

A direct analysis of the task of randomness amplification from Santha-Vazirani sources using the violation of the chained Bell inequality is performed in terms of the convex combination of no-signaling boxes required to simulate quantum violation of the inequality. This analysis is used to find the exact threshold value of the initial randomness parameter from which perfect randomness can be extracted in the asymptotic limit of a large number of measurement settings. As a byproduct, we provide a tool for the analysis of randomness amplification protocols, namely a general characterization of the probability distributions of bits generated by Santha-Vazirani sources, which are shown to be mixtures of specific permutations of Bernoulli distributions with a parameter defined by the source.

DOI
10.1103/physreva.90.032322

Related papers

Amplifying the randomness of weak sources correlated with devices

Wojewódka, H., Fernando G. S. L. Brandão, Grudka, A. +5 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 work, we relax this assumption, and reconsider the original protocol of Colbeck and Renner, Nature Physics 8, 450-454 (2012), on randomness amplification 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 ≤ ε <(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 against this attack for the parameter range 0 ≤ ε < 0.0132. We leave the case of a yet more general attack on the amplification protocol as an interesting open problem.

•Jan 25, 2016•8 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

Randomness Amplification under Minimal Fundamental Assumptions on the Devices

Ravishankar Ramanathan, Fernando G. S. L. Brandão, Karol Horodecki +3 more

Recently, the physically realistic protocol amplifying the randomness of Santha-Vazirani sources producing cryptographically secure random bits was proposed; however, for reasons of practical relevance, the crucial question remained open regarding whether this can be accomplished under the minimal conditions necessary for the task. Namely, is it possible to achieve randomness amplification using only two no-signaling components and in a situation where the violation of a Bell inequality only guarantees that some outcomes of the device for specific inputs exhibit randomness? Here, we solve this question and present a device-independent protocol for randomness amplification of Santha-Vazirani sources using a device consisting of two nonsignaling components. We show that the protocol can amplify any such source that is not fully deterministic into a fully random source while tolerating a constant noise rate and prove the composable security of the protocol against general no-signaling adversaries. Our main innovation is the proof that even the partial randomness certified by the two-party Bell test [a single input-output pair (u^{*}, x^{*}) for which the conditional probability P(x^{*}|u^{*}) is bounded away from 1 for all no-signaling strategies that optimally violate the Bell inequality] can be used for amplification. We introduce the methodology of a partial tomographic procedure on the empirical statistics obtained in the Bell test that ensures that the outputs constitute a linear min-entropy source of randomness. As a technical novelty that may be of independent interest, we prove that the Santha-Vazirani source satisfies an exponential concentration property given by a recently discovered generalized Chernoff bound.

arXiv:1504.06313•Physical Review Letters•Nov 30, 2016•40 citations

Robust amplification of Santha-Vazirani sources with three devices

Piotr Mironowicz, Rodrigo Gallego, Marcin Pawłowski

We demonstrate that amplification of arbitrarily weak randomness is possible using quantum resources. We present a randomness amplification protocol that involves Bell experiments. We find a Bell inequality that can amplify arbitrarily weak randomness and give a detailed analysis of the protocol involving it. Our analysis includes finding a sufficient violation of the Bell inequality as a function of the initial quality of randomness. It has a very important property that for any quality the required violation is strictly lower than possible to obtain using quantum resources. Among other things, this means that the protocol takes a finite amount of time to amplify arbitrarily weak randomness.

arXiv:1301.7722•Physical Review A•Mar 23, 2015•19 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

Robust Device Independent Randomness Amplification

Ravishankar Ramanathan, Fernando G. S. L. Brandão, Andrzej Grudka +3 more

In randomness amplification a slightly random source is used to produce an improved random source. Perhaps surprisingly, a single source of randomness cannot be amplified at all classically. However, the situation is different if one considers correlations allowed by quantum mechanics as an extra resource. Here we present a protocol that amplifies Santha-Vazirani sources arbitrarily close to deterministic into fully random sources. The protocol is device independent, depending only on the observed statistics of the devices and on the validity of the no-signaling principle between different devices. It improves previously-known protocols in two respects. First the protocol is tolerant to noise so that even noisy quantum-mechanical systems give rise to good devices for the protocol. Second it is simpler, being based on the violation of a four-party Bell inequality and on the XOR as a hash function. As a technical tool we prove a new de Finetti theorem where the subsystems are selected from a Santha-Vazirani source.

arXiv:1308.4635•Aug 21, 2013•9 citations
A direct analysis of the task of randomness amplification from Santha-Vazirani sources using the violation of the chained Bell inequality is performed in terms of the convex combination of no-signaling boxes required to simulate quantum violation of the inequality. This analysis is used to find the exact threshold value of the initial randomness parameter from which perfect randomness can be extracted in the asymptotic limit of a large number of measurement settings. As a byproduct, we provide a tool for the analysis of randomness amplification protocols, namely a general characterization of the probability distributions of bits generated by Santha-Vazirani sources, which are shown to be mixtures of specific permutations of Bernoulli distributions with a parameter defined by the source.
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 work, we relax this assumption, and reconsider the original protocol of Colbeck and Renner, Nature Physics 8, 450-454 (2012), on randomness amplification 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 ≤ ε <(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 against this attack for the parameter range 0 ≤ ε < 0.0132. We leave the case of a yet more general attack on the amplification protocol as an interesting open problem.
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.
Recently, the physically realistic protocol amplifying the randomness of Santha-Vazirani sources producing cryptographically secure random bits was proposed; however, for reasons of practical relevance, the crucial question remained open regarding whether this can be accomplished under the minimal conditions necessary for the task. Namely, is it possible to achieve randomness amplification using only two no-signaling components and in a situation where the violation of a Bell inequality only guarantees that some outcomes of the device for specific inputs exhibit randomness? Here, we solve this question and present a device-independent protocol for randomness amplification of Santha-Vazirani sources using a device consisting of two nonsignaling components. We show that the protocol can amplify any such source that is not fully deterministic into a fully random source while tolerating a constant noise rate and prove the composable security of the protocol against general no-signaling adversaries. Our main innovation is the proof that even the partial randomness certified by the two-party Bell test [a single input-output pair (u^{*}, x^{*}) for which the conditional probability P(x^{*}|u^{*}) is bounded away from 1 for all no-signaling strategies that optimally violate the Bell inequality] can be used for amplification. We introduce the methodology of a partial tomographic procedure on the empirical statistics obtained in the Bell test that ensures that the outputs constitute a linear min-entropy source of randomness. As a technical novelty that may be of independent interest, we prove that the Santha-Vazirani source satisfies an exponential concentration property given by a recently discovered generalized Chernoff bound.
We demonstrate that amplification of arbitrarily weak randomness is possible using quantum resources. We present a randomness amplification protocol that involves Bell experiments. We find a Bell inequality that can amplify arbitrarily weak randomness and give a detailed analysis of the protocol involving it. Our analysis includes finding a sufficient violation of the Bell inequality as a function of the initial quality of randomness. It has a very important property that for any quality the required violation is strictly lower than possible to obtain using quantum resources. Among other things, this means that the protocol takes a finite amount of time to amplify arbitrarily weak randomness.
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.
In randomness amplification a slightly random source is used to produce an improved random source. Perhaps surprisingly, a single source of randomness cannot be amplified at all classically. However, the situation is different if one considers correlations allowed by quantum mechanics as an extra resource. Here we present a protocol that amplifies Santha-Vazirani sources arbitrarily close to deterministic into fully random sources. The protocol is device independent, depending only on the observed statistics of the devices and on the validity of the no-signaling principle between different devices. It improves previously-known protocols in two respects. First the protocol is tolerant to noise so that even noisy quantum-mechanical systems give rise to good devices for the protocol. Second it is simpler, being based on the violation of a four-party Bell inequality and on the XOR as a hash function. As a technical tool we prove a new de Finetti theorem where the subsystems are selected from a Santha-Vazirani source.