CS Colloquium on Wednesday, Jan 28 at 11AM

Title: Locally Computable Extractors and Cryptosystems in the
       Bounded-Storage Model

Speaker: Salil Vadhan
         Harvard University and
         the Radcliffe Institute for Advanced Study

Place: MCS 135, 111 Cummington Street (please see
       http://cs-www.bu.edu/colloquium for directions)

-------------------------------------------------------------------------  

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 (notably
those of Aumann, Ding, and Rabin (1999,2002)).

In 2002, 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.

The correctness of the sample-then-extract approach is based on a
fundamental lemma of Nisan and Zuckerman (1993), 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.


Bio:

Salil Vadhan is an assistant professor of computer science at Harvard
University.  He holds an AB in mathematics and computer science from Harvard
and a PhD in applied mathematics from MIT. After his PhD, he spent a year at
the Institute for Advanced Study in Princeton before returning to Harvard.
His research interests are in Computational Complexity, Cryptography, and
Randomness in Computation.  His thesis, "A Study of Statistical
Zero-Knowledge Proofs", was awarded the ACM Doctoral Dissertation Award in
2000.  He is a recipient of a Sloan Research Fellowship and an NSF Career
Award. This year, he is chairing a research cluster on Randomness &
Computation at the Radcliffe Institute for Advanced Study.

Host: Leonid Reyzin (http://www.cs.bu.edu/~reyzin)