Inverted Leftover Hash Lemma

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Maciej Obremski
  • ,
  • Maciej Skorski, IST Austria

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 possible applications to the theory of randomness extractors and non-malleable codes.

Original languageEnglish
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
Number of pages5
Publication year15 Aug 2018
Article number8437654
ISBN (print)9781538647806
Publication statusPublished - 15 Aug 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: 17 Jun 201822 Jun 2018


Conference2018 IEEE International Symposium on Information Theory, ISIT 2018
LandUnited States
SponsorHuawei, IEEE, IEEE InformationTheory Society, National Science Foundation, Qualcomm

    Research areas

  • Extremal Graph Theory, Min-Entropy Extractors, Universal Hash Functions

See relations at Aarhus University Citationformats

ID: 143073628