Paper Info
Title
Near-optimal extractors against quantum storage
Abstract
We give near-optimal constructions of extractors secure against quantum bounded-storage ad- versaries. One instantiation gives the rst such extractor to achieve an output length ( K b), where K is the source's entropy and b the adversary's storage, depending linearly on the adver- sary's amount of 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 (Ts09) could only extract (K=b)1=15 bits. Our construction follows Trevisan's general reconstruction paradigm (Tre01), and in fact our proof of security shows that essentially all extractors constructed using this paradigm are secure against quantum storage, with optimal parameters. 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 (Ts09), which was the source of the multiplicative overhead. 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.
Year
DOI
Venue
2010
10.1145/1806689.1806713
STOC
Keywords
Field
DocType
near-optimal extractor,additional advantage,extractors,bounded quantum storage adversary,logarithmic key length,output length,smaller output length,cryptographic application,quantum functional access code,poly-logarithmic seed length,random access codes,multiplicative overhead,quantum storage,list decodable code,quantum random access code,random access,list decoding,quantum physics
Discrete mathematics,Quantum,Combinatorics,Multiplicative function,Cryptography,Extractor,Logarithm,Mathematics,Key size,Bounded function,Random access
Conference
Volume
ISSN
Citations 
16
0737-8017
11
PageRank 
References 
Authors
0.64
23
2
Name
Order
Citations
PageRank
Anindya De123924.77
Thomas Vidick237731.69