We consider the problem of constructing randomness extractors that are locally computable; that is, read only 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).
We suggest a general “sample-then-extract” approach to constructing locally computable extractors. Plugging in known sampler
and extractor 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.
The correctness of this approach follows from a fundamental lemma of Nisan and Zuckerman (J. Computer and System Sciences, 1996), which states that sampling bits from a weak random source roughly preserves the min-entropy rate. We also present
a refinement of this lemma, showing that the min-entropy rate is preserved up to an arbitrarily small additive loss, whereas
the original lemma loses a logarithmic factor.
A preliminary version of this paper has appeared on the Cryptology e-print archive [1] and a full version will appear in the
Journal of Cryptology.