Seedless extractors for device-independent quantum cryptography

Cameron Foreman; Lluis Masanes

doi:10.22331/q-2025-03-06-1654

Seedless extractors for device-independent quantum cryptography

Cameron Foreman^1,2 and Lluis Masanes^2,3

¹Quantinuum, Partnership House, Carlisle Place, London SW1P 1BX, United Kingdom
²Department of Computer Science, University College London, United Kingdom
³London Centre for Nanotechnology, University College London, United Kingdom

Published:	2025-03-06, volume 9, page 1654
Editor:	Anna Pappa
Eprint:	arXiv:2403.04713v2
Doi:	https://doi.org/10.22331/q-2025-03-06-1654
Citation:	Quantum 9, 1654 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Device-independent (DI) quantum cryptography aims at providing secure cryptography with minimal trust in, or characterisation of, the underlying quantum devices. A key step in DI protocols is randomness extraction (or privacy amplification), which typically requires a $seed$ of additional bits with sufficient entropy and statistical independence from any bits generated during the protocol. In this work, we propose a method for extraction in DI protocols that does not require a seed and is secure against computationally unbounded quantum adversaries. The core idea is to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. We present a complete security proof in a model where the experiment uses memoryless measurement devices acting on an arbitrary joint (across all rounds) state. Our results mark a first step in this alternative, seedless, approach to extraction in DI protocols.

Popular summary

Device-independent (DI) quantum cryptography is a leading approach for cryptographic systems based on quantum mechanics, as it allows security to be proven with minimal trust in, or characterization of, the physical implementation. This security is achieved by exploiting quantum non-locality, that is, correlations that violate Bell inequalities and cannot be explained by any local causal model. DI protocols have been developed for secure key distribution, randomness generation, and much more.

A key step in many DI protocols is randomness extraction (or privacy amplification), which involves distilling a near-perfectly unpredictably output from the raw outcomes produced by the quantum hardware, in the presence of an adversary. Traditionally, this requires a \textit{seed} of bits that must be statistically independent of the hardware and sufficiently unpredictably from the adversary's perspective, which can be a significant practical challenge.

In this work, we show that randomness extraction in DI quantum cryptography can be achieved using a deterministic algorithm (i.e., without a seed), while maintaining security against computationally unbounded quantum adversaries. The intuition behind our results is that the violation of Bell inequalities guarantees both a lower bound on outcome unpredictability and certain statistical independence between outcomes from different rounds, which together allows us to eliminate the need for additional randomness in this step.

This paper marks the first step in this alternative approach to extraction in DI protocols. From a theoretical standpoint, we introduce a new class of imperfectly unpredictable sources that can be both deterministically extracted and generated by realizable experimental processes. From a practical perspective, future developments using our method may enable DI protocols with fewer assumptions (and thus fewer opportunities for side-channel attacks) and improved efficiency.

► BibTeX data

@article{Foreman2025seedlessextractors,
  doi = {10.22331/q-2025-03-06-1654},
  url = {https://doi.org/10.22331/q-2025-03-06-1654},
  title = {Seedless extractors for device-independent quantum cryptography},
  author = {Foreman, Cameron and Masanes, Lluis},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1654},
  month = mar,
  year = {2025}
}

► References

[1] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. Device-independent security of quantum cryptography against collective attacks. Physical Review Letters, 98 (23): 230501, 2007. https://doi.org/10.1103/PhysRevLett.98.230501.
https://doi.org/10.1103/PhysRevLett.98.230501

[2] Stefano Pironio, Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, and Valerio Scarani. Device-independent quantum key distribution secure against collective attacks. New Journal of Physics, 11 (4): 045021, 2009. https://doi.org/10.1088/1367-2630/11/4/045021.
https://doi.org/10.1088/1367-2630/11/4/045021

[3] John S Bell. On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1 (3): 195, 1964.

[4] Dominic Mayers and Andrew Yao. Quantum cryptography with imperfect apparatus. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 503–509. IEEE, 1998. https://doi.org/10.1109/SFCS.1998.743501.
https://doi.org/10.1109/SFCS.1998.743501

[5] Renato Renner. Security of quantum key distribution. International Journal of Quantum Information, 6 (01): 1–127, 2008. https://doi.org/10.1142/S0219749908003256.
https://doi.org/10.1142/S0219749908003256

