Fall 2003

Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model

Salil Vadhan, Harvard University and the Radcliffe Institute for Advanced Study
Friday, November 14, 2003, 3:00PM, Stratton Hall, WPI, Room 203

Abstract

In 1990, Maurer proposed an interesting model for cryptography against a storage-bounded adversary in which information-theoretic security becomes feasible. Recently, this model has received much attention, with increasingly secure and efficient protocols being constructed.

Last year, Lu showed how secure cryptosystems in this model can be obtained directly from "randomness extractors" --- procedures for extracting almost-uniform bits from a source of biased and correlated bits. However, this application requires a nonstandard property from extractors: they should be "locally computable", i.e. read only a small number of bits from their input.

In this work, we present a general "sample-then-extract" approach for constructing locally computable extractors: use 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.

Maintained by webmaster@wpi.edu
Last modified: Sep 22, 2006, 20:31 EDT