When are fuzzy extractors possible?

Benjamin Fuller; Leonid Reyzin; Adam Smith

doi:10.1007/978-3-662-53887-6_10

When are fuzzy extractors possible?

Benjamin Fuller, Leonid Reyzin, Adam Smith

School of Electrical Engineering and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

19 Scopus citations

Abstract

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key. We define fuzzy min-entropy to quantify this property of a noisy source of secrets. Fuzzy min-entropy measures the success of the adversary when provided with only the functionality of the fuzzy extractor, that is, the ideal security possible from a noisy distribution. High fuzzy min-entropy is necessary for the existence of a fuzzy extractor. We ask: is high fuzzy min-entropy a sufficient condition for key extraction from noisy sources? If only computational security is required, recent progress on program obfuscation gives evidence that fuzzy minentropy is indeed sufficient. In contrast, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy. In this paper, we show that fuzzy min-entropy is sufficient for information theoretically secure fuzzy extraction. For every source distribution W for which security is possible we give a secure fuzzy extractor. Our construction relies on the fuzzy extractor knowing the precise distribution of the source W. A more ambitious goal is to design a single extractor that works for all possible sources. Our second main result is that this more ambitious goal is impossible: we give a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. We show three flavors of this impossibility result: for standard fuzzy extractors, for fuzzy extractors that are allowed to sometimes be wrong, and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.

Original language	English (US)
Title of host publication	Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Jung Hee Cheon, Tsuyoshi Takagi
Publisher	Springer Verlag
Pages	277-306
Number of pages	30
ISBN (Print)	9783662538869
DOIs	https://doi.org/10.1007/978-3-662-53887-6_10
State	Published - 2016
Event	22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016 - Hanoi, Viet Nam Duration: Dec 4 2016 → Dec 8 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10031 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016
Country/Territory	Viet Nam
City	Hanoi
Period	12/4/16 → 12/8/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-53887-6_10

Cite this

Fuller, B., Reyzin, L., & Smith, A. (2016). When are fuzzy extractors possible? In J. H. Cheon, & T. Takagi (Eds.), Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 277-306). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10031 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-53887-6_10

Fuller, Benjamin ; Reyzin, Leonid ; Smith, Adam. / When are fuzzy extractors possible?. Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Jung Hee Cheon ; Tsuyoshi Takagi. Springer Verlag, 2016. pp. 277-306 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0ed6d4b1f0e2476baab89bf06d2ef47a,

title = "When are fuzzy extractors possible?",

abstract = "Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key. We define fuzzy min-entropy to quantify this property of a noisy source of secrets. Fuzzy min-entropy measures the success of the adversary when provided with only the functionality of the fuzzy extractor, that is, the ideal security possible from a noisy distribution. High fuzzy min-entropy is necessary for the existence of a fuzzy extractor. We ask: is high fuzzy min-entropy a sufficient condition for key extraction from noisy sources? If only computational security is required, recent progress on program obfuscation gives evidence that fuzzy minentropy is indeed sufficient. In contrast, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy. In this paper, we show that fuzzy min-entropy is sufficient for information theoretically secure fuzzy extraction. For every source distribution W for which security is possible we give a secure fuzzy extractor. Our construction relies on the fuzzy extractor knowing the precise distribution of the source W. A more ambitious goal is to design a single extractor that works for all possible sources. Our second main result is that this more ambitious goal is impossible: we give a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. We show three flavors of this impossibility result: for standard fuzzy extractors, for fuzzy extractors that are allowed to sometimes be wrong, and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.",

author = "Benjamin Fuller and Leonid Reyzin and Adam Smith",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2016.; 22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016 ; Conference date: 04-12-2016 Through 08-12-2016",

year = "2016",

doi = "10.1007/978-3-662-53887-6_10",

language = "English (US)",

isbn = "9783662538869",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "277--306",

editor = "Cheon, {Jung Hee} and Tsuyoshi Takagi",

booktitle = "Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

}

Fuller, B, Reyzin, L & Smith, A 2016, When are fuzzy extractors possible? in JH Cheon & T Takagi (eds), Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10031 LNCS, Springer Verlag, pp. 277-306, 22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016, Hanoi, Viet Nam, 12/4/16. https://doi.org/10.1007/978-3-662-53887-6_10

When are fuzzy extractors possible? / Fuller, Benjamin; Reyzin, Leonid; Smith, Adam.
Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Jung Hee Cheon; Tsuyoshi Takagi. Springer Verlag, 2016. p. 277-306 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10031 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution