Cryptology ePrint Archive: Report 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).

Category / Keywords: secret-key cryptography / extractors, bounded storage model, everlasting security, space-bounded adversaries, unconditional security, averaging samplers, expander graphs

Date: received 1 Nov 2002

Contact author: salil at eecs harvard edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20021101:202713 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]