Security and composability of randomness expansion from Bell inequalities
Open accessAbstract
The nonlocal behavior of quantum mechanics can be used to generate guaranteed fresh randomness from an untrusted device that consists of two nonsignalling components; since the generation process requires some initial fresh randomness to act as a catalyst, one also speaks of randomness expansion. R. Colbeck and A. Kent [J. Phys. A 44, 095305 (2011)] proposed the first method for generating randomness from untrusted devices, but without providing a rigorous analysis. This was addressed subsequently by S. Pironio et al. [Nature (London) 464, 1021 (2010)], who aimed at deriving a lower bound on the min-entropy of the data extracted from an untrusted device based only on the observed nonlocal behavior of the device. Although that article succeeded in developing important tools for reaching the stated goal, the proof itself contained a bug, and the given formal claim on the guaranteed amount of min-entropy needs to be revisited. In this paper we build on the tools provided by Pironio et al. and obtain a meaningful lower bound on the min-entropy of the data produced by an untrusted device based on the observed nonlocal behavior of the device. Our main result confirms the essence of the (improperly formulated) claims of Pironio et al. and puts them on solid ground. We also address the question of composability and show that different untrusted devices can be composed in an alternating manner under the assumption that they are not entangled. This enables superpolynomial randomness expansion based on two untrusted yet unentangled devices.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
On the basis of the CHSH inequality, Fehr et al. and Pironio et al. proposed self-testing randomness expansion protocols against classical adversaries.
“On the basis of the Clauser -Horne -Shimony -Holt (CHSH) inequality, 56 Fehr et al. 57 and Pironio et al. 58 proposed self-testing randomness expansion protocols against classical adversaries.”
From Quantum random number generation (2016) · cites this paper as [57]
The paper’s “Classical side information” section addresses an adversary holding classical information about the device, supporting that part of the claim. But Section III says readers may think of CHSH while its results hold generally, and “Concurrent and related work” explicitly says its scheme holds for any Bell inequality. Describing Fehr et al.’s protocol as based specifically on CHSH is therefore too narrow. (LLM, conf=0.88)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654 · see citing works
On the Einstein Podolsky Rosen paradox
Bell, J. S. (1964) · Physics Physique Fizika · doi:10.1103/physicsphysiquefizika.1.195 · Cited by 12,252 · see citing works
Proposed Experiment to Test Local Hidden-Variable Theories
Clauser, J. F., Horne, M. A., Shimony, A., & Holt, R. A. (1969) · Physical Review Letters · doi:10.1103/physrevlett.23.880 · Cited by 7,573 · see citing works
Random numbers certified by Bell’s theorem
Pironio, S., Acín, A., Massar, S., de la Giroday, A. B., Matsukevich, D. N., Maunz, P., Olmschenk, S., Hayes, D., Luo, L., Manning, T. A., et al. (2010) · Nature · doi:10.1038/nature09008 · Cited by 1,420 · see citing works
SECURITY OF QUANTUM KEY DISTRIBUTION
Renner, R. (2008) · International Journal of Quantum Information · doi:10.1142/s0219749908003256 · Cited by 1,160 · see citing works
A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
Navascués, M., Pironio, S., & Acín, A. (2008) · New Journal of Physics · doi:10.1088/1367-2630/10/7/073013 · Cited by 702 · see citing works
The Operational Meaning of Min- and Max-Entropy
König, R., Renner, R., & Schaffner, C. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2025545 · Cited by 645 · see citing works
Self-citationBounding the Set of Quantum Correlations
Navascués, M., Pironio, S., & Acín, A. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.010401 · Cited by 536 · see citing works
Algorithms and Complexity: New Directions and Recent Results
Traub, J. F. (1976) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 419 · see citing works
Private randomness expansion with untrusted devices
Colbeck, R., & Kent, A. (2011) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/44/9/095305 · Cited by 376 · see citing works
Quantum And Relativistic Protocols For Secure Multi-Party ComputationPreprint
Colbeck, R. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0911.3814 · Cited by 335 · see citing works
Randomness versus Nonlocality and Entanglement
Acín, A., Massar, S., & Pironio, S. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.100402 · Cited by 324 · see citing works
Memory Attacks on Device-Independent Quantum Cryptography
Barrett, J., Colbeck, R., & Kent, A. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.010503 · Cited by 174 · see citing works
Security of practical private randomness generation
Pironio, S., & Massar, S. (2013) · Physical Review A · doi:10.1103/physreva.87.012336 · Cited by 169 · see citing works
Trevisan's Extractor in the Presence of Quantum Side Information
De, A., Portmann, C., Vidick, T., & Renner, R. (2012) · SIAM Journal on Computing · doi:10.1137/100813683 · Cited by 161 · see citing works
Vazirani, U. V., & Vidick, T. (2012) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2011.0336 · Cited by 42 · see citing works
Certifiable Quantum Dice - Or, testable exponential randomness expansionPreprint
Vazirani, U. V., & Vidick, T. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.6054 · Cited by 33 · see citing works
Flagged first, then by citations
Research works printed but not linked: 3
- J. Bell, Physics 1, 195 (1964).
- R. Colbeck, Ph.D. thesis, University of Cambridge, 2009.
- R. Renner, Ph.D. thesis, ETH Zürich, 2005.
Cited by
Sorted by citations
Detection-Loophole-Free Test of Quantum Nonlocality, and Applications
Christensen, B. G., McCusker, K. T., Altepeter, J. B., Calkins, B., Gerrits, T., Lita, A. E., Miller, A., Shalm, L. K., Zhang, Y., Nam, S. W., et al. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.130406 · Cited by 477 · see citing works
Quantum random number generation
Ma, X., Yuan, X., Cao, Z., Qi, B., & Zhang, Z. (2016) · npj Quantum Information · doi:10.1038/npjqi.2016.21 · Cited by 445 · see citing works
Full randomness from arbitrarily deterministic events
Gallego, R., Masanes, L., De La Torre, G., Dhara, C., Aolita, L., & Acín, A. (2013) · Nature Communications · doi:10.1038/ncomms3654 · Cited by 186 · see citing works
Security of practical private randomness generation
Pironio, S., & Massar, S. (2013) · Physical Review A · doi:10.1103/physreva.87.012336 · Cited by 169 · see citing works
“y, the problem lies with Eq. (3) and Eq. (A.9) of the Supplementary Information of [14] and with the final steps leading to these equations. 2Note that previous versions of these results (see [25] and [26]) claimed security against quantum side information, but both proofs were incorrect. 3 prevented to communicate wit…”
BackgroundMethodInfluentialMannalath, V., Mishra, S., & Pathak, A. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04175-y · Cited by 125 · see citing works
“Many interesting experiments on the development of such devices have already been reported in the last decade [56, 57, 58, 59, 60, 61, 62].”
BackgroundCertifiable quantum dice: or, true random number generation secure against quantum adversaries
Vazirani, U., & Vidick, T. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213984 · Cited by 80 · see citing works
“Two concurrent and independent papers, the first by Fehr, Gelles and Schaffner [12] and the second by Pironio and Massar [22], consider the problem of randomness expansion in the presence of classical adversaries.”
Background
- Authors
- Fehr, S., Gelles, R., & Schaffner, C.
- Affiliations
- Centrum Wiskunde & Informatica (NL)
- University of California, Los Angeles (US)
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2013-01-30
- Volume
- 87
- Issue
- 1
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2093419514
- Cited by
- 104
- References
- 17
- Citations by year
- 2025: 2 · 2024: 4 · 2023: 5 · 2021: 8 · 2020: 9 · 2019: 12 · 2018: 8 · 2017: 5 · 2016: 7 · 2015: 12 · 2014: 12 · 2013: 15 · 2012: 3
- FWCI
- 16.93
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Physical Review A (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands (submittedVersion, other-oa)
- Data Archiving and Networked Services (DANS) (submittedVersion, other-oa)
- UvA-DARE (University of Amsterdam) (submittedVersion, cc-by)
- arXiv (Cornell University)
- Funders
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Keywords
- Bell inequalities, min-entropy, untrusted devices, nonlocality, composability, device-independent randomness generation, entanglement
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
