--- res: bibo_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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Marciej foaf_name: Obremski, Marciej foaf_surname: Obremski - foaf_Person: foaf_givenName: Maciej foaf_name: Skorski, Maciej foaf_surname: Skorski foaf_workInfoHomepage: http://www.librecat.org/personId=EC09FA6A-02D0-11E9-8223-86B7C91467DD bibo_doi: 10.1109/ISIT.2018.8437654 bibo_volume: 2018 dct_date: 2018^xs_gYear dct_identifier: - UT:000448139300368 dct_language: eng dct_publisher: IEEE@ dct_title: Inverted leftover hash lemma@ ...