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 min-entropy 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.Category / Keywords: Fuzzy extractors, secure sketches, information theory, biometric authentication, error-tolerance, key derivation, error-correcting codes Original Publication (with minor differences): IACR-ASIACRYPT-2016 Date: received 24 Nov 2014, last revised 7 Sep 2016 Contact author: benjamin fuller at uconn edu Available format(s): PDF | BibTeX Citation Note: This is the full version of a work appearing at Asiacrypt 2016. It contains additional proofs. Version: 20160907:140355 (All versions of this report) Short URL: ia.cr/2014/961 Discussion forum: Show discussion | Start new discussion