Title: On Extractors, Error-Correction and Hiding All Partial Information

Speaker: Yevgeniy Dodis, NYU 

Abstract:
======
Randomness extractors allow one to obtain nearly perfect randomness
from highly imperfect sources randomness, which are only known to
contain "scattered" entropy. Not surprisingly, such extractors have
found numerous applications in many areas of computer science
including cryptography. Aside from extracting randomness, a less known
usage of extractors comes from the fact that they hide all
deterministic functions of their (high-entropy) input: in other words,
extractors provide certain level of privacy for the imperfect source
that they use. In the latter kind of applications, one typically needs
extra properties of extractors, such as invertibility,
collision-resistance, error-correction or unforgeability. In this talk
we survey some of such usages of extractors, concentrating on several
recent results by the speaker. The primitives we will survey include
several flavors of randomness extractors (including "fuzzy extractors"
and "extractor-macs"), entropically secure encryption and perfect
one-way hash functions. The main technical tools will include several
variants of the leftover hash lemma, error correcting codes, and the
connection between randomness extraction and hiding all partial
information.

The survey paper can be found at
http://theory.lcs.mit.edu/~yevgen/ps/ent-survey.ps