Inverted leftover hash lemma Conference Paper

Author(s): Obremski, Marciej; Skórski, Maciej
Title: Inverted leftover hash lemma
Title Series: ISIT Proceedings
Affiliation IST Austria
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 possible applications to the theory of randomness extractors and non-malleable codes.
Keywords: Extremal Graph Theory; Min-Entropy Extractors; Universal Hash Functions
Conference Title: ISIT: International Symposium on Information Theory
Volume: 2018
Conference Dates: June 17 - 22, 2018
Conference Location: Vail, CO, USA
ISBN: 21578095 (ISSN); 9781538647806 (ISBN)
Publisher: IEEE  
Date Published: 2018-08-15
Start Page: Article number: 8437654
DOI: 10.1109/ISIT.2018.8437654
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work