Near-optimal extractors against quantum storage

DOI10.1145/1806689.1806713zbMATH Open1293.68128arXiv0911.4680OpenAlexW2077372202WikidataQ59792831 ScholiaQ59792831MaRDI QIDQ2875142FDOQ2875142

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)

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.

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

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

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)

Cited In (14)

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

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)