You are looking at a specific version 20160907:140355 of this paper. See the latest version.

Paper 2014/961

When are Fuzzy Extractors Possible?

Benjamin Fuller and Leonid Reyzin and Adam Smith

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 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.

Note: This is the full version of a work appearing at Asiacrypt 2016. It contains additional proofs.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2016
Keywords
Fuzzy extractorssecure sketchesinformation theorybiometric authenticationerror-tolerancekey derivationerror-correcting codes
Contact author(s)
benjamin fuller @ uconn edu
History
2020-08-26: last of 8 revisions
2014-11-25: received
See all versions
Short URL
https://ia.cr/2014/961
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.