Salil P. Vadhan
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: use essentially any randomness-efficient sampler to select bits from the input and then apply any extractor to the selected bits. 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. We also provide lower bounds showing that the parameters we achieve are nearly optimal.
The correctness of the sample-then-extract 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.