Inverted Leftover Hash Lemma
| العنوان: | Inverted Leftover Hash Lemma |
|---|---|
| المؤلفون: | Maciej Skorski, Maciej Obremski |
| المصدر: | ISIT Obremski, M & Skorski, M 2018, Inverted Leftover Hash Lemma . in 2018 IEEE International Symposium on Information Theory, ISIT 2018 . vol. 2018-June, 8437654, IEEE, pp. 1834-1838, 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, United States, 17/06/2018 . https://doi.org/10.1109/ISIT.2018.8437654 2018 IEEE International Symposium on Information Theory (ISIT) |
| بيانات النشر: | IEEE, 2018. |
| سنة النشر: | 2018 |
| مصطلحات موضوعية: | Discrete mathematics, Universal Hash Functions, Universal hashing, Computer science, business.industry, Leftover hash lemma, TheoryofComputation_GENERAL, 020206 networking & telecommunications, Cryptography, Data_CODINGANDINFORMATIONTHEORY, 0102 computer and information sciences, 02 engineering and technology, Min-Entropy Extractors, 16. Peace & justice, 01 natural sciences, Extractor, Extremal graph theory, 010201 computation theory & mathematics, Extremal Graph Theory, 0202 electrical engineering, electronic engineering, information engineering, business, Randomness |
| الوصف: | 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. |
| ردمك: | 978-1-5386-4781-3 |
| DOI: | 10.1109/isit.2018.8437654 |
| DOI: | 10.1109/ISIT.2018.8437654 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::96b299d43b36ea2deb807076bbbd2e9d https://doi.org/10.1109/isit.2018.8437654 |
| Rights: | RESTRICTED |
| رقم الانضمام: | edsair.doi.dedup.....96b299d43b36ea2deb807076bbbd2e9d |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9781538647813 |
|---|---|
| DOI: | 10.1109/isit.2018.8437654 |