Cryptology ePrint Archive: Report 2017/507

Inverted Leftover Hash Lemma

Maciej Obremski and Maciej Skórski

Abstract: Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors.

In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs.

Our proof technique is based on tools from extremal graph theory applied to the ”collision graph” induced by the extractor, and may be of independent interest. We discuss implications for randomness extractors and non-malleable codes.

Category / Keywords: foundations / randomness extractors, universal hash functions, extremal graph theory

Date: received 1 Jun 2017, last revised 7 Jul 2017

Contact author: maciej skorski at gmail com

Available format(s): PDF | BibTeX Citation

Note: typo fix

Version: 20170707:191432 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]