Better short-seed quantum-proof extractors

DOI10.1016/J.TCS.2011.11.036MaRDI QIDQ764353zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Avraham Ben-Aroya, Amnon Ta-Shma

Publication date 13 March 2012

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

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

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)

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 $$.

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

Cites work

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

Cited in

(10)

• Quantum to classical randomness extractors
• Connectivity for quantum graphs
• Quantum expanders and growth of group representations
• The Bounded-Storage Model in the Presence of a Quantum Adversary
• Short seed extractors against quantum storage
• Semidefinite programs for randomness extractors
• 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)