A Caltech Library Service

Near-Optimal Extractors Against Quantum Storage

De, Anindya and Vidick, Thomas (2010) Near-Optimal Extractors Against Quantum Storage. In: Proceedings of the 42nd ACM symposium on Theory of computing. ACM , New York, NY, pp. 161-170. ISBN 978-1-4503-0050-6.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show that Trevisan's extractor and its variants] 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 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, which was the source of the multiplicative overhead.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2010 ACM. Supported by the "Berkeley Fellowship for Graduate Study" and Luca Trevisan's US-Israel BSF grant 2006060. Supported by ARO grant W911NF-09-1-0440 and NSF grant CCF-0905626. We are grateful to Falk Unger and Umesh Vazirani for comments which helped us improve the presentation in this paper. The first author would like to thank Luca Trevisan for kindly sharing his understanding of extractors.
Funding AgencyGrant Number
Berkeley Fellowship for Graduate StudyUNSPECIFIED
Binational Science Foundation (USA-Israel)2006060
Army Research Office (ARO)W911NF-09-1-0440
Subject Keywords:Extractors, Bounded Quantum Storage, Random Access Codes
Record Number:CaltechAUTHORS:20140910-145258006
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49561
Deposited By: Tony Diaz
Deposited On:10 Sep 2014 22:02
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page