On Extractors, Error-Correction and Hiding All Partial Information On Extractors, Error-Correction and Hiding All Partial Information
Speaker: Yevgeniy Dodis , New York University
Date: March 10 2006
Time: 10:30AM to 12:00PM
Location: 32-G449, Patil/Kiva,
Contact: Be Blackburn, 3-6098, firstname.lastname@example.org
Relevant URL: http://theory.lcs.mit.edu/~yevgen/ps/ent-survey.ps
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.
See other events that are part of Cryptography and Information Security Seminar Seminars 2005/2006
See other events happening in March 2006