
CS Colloquium
Wed, Apr 27, 2011 @ 03:30 PM  05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Yevgeniy Dodis, NYU
Talk Title: Leftover Hash Lemma, Revisited
Abstract: The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHLbased extractors suffer from the following two drawbacks:
(1) Large Entropy Loss: to extract v bits from distribution X of minentropy m which are eclose to uniform, one must set v = 2*log(1/e).
(2) Large Seed Length: the seed length n of universal hash function required by the LHL must be linear in the length of the source.
Quite surprisingly, we show that both limitations of the LHL  large entropy loss and large seed  can often be overcome (or, at least,
mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1/e) for the setting of deriving secret keys for a wide range of cryptographic applications, including *all* "unpredictability" applications (signatures, MACs, etc.) and also some prominent "indistinguishability" applications, including chosen plaintext (or ciphertext) attack secure (public or symmetrickey) encryption schemes. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2^{L}).(Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the minentropy we have!)
Second, we study the soundness of the natural *expandthenextract* approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S', and then use the resulting S' as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expandthenextract approach is not sound if the Decisional DiffieHellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in *minicrypt*.
Implication (2) suggests that the samplethenextract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security!
The paper can be found at http://eprint.iacr.org/2011/088
Biography: Yevgeniy Dodis is an Associate Professor of computer science at New York University, which he joined in 2001 after receiving his PhD at MIT in 2000 and being a postdoc at IBM T.J.Watson Research center.
He also spent 20072008 academic year visiting the CRCS center at Harvard University.
Dr. Dodis' research is primarily in cryptography and network security.
In particular, he worked in a variety of areas including leakageresilient cryptography, cryptography under weak randomness, cryptography with biometrics and other noisy data, hash function and block cipher design, protocol composition and informationtheoretic cryptography. Dr. Dodis has more than 90 scientific publications at various conferences, journals and other venues, has been on program committees of many international conferences (including FOCS, STOC, CRYPTO 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, Google Faculty Award and Best Paper Award at 2005 Public Key Cryptography Conference. As an undergraduate student, he was also a winner of the USCanada Putnam Mathematical Competition in 1995.
Host: Prof. David Kempe
Location: Grace Ford Salvatori Hall Of Letters, Arts & Sciences (GFS)  118
Audiences: Everyone Is Invited
Contact: Kanak Agrawal