Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2010 | Submitted
Book Section - Chapter Open

Near-Optimal Extractors Against Quantum Storage

Abstract

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.

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.

Attached Files

Submitted - 0911.4680v3.pdf

Files

0911.4680v3.pdf
Files (248.5 kB)
Name Size Download all
md5:a18a8150873a215cb460faf42399a555
248.5 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 17, 2023