Inverted leftover hash lemma

M. Obremski, M. Skorski, in:, IEEE, 2018.

Conference Paper | Published | English

Scopus indexed
Obremski, Marciej; Skórski, MaciejIST Austria
Series Title
ISIT Proceedings
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.
Publishing Year
Date Published
ISIT: International Symposium on Information Theory
Conference Location
Vail, CO, USA
Conference Date
2018-06-17 – 2018-06-22

Cite this

Obremski M, Skorski M. Inverted leftover hash lemma. In: Vol 2018. IEEE; 2018. doi:10.1109/ISIT.2018.8437654
Obremski, M., & Skorski, M. (2018). Inverted leftover hash lemma (Vol. 2018). Presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA: IEEE.
Obremski, Marciej, and Maciej Skorski. “Inverted Leftover Hash Lemma,” Vol. 2018. IEEE, 2018.
M. Obremski and M. Skorski, “Inverted leftover hash lemma,” presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA, 2018, vol. 2018.
Obremski M, Skorski M. 2018. Inverted leftover hash lemma. ISIT: International Symposium on Information Theory, ISIT Proceedings, vol. 2018.
Obremski, Marciej, and Maciej Skorski. Inverted Leftover Hash Lemma. Vol. 2018, IEEE, 2018, doi:10.1109/ISIT.2018.8437654.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar