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 limitations: • Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are ε-close to uniform, one must set v ≤ m − 2 log (1/ε), meaning that the entropy loss L def = m − v ≥ 2 log (1/ε). For many applications, such entropy loss is too large. • Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n ≥ min(u − v, v + 2 log (1/ε))−O(1), where u is the length of the source, and must grow with the number of extracted bits. Quite surprisingly, we show that both limitations of the LHL — large entropy loss and large seed — can be overcome (or, at least, mitigated) in various important scenarios. First, we show that entropy loss could be reduced to L = log (1/ε) for the setting of deriving secret key