In this note, we observe that a fundamental lemma of Nisan and Zuckerman (J. Computer and System Sciences, 1996) yields a general technique for constructing locally computable extractors. Specifically, we obtain a locally computable extractor by combining any extractor with any randomness-efficient (averaging) sampler. Plugging in known extractor and sampler constructions, we obtain locally computable extractors, and hence cryptosystems in the bounded storage model, whose parameters improve upon previous constructions and come quite close to the lower bounds.
Along the way, we also present a refinement of the Nisan--Zuckerman lemma, showing that random sampling bits from a weak random source preserves the min-entropy rate up to an arbitrarily small additive loss (whereas the original lemma loses a logarithmic factor).
Category / Keywords: secret-key cryptography / extractors, bounded storage model, everlasting security, space-bounded adversaries, unconditional security, averaging samplers, expander graphs Date: received 1 Nov 2002 Contact author: salil at eecs harvard edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20021101:202713 (All versions of this report) Short URL: ia.cr/2002/162 Discussion forum: Show discussion | Start new discussion