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:1409.3563 · IEEE Transactions on Information Theory

Quantum-Proof Randomness Extractors via Operator Space Theory

Mario Berta, Omar Fawzi, Volkher B. Scholz

Published Nov 11, 2016• 12 citations
arXivHTMLPDF

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.

DOI
10.1109/tit.2016.2627531

Related papers

Semidefinite Programs for Randomness Extractors

Mario Berta, Omar Fawzi, Volkher B. Scholz

Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation.

Leibniz international proceedings in informatics•Jan 1, 2015•2 citations

Variations on classical and quantum extractors

Mario Berta, Omar Fawzi, Volkher B. Scholz +1 more

Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).

•Jan 1, 2014•4 citations

Variations on classical and quantum extractors

Mario Berta, Omar Fawzi, Volkher B. Scholz +1 more

Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).

arXiv:1402.3279•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•10 citations

Quantum-Proof Extractors: Optimal up to Constant Factors

Kai-Min Chung, Cohen, Gil, Thomas Vidick +1 more

We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence $O(\log(n/\varepsilon))$ on the input length $n$ and error $\varepsilon$. Our extractors support any min-entropy $k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))$ and extract $m=(1-α)k$ bits that are $\varepsilon$-close to uniform, for any desired constant $α> 0$. Previous constructions had a quadratically worse seed length or were restricted to very large input min-entropy or very few output bits. Our result is based on a generic reduction showing that any strong classical condenser is automatically quantum-proof, with comparable parameters. The existence of such a reduction for extractors is a long-standing open question, here we give an affirmative answer for condensers. Once this reduction is established, to obtain our quantum-proof extractors one only needs to consider high entropy sources. We construct quantum-proof extractors with the desired parameters for such sources by extending a classical approach to extractor construction, based on the use of block-sources and sampling, to the quantum setting. Our extractors can be used to obtain improved protocols for device-independent randomness expansion and for privacy amplification.

arXiv:1605.04194•May 13, 2016•1 citation

Quantum to Classical Randomness Extractors

Mario Berta, Omar Fawzi, Stephanie Wehner

The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.

arXiv:1111.2026•IEEE Transactions on Information Theory•Jan 24, 2014•38 citations

Quantum-Proof Multi-Source Randomness Extractors in the Markov Model

Rotem Arnon-Friedman, Christopher Portmann, Volkher B. Scholz

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.

Leibniz international proceedings in informatics•Jan 1, 2016•11 citations
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.
Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation.
Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).
Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).
We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence O(log⁡(n/ε))O(\log(n/\varepsilon))O(log(n/ε)) on the input length nnn and error ε\varepsilonε. Our extractors support any min-entropy k=Ω(log⁡n+log⁡1+α(1/ε))k=Ω(\log{n} + \log^{1+α}(1/\varepsilon))k=Ω(logn+log1+α(1/ε)) and extract m=(1−α)km=(1-α)km=(1−α)k bits that are ε\varepsilonε-close to uniform, for any desired constant α>0α> 0α>0. Previous constructions had a quadratically worse seed length or were restricted to very large input min-entropy or very few output bits. Our result is based on a generic reduction showing that any strong classical condenser is automatically quantum-proof, with comparable parameters. The existence of such a reduction for extractors is a long-standing open question, here we give an affirmative answer for condensers. Once this reduction is established, to obtain our quantum-proof extractors one only needs to consider high entropy sources. We construct quantum-proof extractors with the desired parameters for such sources by extending a classical approach to extractor construction, based on the use of block-sources and sampling, to the quantum setting. Our extractors can be used to obtain improved protocols for device-independent randomness expansion and for privacy amplification.
The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.
Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.