## 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 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 - 2log(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 + 2log(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 keys for a wide range of cryptographic applications. Specifically, the security of these schemes with an LHL-derived key gracefully degrades from ε to at most ε + √ε2^{-L}. (Notice that, unlike standard LHL, this bound is meaningful even when one extracts more bits than the min-entropy we have!) Based on these results we build a general computational extractor that enjoys low entropy loss and can be used to instantiate a generic key derivation function for any cryptographic application. Second, we study the soundness of the natural expand-then-extract 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, by any randomness extractor). We show that, in general, the expand-then-extract approach is not sound if the Decisional Diffie-Hellman 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 expand-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security!

Original language | English (US) |
---|---|

Title of host publication | Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings |

Publisher | Springer Verlag |

Pages | 1-20 |

Number of pages | 20 |

ISBN (Print) | 9783642227912 |

DOIs | |

State | Published - 2011 |

Event | 31st Annual International Cryptology Conference, CRYPTO 2011 - Santa Barbara, CA, United States Duration: Aug 14 2011 → Aug 18 2011 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 6841 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 31st Annual International Cryptology Conference, CRYPTO 2011 |
---|---|

Country/Territory | United States |

City | Santa Barbara, CA |

Period | 8/14/11 → 8/18/11 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)