[6] Umesh Vazirani and Thomas Vidick. Fully device independent quantum key distribution. Communications of the ACM, 62 (4): 133–133, 2019. https://doi.org/10.1145/3310974.
https://doi.org/10.1145/3310974

[7] David P Nadlinger, Peter Drmota, Bethan C Nichol, Gabriel Araneda, Dougal Main, Raghavendra Srinivas, David M Lucas, Christopher J Ballance, Kirill Ivanov, Ernest Y-Z Tan, et al. Experimental quantum key distribution certified by Bell's theorem. Nature, 607 (7920): 682–686, 2022. https://doi.org/10.1038/s41586-022-04941-5.
https://doi.org/10.1038/s41586-022-04941-5

[8] Víctor Zapatero, Tim van Leent, Rotem Arnon-Friedman, Wen-Zhao Liu, Qiang Zhang, Harald Weinfurter, and Marcos Curty. Advances in device-independent quantum key distribution. npj Quantum Information, 9 (1): 10, 2023. https://doi.org/10.1038/s41534-023-00684-x.
https://doi.org/10.1038/s41534-023-00684-x

[9] Roger Colbeck and Adrian Kent. Private randomness expansion with untrusted devices. Journal of Physics A: Mathematical and Theoretical, 44 (9): 095305, 2011. https://doi.org/10.1088/1751-8113/44/9/095305.
https://doi.org/10.1088/1751-8113/44/9/095305

[10] Antonio Acín and Lluis Masanes. Certified randomness in quantum physics. Nature, 540 (7632): 213–219, 2016. https://doi.org/10.1038/nature20119.
https://doi.org/10.1038/nature20119

[11] Roger Colbeck and Renato Renner. Free randomness can be amplified. Nature Physics, 8 (6): 450–453, 2012. https://doi.org/10.1038/nphys2300.
https://doi.org/10.1038/nphys2300

[12] Alexandru Gheorghiu, Elham Kashefi, and Petros Wallden. Robustness and device independence of verifiable blind quantum computing. New Journal of Physics, 17 (8): 083040, 2015. https://doi.org/10.1088/1367-2630/17/8/083040.
https://doi.org/10.1088/1367-2630/17/8/083040

[13] Srijita Kundu and Ernest Y-Z Tan. Device-independent uncloneable encryption. Quantum, 9: 1582, 2025. https://doi.org/10.22331/q-2025-01-08-1582.
https://doi.org/10.22331/q-2025-01-08-1582

[14] Anne Broadbent and Peter Yuen. Device-independent oblivious transfer from the bounded-quantum-storage-model and computational assumptions. New Journal of Physics, 25 (5): 053019, 2023. https://doi.org/10.1088/1367-2630/accf32.
https://doi.org/10.1088/1367-2630/accf32

[15] Rotem Arnon-Friedman, Christopher Portmann, and Volkher B. Scholz. Quantum-Proof Multi-Source Randomness Extractors in the Markov Model. In Anne Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:34, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-019-4. https://doi.org/10.4230/LIPIcs.TQC.2016.2.
https://doi.org/10.4230/LIPIcs.TQC.2016.2

[16] Marshall Ball, Oded Goldreich, and Tal Malkin. Randomness extraction from somewhat dependent sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.12.
https://doi.org/10.4230/LIPIcs.ITCS.2022.12

[17] Xin Li. Two source extractors for asymptotically optimal entropy, and (many) more. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1271–1281. IEEE, 2023. https://doi.org/10.1109/FOCS57990.2023.00075.
https://doi.org/10.1109/FOCS57990.2023.00075

[18] Xiongfeng Ma, Feihu Xu, He Xu, Xiaoqing Tan, Bing Qi, and Hoi-Kwong Lo. Postprocessing for quantum random-number generators: Entropy evaluation and randomness extraction. Physical Review A, 87 (6): 062327, 2013. https://doi.org/10.1103/PhysRevA.87.062327.
https://doi.org/10.1103/PhysRevA.87.062327

[19] Cameron Foreman, Richie Yeung, Alec Edgington, and Florian J Curchod. Cryptomite: A versatile and user-friendly library of randomness extractors. Quantum, 9: 1584, 2025. https://doi.org/10.22331/q-2025-01-08-1584.
https://doi.org/10.22331/q-2025-01-08-1584

