Quantum-Proof Randomness Extractors via Operator Space Theory
Open accessThe DOI matches its Crossref record; 54 of the 57 references it cites were found in a registry or an index, and 3 are not checked yet.
Abstract
Quantum-proof randomness extractors are an important building block for classical and quantum cryptography as well as device independent randomness amplification and expansion. Furthermore, they are also a useful tool in quantum Shannon theory. It is known that some extractor constructions are quantum-proof whereas others are provably not [Gavinsky et al., STOC'07]. We argue that the theory of operator spaces offers a natural framework for studying to what extent extractors are secure against quantum adversaries: we first phrase the definition of extractors as a bounded norm condition between normed spaces, and then show that the presence of quantum adversaries corresponds to a completely bounded norm condition between operator spaces. From this, we show that very high min-entropy extractors as well as extractors with small output are always (approximately) quantum-proof. We also study a generalization of extractors called randomness condensers. We phrase the definition of condensers as a bounded norm condition and the definition of quantum-proof condensers as a completely bounded norm condition. Seeing condensers as bipartite graphs, we then find that the bounded norm condition corresponds to an instance of a well-studied combinatorial problem, called bipartite densest subgraph. Furthermore, using the characterization in terms of operator spaces, we can associate to any condenser a Bell inequality (two-player game), such that classical and quantum strategies are in one-to-one correspondence with classical and quantum attacks on the condenser. Hence, we get for every quantum-proof condenser (which includes in particular quantum-proof extractors) a Bell inequality that cannot be violated by quantum mechanics.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V., & Wehner, S. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.419 · Cited by 2,688
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424 · cited 3×
“The dual norm is called the diamond norm, first introduced in quantum information by Kitaev [26].”
BackgroundInfluentialGeneralized privacy amplification
Bennett, C. H., Brassard, G., Crepeau, C., & Maurer, U. M. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.476316 · Cited by 1,417
SECURITY OF QUANTUM KEY DISTRIBUTION
RENNER, R. (2008) · International Journal of Quantum Information · doi:10.1142/s0219749908003256 · Cited by 1,047
Privacy Amplification by Public Discussion
Bennett, C. H., Brassard, G., & Robert, J.-M. (1988) · SIAM Journal on Computing · doi:10.1137/0217014 · Cited by 867
Introduction to Operator Space Theory
Pisier, G. (2003) · Cambridge University Press eBooks · doi:10.1017/cbo9781107360235 · Cited by 742
Nisan, N., & Zuckerman, D. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0004 · Cited by 634
Feige, U., Peleg, D., & Kortsarz, G. (2001) · Algorithmica · doi:10.1007/s004530010050 · Cited by 592
Leftover Hashing Against Quantum Side Information
Tomamichel, M., Schaffner, C., Smith, A., & Renner, R. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158473 · Cited by 303
RECENT DEVELOPMENTS IN EXPLICIT CONSTRUCTIONS OF EXTRACTORS
SHALTIEL, R. (2004) · Current Trends in Theoretical Computer Science · doi:10.1142/9789812562494_0013 · Cited by 291
Research works printed but not linked: 3
- 10.4086/toc.2012.v008a021 · doi:10.4086/toc.2012.v008a021
- ta-shma, 2013, Extractors against classical and quantum adversaries, Proc Tutorial QCrypt
- 10.4086/toc.2009.v005a011 · doi:10.4086/toc.2009.v005a011
Cited by
Quantum Machine Learning for 6G Communication Networks: State-of-the-Art and Vision for the Future
Nawaz, S. J., Sharma, S. K., Wyne, S., Patwary, M. N., & Asaduzzaman, M. (2019) · IEEE Access · doi:10.1109/access.2019.2909490 · Cited by 658
Security in quantum cryptography
Portmann, C., & Renner, R. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.025008 · Cited by 390
Universal Security for Randomness Expansion from the Spot-Checking Protocol
Miller, C. A., & Shi, Y. (2017) · SIAM Journal on Computing · doi:10.1137/15m1044333 · Cited by 107
Realistic noise-tolerant randomness amplification using finite number of devices
Brandão, F. G. S. L., Ramanathan, R., Grudka, A., Horodecki, K., Horodecki, M., Horodecki, P., Szarek, T., & Wojewódka, H. (2016) · Nature Communications · doi:10.1038/ncomms11345 · Cited by 66
Mitigating 5G security challenges for next-gen industry using quantum computing
Mangla, C., Rani, S., Qureshi, N. M. F., & Singh, A. D. (2022) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2022.07.009 · Cited by 69
Metadata
- Authors
- Berta, M., Fawzi, O., & Scholz, V. B.
- Affiliations
- California Institute of Technology (US)
- Lyon 1 Université (FR)
- Ghent University (BE)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2017-04
- Volume
- 63
- Issue
- 4
- Pages
- 2480-2503
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W10211374
- Cited by
- 12
- References
- 57
- Citations by year
- 2025: 2 · 2023: 1 · 2022: 3 · 2020: 1 · 2019: 1
- FWCI
- 1.37
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (publishedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- HAL (submittedVersion)
- Spiral (Imperial College London) (submittedVersion)
- arXiv (Cornell University)
- Funders
- SNSF through a fellowship
- Institute for Quantum Information and Matter
- NSF Physics Frontiers Center (PHY-1125565)
- Gordon and Betty Moore Foundation (GBMF-12500028)
- Army Research Office grant for Research on Quantum Algorithms at IQIM (W911NF-12-1-0521)
- European Research Council (258932)
- EU under the Project Randomness and Quantum Entanglement (RAQUEL)
- ETH Fellowship
- Topics
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Keywords
- operator spaces, completely bounded norm, Bell inequalities, device-independent randomness, quantum Shannon theory, quantum adversaries
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Quantum-Proof Randomness Extractors via Operator Space Theory. https://app.cochat.ai/papers/10.1109/tit.2016.2627531
- The paper
- Berta, M., Fawzi, O., & Scholz, V. B. (2017). Quantum-Proof Randomness Extractors via Operator Space Theory. IEEE Transactions on Information Theory. https://doi.org/10.1109/tit.2016.2627531
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.