SPEAKER: Yevgeniy Dodis New York University TITLE: The 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, LHL-based extractors suffer from the following two drawbacks: * Large Entropy Loss: the maximum number of extracted bits is at least L = 2*log(1/e) less than the (min-)entropy of the source, where e is the desired statistical distance from uniform. * Large Seed Length: the seed length of universal hash functions 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 most cryptographic applications. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e / 2^L). Second, we study the soundness of the natural *expand-then-extract* approach, where one uses a pseudorandom generator (PRG) to expand the seed of extractors which require large seed length (such as LHL-based extractors). As our main result, we show that, although the expand than extract-approach is *not* sound in general, any counter-example implies an efficient construction of public-key encryption (and even oblivious transfer!) from a PRG. This suggests that the sample-then-extract 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, and is also mentioned in the New Yorker magazine (October 2011). Joint work with: Boaz Barak, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, Francois-Xavier Standaert, and Yu Yu