Paper 2002/162

On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model

Salil P. Vadhan

Abstract

We consider the problem of constructing randomness extractors which are {\em locally computable}, i.e. only read a small number of bits from their input. As recently shown by Lu (CRYPTO `02), locally computable extractors directly yield secure private-key cryptosystems in Maurer's bounded storage model (J. Cryptology, 1992). 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).