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
Ruan, Z.-J. (1988) · Journal of Functional Analysis · doi:10.1016/0022-1236(88)90057-2 · Cited by 269
Grothendieck’s Theorem, past and present
Pisier, G. (2012) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-2011-01348-9 · Cited by 236
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
Radhakrishnan, J., & Ta-Shma, A. (2000) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480197329508 · Cited by 223
(2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5 · Cited by 223
Unconditional Security From Noisy Quantum Storage
Konig, R., Wehner, S., & Wullschleger, J. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2177772 · Cited by 168
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
Large Violation of Bell Inequalities with Low Entanglement
Junge, M., & Palazuelos, C. (2011) · Communications in Mathematical Physics · doi:10.1007/s00220-011-1296-8 · Cited by 160
Extracting Randomness: A Survey and New Constructions
Nisan, N., & Ta‐Shma, A. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1546 · Cited by 158
Expanders, randomness, or time versus space
Sipser, M. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90035-9 · Cited by 127
Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., & de Wolf, R. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250866 · Cited by 126
Polynomial integrality gaps for strong SDP relaxations of Densest k -subgraph
Bhaskara, A., Charikar, M., Guruswami, V., Vijayaraghavan, A., & Zhou, Y. (2012) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973099.34 · Cited by 111
Advances in Cryptology – CRYPTO 2013
Canetti, R., & Garay, J. A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40084-1 · Cited by 110
Physical Randomness Extractors: Generating Random Numbers with Minimal AssumptionsPreprint
Chung, K.-M., Shi, Y., & Wu, X. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.4797 · Cited by 89
On recycling the randomness of states in space bounded computation
Raz, R., & Reingold, O. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301294 · Cited by 89
Miller, C. A., & Shi, Y. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591843 · Cited by 88
Multiplicativity of Completely Bounded p-Norms Implies a New Additivity Result
Devetak, I., Junge, M., King, C., & Ruskai, M. B. (2006) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0034-0 · Cited by 82
Certifiable 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 · cited 1×
“They are an essential ingredient in quantum key distribution and device independent randomness expansion protocols [3], [4], but are for example also useful in quantum Shannon theory [5], [6].”
BackgroundMultiplicativity of completely bounded p-norms implies a new additivity result
Devetak, I., Junge, M., King, C., & Ruskai, M. B. (2005) · CERN Document Server (European Organization for Nuclear Research) · Cited by 78
Unbounded Violations of Bipartite Bell Inequalities via Operator Space Theory
Junge, M., Palazuelos, C., Pérez-García, D., Villanueva, I., & Wolf, M. M. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-010-1125-5 · Cited by 78
Construction of extractors using pseudo-random generators (extended abstract)
Trevisan, L. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301289 · Cited by 73
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraphPreprint
Bhaskara, A., Charikar, M., Vijayaraghavan, A., et al. (2012) · doi:10.5555/2095116.2095150 · Cited by 73
Lossless Condensers, Unbalanced Expanders, And Extractors
Ta‐Shma, A., Umans, C., & Zuckerman, D. (2007) · COMBINATORICA · doi:10.1007/s00493-007-0053-2 · Cited by 71
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
The Bounded-Storage Model in the Presence of a Quantum Adversary
Konig, R. T., & Terhal, B. M. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.913245 · Cited by 65
Sampling of Min-Entropy Relative to Quantum Knowledge
Konig, R., & Renner, R. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2146730 · Cited by 64
Infinite randomness expansion with a constant number of devices
Coudron, M., & Yuen, H. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591873 · Cited by 62
Identifying the Information Gain of a Quantum Measurement
Berta, M., Renes, J. M., & Wilde, M. M. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2365207 · Cited by 60
Self-citationQuantum to Classical Randomness Extractors
Berta, M., Fawzi, O., & Wehner, S. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2291780 · Cited by 59
Self-citationUnbounded violations of bipartite Bell Inequalities via Operator Space theory
Junge, M., Pérez García, D., Palazuelos, C., Villanueva, I., & Wolf, M. (2010) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · Cited by 53
Mixed-norm Inequalities and Operator Space Lp Embedding Theory
Junge, M., & Parcet, J. (2010) · Cited by 48
Berta, M., Fawzi, O., & Scholz, V. B. (2016) · SIAM Journal on Optimization · doi:10.1137/15m1037731 · Cited by 44
Self-citationExtracting Randomness via Repeated Condensing
Reingold, O., Shaltiel, R., & Wigderson, A. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539703431032 · Cited by 39
Mixed-norm inequalities and operator space 𝐿_{𝑝} embedding theory
Junge, M., & Parcet, J. (2009) · Memoirs of the American Mathematical Society · doi:10.1090/s0065-9266-09-00570-5 · Cited by 31
The unified theory of pseudorandomness
Vadhan, S. (2007) · ACM SIGACT News · doi:10.1145/1324215.1324225 · Cited by 27
Operator spaces and Araki-Woods factors: A quantum probabilistic approach
Junge, M. (2006) · International Mathematics Research Papers · doi:10.1155/imrp/2006/76978 · Cited by 24
A Decoupling Approach to Classical Data Transmission Over Quantum Channels
Dupuis, F., Szehr, O., & Tomamichel, M. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2295330 · Cited by 22
Quantum to Classical Randomness Extractors
Berta, M., Fawzi, O., & Wehner, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32009-5_45 · Cited by 20
Self-citationMulti-Source Randomness Extractors Against Quantum Side Information, and their ApplicationsPreprint
Chung, K.-M., Li, X., & Wu, X. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.2315 · Cited by 19
Theory of Quantum Computation, Communication, and Cryptography
(2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54429-3 · Cited by 17
Better short-seed quantum-proof extractors
Ben-Aroya, A., & Ta‐Shma, A. (2011) · Theoretical Computer Science · doi:10.1016/j.tcs.2011.11.036 · Cited by 13
Variations on classical and quantum extractors
Berta, M., Fawzi, O., Scholz, V., & Szehr, O. (2014) · 2014 IEEE International Symposium on Information Theory · doi:10.1109/isit.2014.6875078 · Cited by 10 · cited 1×
“, spectral extractors [4]), and hence that the l1-normalization condition on the input is crucial for studying to what extent extractors are quantum-proof.”
BackgroundSelf-citationDecoupling TheoremsPreprint
Szehr, O. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.3927 · Cited by 8
Achieving the Limits of the Noisy-Storage Model Using Entanglement Sampling
Dupuis, F., Fawzi, O., & Wehner, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40084-1_19 · Cited by 7
Self-citationBitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access CodesPreprint
Wullschleger, J. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.2291 · Cited by 5
Variations on classical and quantum extractors
Berta, M., Fawzi, O., Scholz, V. B., & Szehr, O. (2014) · CaltechAUTHORS (California Institute of Technology) · Cited by 4
Self-citationBitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes
Wullschleger, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54429-3_11 · Cited by 3
Semidefinite Programs for Randomness Extractors
Berta, M., Fawzi, O., & Scholz, V. B. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.tqc.2015.73 · Cited by 3
Self-citation
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
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.