[20] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23 (15): 880, 1969. https://doi.org/10.1103/PhysRevLett.23.880.
https://doi.org/10.1103/PhysRevLett.23.880

[21] Yukun Wang, Xingyao Wu, and Valerio Scarani. All the self-testings of the singlet for two binary measurements. New Journal of Physics, 18 (2): 025021, 2016. https://doi.org/10.1088/1367-2630/18/2/025021.
https://doi.org/10.1088/1367-2630/18/2/025021

[22] Miklos Santha and Umesh V Vazirani. Generating quasi-random sequences from semi-random sources. Journal of computer and system sciences, 33 (1): 75–87, 1986. https://doi.org/10.1016/0022-0000(86)90044-9.
https://doi.org/10.1016/0022-0000(86)90044-9

[23] John Von Neumann. Various techniques used in connection with random digits. John von Neumann, Collected Works, 5: 768–770, 1963.

[24] Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28 (4): 415–440, 2008. https://doi.org/10.1007/s00493-008-2259-3.
https://doi.org/10.1007/s00493-008-2259-3

[25] Ariel Gabizon, Ran Raz, and Ronen Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM Journal on Computing, 36 (4): 1072–1094, 2006. https://doi.org/10.1137/S0097539705447049.
https://doi.org/10.1137/S0097539705447049

[26] Jesse Kamp, Anup Rao, Salil Vadhan, and David Zuckerman. Deterministic extractors for small-space sources. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pages 691–700, 2006. https://doi.org/10.1145/1132516.1132613.
https://doi.org/10.1145/1132516.1132613

[27] Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 168–177. IEEE, 2016. https://doi.org/10.1109/FOCS.2016.26.
https://doi.org/10.1109/FOCS.2016.26

[28] Eshan Chattopadhyay and Xin Li. Extractors for sumset sources. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pages 299–311, 2016. https://doi.org/10.1145/2897518.2897643.
https://doi.org/10.1145/2897518.2897643

[29] Salman Beigi, Andrej Bogdanov, Omid Etesami, and Siyao Guo. Optimal deterministic extractors for generalized santha-vazirani sources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.30.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.30

[30] Eshan Chattopadhyay. Recent advances in randomness extraction. Entropy, 24 (7): 880, 2022. https://doi.org/10.3390/e24070880.
https://doi.org/10.3390/e24070880

[31] Harry Buhrman, Richard Cleve, Serge Massar, and Ronald De Wolf. Nonlocality and communication complexity. Reviews of modern physics, 82 (1): 665, 2010. https://doi.org/10.1103/RevModPhys.82.665.
https://doi.org/10.1103/RevModPhys.82.665

[32] Lluis Masanes. Universally composable privacy amplification from causality constraints. Physical Review Letters, 102 (14): 140501, 2009. https://doi.org/10.1103/PhysRevLett.102.140501.
https://doi.org/10.1103/PhysRevLett.102.140501

[33] Rodrigo Gallego, Lluis Masanes, Gonzalo De La Torre, Chirag Dhara, Leandro Aolita, and Antonio Acín. Full randomness from arbitrarily deterministic events. Nature Communications, 4 (1): 2654, 2013. https://doi.org/10.1038/ncomms3654.
https://doi.org/10.1038/ncomms3654

[34] Lewis Wooltorton, Peter Brown, and Roger Colbeck. Device-independent quantum key distribution with arbitrarily small nonlocality. Physical Review Letters, 132 (21): 210802, 2024. https://doi.org/10.1103/PhysRevLett.132.210802.
https://doi.org/10.1103/PhysRevLett.132.210802

[35] Máté Farkas. Unbounded device-independent quantum key rates from arbitrarily small nonlocality. Physical Review Letters, 132 (21): 210803, 2024. https://doi.org/10.1103/PhysRevLett.132.210803.
https://doi.org/10.1103/PhysRevLett.132.210803

[36] Ravishankar Ramanathan, Fernando GSL Brandão, Karol Horodecki, Michał Horodecki, Paweł Horodecki, and Hanna Wojewódka. Randomness amplification under minimal fundamental assumptions on the devices. Physical Review Letters, 117 (23): 230501, 2016. https://doi.org/10.1103/PhysRevLett.117.230501.
https://doi.org/10.1103/PhysRevLett.117.230501

