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 -