### When are Fuzzy Extractors Possible?

Benjamin Fuller, Leonid Reyzin, and Adam Smith

##### Abstract

Fuzzy extractors (Dodis et al., SIAM J. Computing 2008) 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 codify this quantify this property in a new notion called fuzzy min-entropy. We ask: is fuzzy min-entropy sufficient to build fuzzy extractors? We provide two answers for different settings. 1) If the algorithms have precise knowledge of the probability distribution $W$ that defines the noisy source is a sufficient condition for information-theoretic key extraction from $W$. 2) A more ambitious goal is to design a single extractor that works for all possible sources. This more ambitious goal is impossible: there is a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. This is true in three settings: a) for standard fuzzy extractors, b) for fuzzy extractors that are allowed to sometimes be wrong, c) and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.

Note: This work is now appearing in IEEE Transactions on Information Theory 2020 and a conference version appeared Asiacrypt 2016. This version contains all proofs and technical details.

Available format(s)
Publication info
Published elsewhere. MINOR revision.2020 IEEE Transactions on Information Theory. Conference Version is in 2016 Asiacrypt.
DOI
10.1109/TIT.2020.2984751
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
See all versions
Short URL
https://ia.cr/2014/961

CC BY

BibTeX

@misc{cryptoeprint:2014/961,
author = {Benjamin Fuller and Leonid Reyzin and Adam Smith},
title = {When are Fuzzy Extractors Possible?},
howpublished = {Cryptology ePrint Archive, Paper 2014/961},
year = {2014},
doi = {10.1109/TIT.2020.2984751},
note = {\url{https://eprint.iacr.org/2014/961}},
url = {https://eprint.iacr.org/2014/961}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.