Paper 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).

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
extractorsbounded storage modeleverlasting securityspace-bounded adversariesunconditional securityaveraging samplersexpander graphs
Contact author(s)
salil @ eecs harvard edu
History
2002-11-01: received
Short URL
https://ia.cr/2002/162
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/162,
      author = {Salil P.  Vadhan},
      title = {On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model},
      howpublished = {Cryptology ePrint Archive, Paper 2002/162},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/162}},
      url = {https://eprint.iacr.org/2002/162}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.