Better short-seed quantum-proof extractors

DOI10.1016/J.TCS.2011.11.036zbMATH Open1288.68067DBLPjournals/tcs/Ben-AroyaT12arXiv1004.3737OpenAlexW1968453666WikidataQ62398451 ScholiaQ62398451MaRDI QIDQ764353FDOQ764353

Authors: Avraham Ben-Aroya, Amnon Ta-Shma 

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We construct a strong extractor against quantum storage that works for every min-entropy $k$, has logarithmic seed length, and outputs $Omega(k)$ bits, provided that the quantum adversary has at most $$ qubits of memory, for any $$. The construction works by first condensing the source (with minimal entropy-loss) and then applying an extractor that works well against quantum adversaries when the source is close to uniform. We also obtain an improved construction of a strong quantum-proof extractor in the high min-entropy regime. Specifically, we construct an extractor that uses a logarithmic seed length and extracts $Omega(n)$ bits from any source over $B^n$, provided that the min-entropy of the source conditioned on the quantum adversary's state is at least $$, for any $$.

Full work available at URL: https://arxiv.org/abs/1004.3737

Recommendations

• Near-optimal extractors against quantum storage
• Short seed extractors against quantum storage
• Short seed extractors against quantum storage
• Quantum to classical randomness extractors
• The Bounded-Storage Model in the Presence of a Quantum Adversary

zbMATH Keywords

quantum informationextractorsbounded storage modelprivacy amplification

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cites Work

• Generalized privacy amplification
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• Privacy Amplification by Public Discussion
• The Operational Meaning of Min- and Max-Entropy
• Randomness is linear in space
• Tiny families of functions with random properties: A quality-size trade-off for hashing
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• Randomness conductors and constant-degree lossless expanders
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• On the Power of Quantum Memory
• Loss-less condensers, unbalanced expanders, and extractors
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Lossless condensers, unbalanced expanders, and extractors
• Correcting errors without leaking partial information
• Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker
• Extractors and pseudorandom generators
• Computing with Very Weak Random Sources
• Leftover Hashing Against Quantum Side Information
• Near-optimal extractors against quantum storage
• Kakeya sets, new mergers, and old extractors
• Trevisan's extractor in the presence of quantum side information
• The Bounded-Storage Model in the Presence of a Quantum Adversary

Cited In (10)

• Quantum to classical randomness extractors
• Connectivity for quantum graphs
• The Bounded-Storage Model in the Presence of a Quantum Adversary
• Quantum expanders and growth of group representations
• Semidefinite programs for randomness extractors
• Short seed extractors against quantum storage
• A modular framework for quantum-proof randomness extractors
• Short seed extractors against quantum storage
• Two-source extractors secure against quantum adversaries
• Two-source extractors secure against quantum adversaries

This page was built for publication: Better short-seed quantum-proof extractors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764353)