Yevgeniy Dodis
New York University

The Leftover Hash Lemma, Revisited

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

*    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