Welcome to the resource topic for 2002/162
Title:
On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model
Authors: 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).
ePrint: https://eprint.iacr.org/2002/162
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .