Paper 2014/961
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
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2014-11-25: received
- See all versions
- Short URL
- https://ia.cr/2014/961
- License
-
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}, url = {https://eprint.iacr.org/2014/961} }