Quantum-Proof Extractors: Optimal up to Constant Factors

Abstract

We give the first construction of a family of quantum-proof extractors that has optimal seed length dependence $O(\log (n/\epsilon ))$ on the input length $n$ and error $\epsilon$. Our extractors support any min-entropy $k=\Omega (\log n+{\log }^{1+\alpha }(1/\epsilon ))$ and extract $m=(1-\alpha )k$ bits that are $\epsilon$-close to uniform, for any desired constant $\alpha >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 paper has been withdrawn due to an error in the proof of Lemma 3.4 (step going from second-last to last centered equations), which invalidates the main result

References in corpus (5)

• Leftover Hashing Against Quantum Side Information
• The Bounded Storage Model in The Presence of a Quantum Adversary
• Quantum-proof randomness extractors via operator space theory
• Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs
• Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification