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:2205.02751 · Quantum

Tilted Hardy paradoxes for device-independent randomness extraction

Shuai Zhao, Ravishankar Ramanathan, Yuan Liu, Paweł Horodecki

Published Sep 15, 2023• 8 citations
arXivHTMLPDF

Abstract

The device-independent paradigm has had spectacular successes in randomness generation, key distribution and self-testing, however most of these results have been obtained under the assumption that parties hold trusted and private random seeds. In efforts to relax the assumption of measurement independence, Hardy's non-locality tests have been proposed as ideal candidates. In this paper, we introduce a family of tilted Hardy paradoxes that allow to self-test general pure two-qubit entangled states, as well as certify up to 1 bit of local randomness. We then use these tilted Hardy tests to obtain an improvement in the generation rate in the state-of-the-art randomness amplification protocols for Santha-Vazirani (SV) sources with arbitrarily limited measurement independence. Our result shows that device-independent randomness amplification is possible for arbitrarily biased SV sources and from almost separable states. Finally, we introduce a family of Hardy tests for maximally entangled states of local dimension 4,8 as the potential candidates for DI randomness extraction to certify up to the maximum possible 2log⁡d bits of global randomness.

DOI
10.22331/q-2023-09-15-1114

Related papers

Semi-device-independent full randomness amplification based on energy bounds

Gabriel Senno, Antonio Acín

Quantum Bell nonlocality allows for the design of protocols that amplify the randomness of public and arbitrarily biased Santha-Vazirani sources, a classically impossible task. Information-theoretical security in these protocols is certified in a device-independent manner, i.e. solely from the observed nonlocal statistics and without any assumption about the inner-workings of the intervening devices. On the other hand, if one is willing to trust on a complete quantum-mechanical description of a protocol's devices, the elementary scheme in which a qubit is alternatively measured in a pair of mutually unbiased bases is, straightforwardly, a protocol for randomness amplification. In this work, we study the unexplored middle ground. We prove that full randomness amplification can be achieved without requiring entanglement or a complete characterization of the intervening quantum states and measurements. Based on the energy-bounded framework introduced in [Van Himbeeck et al., Quantum 1, 33 (2017)], our prepare-and-measure protocol is able to amplify the randomness of any public Santha-Vazirani source, requiring the smallest number of inputs and outcomes possible and being secure against quantum adversaries.

arXiv:2108.09100•Aug 20, 2021•0 citations

Practical No-Signalling proof Randomness Amplification using Hardy paradoxes and its experimental implementation

Ravishankar Ramanathan, Michał Horodecki, Hammad Anwer +6 more

Abstract Device-Independent (DI) security is the gold standard of quantum cryptography, providing information-theoretic security based on the very laws of nature. In its highest form, security is guaranteed against adversaries limited only by the no-superluminal signalling rule of relativity. The task of randomness amplification, to generate secure fully uniform bits starting from weakly random seeds, is of both cryptographic and foundational interest, being important for the generation of cryptographically secure random numbers as well as bringing deep connections to the existence of free-will. DI no-signalling proof protocols for this fundamental task have thus far relied on esoteric proofs of non-locality termed pseudo-telepathy games, complicated multi-party setups or high-dimensional quantum systems, and have remained out of reach of experimental implementation. In this paper, we construct the first practically relevant no-signalling proof DI protocols for randomness amplification based on the simplest proofs of Bell non-locality and illustrate them with an experimental implementation in a quantum optical setup using polarised photons. Technically, we relate the problem to the vast field of Hardy paradoxes, without which it would be impossible to achieve amplification of arbitrarily weak sources in the simplest Bell non-locality scenario consisting of two parties choosing between two binary inputs. Furthermore, we identify a deep connection between proofs of the celebrated Kochen-Specker theorem and Hardy paradoxes that enables us to construct Hardy paradoxes with the non-zero probability taking any value in (0,1]. Our methods enable us, under the fair-sampling assumption of the experiment, to realize up to 25 bits of randomness in 20 hours of experimental data collection from an initial private source of randomness 0.1 away from uniform.

arXiv:1810.11648•Sep 11, 2020•9 citations

No-signaling-proof randomness extraction from public weak sources

Ravishankar Ramanathan, Michał Banacki, Paweł Horodecki

The extraction of randomness from weakly random seeds is a topic of central importance in cryptography. Weak sources of randomness can be considered to be either private or public, where public sources such as the NIST randomness beacon broadcast the random bits once they are generated. The problem of device-independent randomness extraction from weak public sources against no-signalling adversaries has remained open. In this paper, we show protocols for device-independent and one-sided device-independent amplification of randomness from weak public Santha Vazirani (SV) sources that use a finite number of devices and are secure against no-signaling adversaries. Specifically, under the assumption that the device behavior is as prescribed by quantum mechanics the protocols allow for amplification of public $ε$-SV sources for arbitrary initial $ε\in [0,0.5)$. On the other hand, when only the assumption of no-signaling between the components of the device is made, the protocols allow for amplification of a limited set of weak public SV sources.

arXiv:2108.08819•Aug 19, 2021•3 citations

Maximal randomness from partially entangled states

Erik Woodhead, Jędrzej Kaniewski, Boris Bourdoncle +4 more

