CSAIL Event Calendar: Previous Series

Extracting Correlations

Speaker: Yuval Ishai , Technion and UCLA
Date: May 12 2009
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, MIT

Randomness extractors convert dirty sources of randomness into clean sources of randomness. We consider an extension of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. Our main result is an efficient interactive two-party protocol which extracts m clean independent instances of a given joint distribution (X,Y) from n=O(m) dirty (or "leaky") instances of the same distribution. The classical case corresponds to X and Y being identical random bits.

I will present several cryptographic applications of correlation extractors and our main result. These include protecting certain cryptographic protocols against information leakage, basing communication-efficient secure computation on a number theoretic intractability assumption, and efficient reductions between different communication channels.

Joint work with Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai.

See other events that are part of Theory Colloquium 2008/2009

See other events happening in May 2009