TY - GEN

T1 - Near-optimal extractors against quantum storage

AU - De, Anindya

AU - Vidick, Thomas

PY - 2010

Y1 - 2010

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

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

KW - bounded quantum storage

KW - extractors

KW - random access codes

UR - http://www.scopus.com/inward/record.url?scp=77954740848&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954740848&partnerID=8YFLogxK

U2 - 10.1145/1806689.1806713

DO - 10.1145/1806689.1806713

M3 - Conference contribution

AN - SCOPUS:77954740848

SN - 9781605588179

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 161

EP - 170

BT - STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing

T2 - 42nd ACM Symposium on Theory of Computing, STOC 2010

Y2 - 5 June 2010 through 8 June 2010

ER -