We investigate how much randomness can be extracted from a generic partially entangled pure state of two qubits in a device-independent setting, where a Bell test is used to certify the correct functioning of the apparatus.For any such state, we first show that two bits of randomness are always attainable both if projective measurements are used to generate the randomness globally or if a nonprojective measurement is used to generate the randomness locally.We then prove that the maximum amount of randomness that can be generated using nonprojective measurements globally is restricted to between approximately 3.58 and 3.96 bits.The upper limit rules out that a bound of four bits potentially obtainable with extremal qubit measurements can be attained.We point out this is a consequence of the fact that nonprojective qubit measurements with four outcomes can only be self-tested to a limited degree in a Bell experiment.

arXiv:1901.06912•Physical Review Research•Nov 13, 2020•37 citations

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

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
The device-independent paradigm has had spectacular successes in randomness generation, key distribution and self-testing, however most of these results have been obtained under the assumption that parties hold trusted and private random seeds. In efforts to relax the assumption of measurement independence, Hardy's non-locality tests have been proposed as ideal candidates. In this paper, we introduce a family of tilted Hardy paradoxes that allow to self-test general pure two-qubit entangled states, as well as certify up to 1 bit of local randomness. We then use these tilted Hardy tests to obtain an improvement in the generation rate in the state-of-the-art randomness amplification protocols for Santha-Vazirani (SV) sources with arbitrarily limited measurement independence. Our result shows that device-independent randomness amplification is possible for arbitrarily biased SV sources and from almost separable states. Finally, we introduce a family of Hardy tests for maximally entangled states of local dimension 4,8 as the potential candidates for DI randomness extraction to certify up to the maximum possible 2log⁡d bits of global randomness.
Quantum Bell nonlocality allows for the design of protocols that amplify the randomness of public and arbitrarily biased Santha-Vazirani sources, a classically impossible task. Information-theoretical security in these protocols is certified in a device-independent manner, i.e. solely from the observed nonlocal statistics and without any assumption about the inner-workings of the intervening devices. On the other hand, if one is willing to trust on a complete quantum-mechanical description of a protocol's devices, the elementary scheme in which a qubit is alternatively measured in a pair of mutually unbiased bases is, straightforwardly, a protocol for randomness amplification. In this work, we study the unexplored middle ground. We prove that full randomness amplification can be achieved without requiring entanglement or a complete characterization of the intervening quantum states and measurements. Based on the energy-bounded framework introduced in [Van Himbeeck et al., Quantum 1, 33 (2017)], our prepare-and-measure protocol is able to amplify the randomness of any public Santha-Vazirani source, requiring the smallest number of inputs and outcomes possible and being secure against quantum adversaries.
Abstract Device-Independent (DI) security is the gold standard of quantum cryptography, providing information-theoretic security based on the very laws of nature. In its highest form, security is guaranteed against adversaries limited only by the no-superluminal signalling rule of relativity. The task of randomness amplification, to generate secure fully uniform bits starting from weakly random seeds, is of both cryptographic and foundational interest, being important for the generation of cryptographically secure random numbers as well as bringing deep connections to the existence of free-will. DI no-signalling proof protocols for this fundamental task have thus far relied on esoteric proofs of non-locality termed pseudo-telepathy games, complicated multi-party setups or high-dimensional quantum systems, and have remained out of reach of experimental implementation. In this paper, we construct the first practically relevant no-signalling proof DI protocols for randomness amplification based on the simplest proofs of Bell non-locality and illustrate them with an experimental implementation in a quantum optical setup using polarised photons. Technically, we relate the problem to the vast field of Hardy paradoxes, without which it would be impossible to achieve amplification of arbitrarily weak sources in the simplest Bell non-locality scenario consisting of two parties choosing between two binary inputs. Furthermore, we identify a deep connection between proofs of the celebrated Kochen-Specker theorem and Hardy paradoxes that enables us to construct Hardy paradoxes with the non-zero probability taking any value in (0,1]. Our methods enable us, under the fair-sampling assumption of the experiment, to realize up to 25 bits of randomness in 20 hours of experimental data collection from an initial private source of randomness 0.1 away from uniform.
The extraction of randomness from weakly random seeds is a topic of central importance in cryptography. Weak sources of randomness can be considered to be either private or public, where public sources such as the NIST randomness beacon broadcast the random bits once they are generated. The problem of device-independent randomness extraction from weak public sources against no-signalling adversaries has remained open. In this paper, we show protocols for device-independent and one-sided device-independent amplification of randomness from weak public Santha Vazirani (SV) sources that use a finite number of devices and are secure against no-signaling adversaries. Specifically, under the assumption that the device behavior is as prescribed by quantum mechanics the protocols allow for amplification of public εεε-SV sources for arbitrary initial ε∈[0,0.5)ε\in [0,0.5)ε∈[0,0.5). On the other hand, when only the assumption of no-signaling between the components of the device is made, the protocols allow for amplification of a limited set of weak public SV sources.
We investigate how much randomness can be extracted from a generic partially entangled pure state of two qubits in a device-independent setting, where a Bell test is used to certify the correct functioning of the apparatus.For any such state, we first show that two bits of randomness are always attainable both if projective measurements are used to generate the randomness globally or if a nonprojective measurement is used to generate the randomness locally.We then prove that the maximum amount of randomness that can be generated using nonprojective measurements globally is restricted to between approximately 3.58 and 3.96 bits.The upper limit rules out that a bound of four bits potentially obtainable with extremal qubit measurements can be attained.We point out this is a consequence of the fact that nonprojective qubit measurements with four outcomes can only be self-tested to a limited degree in a Bell experiment.
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.
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.