CSE Seminars/Conferences

Colloquia, Seminars and Conference News

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

Date : October 6, 2006. (11:00 am) Tea starts half an hour before each seminar

Location: ITEB 336

Speaker : Prof. Yevgeniy Dodis

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.

Bio:Yevgeniy Dodis is an assistant professor of computer science at New York University. Dr. Dodis received his summa cum laude Bachelors degree in mathematics and computer science from New York University in 1996, and his PhD degree in Computer Science from MIT in 2000. Dr. Dodis was a post-doc at IBM T.J.Watson Research center in 2000, and joined New York University as an assistant professor in 2001. Dr. Dodis' research is primarily in cryptography and network security. In particular, he worked in a variety of areas including exposure-resilient cryptography, cryptography and imperfect randomness, cryptography with biometrics and other noisy data, authenticated encryption, hash functions and information-theoretic cryptography. Dr. Dodis has more than 60 scientific publications at various conferences, journals and other venues, has been on program committees of many international conferences (including STOC, CRTYPTO and Eurocrypt), and gave numerous invited lectures and courses at various venues. Dr. Dodis is the recipient of National Science Foundation CAREER Award, IBM Faculty Award and Best Paper Award at 2005 Public Key Cryptography Conference. As an undergraduate student, he was also a winner of the US-Canada Putnam Mathematical Competition. Please see http://theory.lcs.mit.edu/~yevgen/ps/ent-survey.ps for more information.

[Back]


Computer Science & Engineering Department 371 Fairfield Road Unit 2155 Storrs, CT 06269-2155 Phone: (860) 486-3719 Fax: (860) 486-4817	Colloquia, Seminars and Conference News Title : On Extractors, Error-Correction and Hiding All Partial Information Date : October 6, 2006. (11:00 am) Tea starts half an hour before each seminar Location: ITEB 336 Speaker : Prof. Yevgeniy Dodis 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. Bio:Yevgeniy Dodis is an assistant professor of computer science at New York University. Dr. Dodis received his summa cum laude Bachelors degree in mathematics and computer science from New York University in 1996, and his PhD degree in Computer Science from MIT in 2000. Dr. Dodis was a post-doc at IBM T.J.Watson Research center in 2000, and joined New York University as an assistant professor in 2001. Dr. Dodis' research is primarily in cryptography and network security. In particular, he worked in a variety of areas including exposure-resilient cryptography, cryptography and imperfect randomness, cryptography with biometrics and other noisy data, authenticated encryption, hash functions and information-theoretic cryptography. Dr. Dodis has more than 60 scientific publications at various conferences, journals and other venues, has been on program committees of many international conferences (including STOC, CRTYPTO and Eurocrypt), and gave numerous invited lectures and courses at various venues. Dr. Dodis is the recipient of National Science Foundation CAREER Award, IBM Faculty Award and Best Paper Award at 2005 Public Key Cryptography Conference. As an undergraduate student, he was also a winner of the US-Canada Putnam Mathematical Competition. Please see http://theory.lcs.mit.edu/~yevgen/ps/ent-survey.ps for more information. [Back] Print \| Email