Paper 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.

Note: typo fix

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
randomness extractorsuniversal hash functionsextremal graph theory
Contact author(s)
maciej skorski @ gmail com
History
2017-07-07: revised
2017-06-02: received
See all versions
Short URL
https://ia.cr/2017/507
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/507,
      author = {Maciej Obremski and Maciej Skórski},
      title = {Inverted Leftover Hash Lemma},
      howpublished = {Cryptology ePrint Archive, Paper 2017/507},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/507}},
      url = {https://eprint.iacr.org/2017/507}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.