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 also 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. We show 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. This result emphasizes the importance of accurate models of high entropy sources.
Category / Keywords: Fuzzy extractors, secure sketches, information theory, biometric authentication, error-tolerance, key derivation, error-correcting codes. Date: received 24 Nov 2014, last revised 24 Feb 2015 Contact author: bfuller at cs bu edu Available format(s): PDF | BibTeX Citation Note: Significantly revised proofs and discussion. In submission. Version: 20150224:222234 (All versions of this report) Short URL: ia.cr/2014/961 Discussion forum: Show discussion | Start new discussion