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.