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