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.
展开▼
机译:防量子随机提取器是经典和量子密码学以及与设备无关的随机性放大和扩展的重要组成部分。此外,它们还是量子香农理论中的有用工具。众所周知,有些萃取器结构是量子抗性的,而另一些萃取器结构却证明不是[Gavinsky et al。,STOC’07]。我们认为,算子空间理论为研究提取器对量子对手的安全程度提供了一个自然的框架:我们首先将提取器的定义表述为范数空间之间的有界范式条件,然后证明量子对手的存在与否到运算符空间之间的完全有界范数条件。由此可见,极高的最小熵提取器以及具有小输出的提取器总是(近似)量子抗的。我们还研究了称为随机冷凝器的提取器的一般化。我们将聚光镜的定义称为有界范数条件,将防量子聚光镜的定义称为完全有界范数条件。将冷凝器看作是二部图,然后我们发现有界范数条件对应于一个经过充分研究的组合问题实例,称为二部最密子图。此外,使用算子空间的表征,我们可以将任何Bell不等式(两人博弈)与任何电容器联系起来,从而使经典和量子策略与对电容器的经典和量子攻击一一对应。因此,我们为每个防量子电容器(特别是包括防量子提取器)获得了一个贝尔不等式,该不等式不能被量子力学所破坏。
展开▼