Near-optimal extractors against quantum storage

Anindya De*, Thomas Vidick

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

We show that Trevisan's extractor and its variants [22,19] are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length Θ(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 Θ((K-b)/Kγ) for any γ>0. In contrast, the previous best construction [21] 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 quantum functional access codes. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in [21], which was the source of the multiplicative overhead.

Original languageEnglish (US)
Title of host publicationSTOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing
Pages161-170
Number of pages10
DOIs
StatePublished - 2010
Event42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States
Duration: Jun 5 2010Jun 8 2010

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other42nd ACM Symposium on Theory of Computing, STOC 2010
CountryUnited States
CityCambridge, MA
Period6/5/106/8/10

Keywords

  • bounded quantum storage
  • extractors
  • random access codes

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Near-optimal extractors against quantum storage'. Together they form a unique fingerprint.

  • Cite this

    De, A., & Vidick, T. (2010). Near-optimal extractors against quantum storage. In STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing (pp. 161-170). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1806689.1806713