Near-optimal extractors against quantum storage

DOI10.1145/1806689.1806713MaRDI QIDQ2875142zbMATHOpenAlexWikidataFDO

Authors Anindya De, Thomas Vidick

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

extractorsbounded quantum storagerandom access codes

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum cryptography (quantum-theoretic aspects) (81P94)

Abstract: We show that Trevisan's extractor and its variants cite{T99,RRV99} are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length $Theta(K-b)$, where $K$ is the source's entropy and $b$ the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length $Theta((K-b)/K^{g}amma)$ for any $gamma>0$. In contrast, the previous best construction cite{TS09} could only extract $(K/b{)}^{1/15}$ bits. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications. Our argument is based on bounds for a generalization of quantum random access codes, which we call emph{quantum functional access codes}. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in cite{TS09}, which was the source of the multiplicative overhead.

Recommendations

• Short seed extractors against quantum storage
• Short seed extractors against quantum storage
• The Bounded-Storage Model in the Presence of a Quantum Adversary
• Efficient and exact quantum compression
• Cryptography in the Bounded-Quantum-Storage Model
• Unconditional Security From Noisy Quantum Storage
• Two-source extractors secure against quantum adversaries
• Two-source extractors secure against quantum adversaries
• A quantum-proof non-malleable extractor. With application to privacy amplification against active quantum adversaries
• Lossless quantum data compression and quantum Kolmogorov complexity

Cited in

(14)

• Two-source extractors secure against quantum adversaries
• Two-source extractors secure against quantum adversaries
• Short seed extractors against quantum storage
• A modular framework for quantum-proof randomness extractors
• Better short-seed quantum-proof extractors
• From graphs to keyed quantum hash functions
• Short seed extractors against quantum storage
• Post-quantum simulatable extraction with minimal assumptions: black-box and constant-round
• Optimal bounds for parity-oblivious random access codes
• scientific article; zbMATH DE number 5788515 (Why is no real title available?)
• Semidefinite programs for randomness extractors
• Quantum to classical randomness extractors
• The Bounded-Storage Model in the Presence of a Quantum Adversary
• Trevisan's extractor in the presence of quantum side information

This page was built for publication: Near-optimal extractors against quantum storage

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