[37] Ravishankar Ramanathan, Michał Horodecki, Hammad Anwer, Stefano Pironio, Karol Horodecki, Marcus Grünfeld, Sadiq Muhammad, Mohamed Bourennane, and Paweł Horodecki. Practical no-signalling proof randomness amplification using Hardy paradoxes and its experimental implementation. arXiv preprint arXiv:1810.11648, 2018. https://doi.org/10.48550/arXiv.1810.11648.
https://doi.org/10.48550/arXiv.1810.11648
arXiv:1810.11648

[38] Max Kessler and Rotem Arnon-Friedman. Device-independent randomness amplification and privatization. IEEE Journal on Selected Areas in Information Theory, 1 (2): 568–584, 2020. https://doi.org/10.1109/JSAIT.2020.3012498.
https://doi.org/10.1109/JSAIT.2020.3012498

[39] Ravishankar Ramanathan, Michał Banacki, and Paweł Horodecki. No-signaling-proof randomness extraction from public weak sources. arXiv preprint arXiv:2108.08819, 2021. https://doi.org/10.48550/arXiv.2108.08819.
https://doi.org/10.48550/arXiv.2108.08819
arXiv:2108.08819

[40] Cameron Foreman, Sherilyn Wright, Alec Edgington, Mario Berta, and Florian J Curchod. Practical randomness amplification and privatisation with implementations on quantum computers. Quantum, 7: 969, 2023. https://doi.org/10.22331/q-2023-03-30-969.
https://doi.org/10.22331/q-2023-03-30-969

[41] Lluis Masanes, Stefano Pironio, and Antonio Acín. Secure device-independent quantum key distribution with causally independent measurement devices. Nature Communications, 2 (1): 238, 2011. https://doi.org/10.1038/ncomms1244.
https://doi.org/10.1038/ncomms1244

[42] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 136–145. IEEE, 2001. https://doi.org/10.1109/SFCS.2001.959888.
https://doi.org/10.1109/SFCS.2001.959888

[43] Israel Gelfand and Mark Neumark. On the imbedding of normed rings into the ring of operators in Hilbert space. Matematicheskii Sbornik, 12 (2): 197–217, 1943.

[44] Cameron Foreman and Lluis Masanes. In preparation.

[45] Le Phuc Thinh, Lana Sheridan, and Valerio Scarani. Bell tests with min-entropy sources. Physical Review A—Atomic, Molecular, and Optical Physics, 87 (6): 062121, 2013. https://doi.org/10.1103/PhysRevA.87.062121.
https://doi.org/10.1103/PhysRevA.87.062121

[46] Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10 (7): 073013, 2008. https://doi.org/10.1088/1367-2630/10/7/073013.
https://doi.org/10.1088/1367-2630/10/7/073013

[47] Lluis Masanes, Renato Renner, Matthias Christandl, Andreas Winter, and Jonathan Barrett. Full security of quantum key distribution from no-signaling constraints. IEEE Transactions on Information Theory, 60 (8): 4973–4986, 2014. https://doi.org/10.1109/TIT.2014.2329417.
https://doi.org/10.1109/TIT.2014.2329417

[48] Rutvij Bhavsar, Sammy Ragy, and Roger Colbeck. Improved device-independent randomness expansion rates using two sided randomness. New Journal of Physics, 25 (9): 093035, 2023. https://doi.org/10.1088/1367-2630/acf393.
https://doi.org/10.1088/1367-2630/acf393

Cited by

[1] Minming Geng, "Advances of Quantum Key Distribution and Network Nonlocality", Entropy 27 9, 950 (2025).

[2] Jaskaran Singh, Cameron Foreman, Kishor Bharti, and Adán Cabello, "Local contextuality-based self-tests are sufficient for randomness expansion secure against quantum adversaries", arXiv:2409.20082, (2024).

[3] Dipak K. Rabari, Yogesh K. Meghrajani, and Laxmi S. Desai, "Universal share based quantum multi secret image sharing scheme", arXiv:2509.12979, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-16 22:12:58) and SAO/NASA ADS (last updated successfully 2026-07-16 22:12:59). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.