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
-
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},
url = {https://eprint.iacr.org/2017/507}
}
