### Continuous-Source Fuzzy Extractors: Source uncertainty and security

Benjamin Fuller and Lowen Peng

##### Abstract

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy source into the same uniformly distributed key. The functionality of a fuzzy extractor outputs the key when provided with a value close to the original reading of the source. A necessary condition for security, called fuzzy min-entropy, is that the probability of every ball of values of the noisy source is small. Many noisy sources are best modeled using continuous metric spaces. To build continuous-source fuzzy extractors, prior work assumes that the system designer has a good model of the distribution (Verbitskiy et al., IEEE TIFS 2010). However, it is impossible to build an accurate model of a high entropy distribution just by sampling from the distribution. Model inaccuracy may be a serious problem. We demonstrate a family of continuous distributions V that is impossible to secure. No fuzzy extractor designed for V extracts a meaningful key from an average element of V. This impossibility result is despite the fact that each element W in V has high fuzzy min-entropy. We show a qualitatively stronger negative result for secure sketches, which are used to construct most fuzzy extractors. Our results are for the Euclidean metric and are information-theoretic in nature. To the best of our knowledge all continuous-source fuzzy extractors argue information-theoretic security. Fuller, Reyzin, and Smith showed comparable negative results for a discrete metric space equipped with the Hamming metric (Asiacrypt 2016). Continuous Euclidean space necessitates new techniques.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.2019 IEEE Symposium on Information theory
Keywords
fuzzy extractorssecure sketchesinformation-theoryauthenticationerror-toleranceerror-correcting codes
Contact author(s)
benjamin fuller @ uconn edu
History
2019-07-12: last of 3 revisions
See all versions
Short URL
https://ia.cr/2018/461

CC BY

BibTeX

@misc{cryptoeprint:2018/461,
author = {Benjamin Fuller and Lowen Peng},
title = {Continuous-Source Fuzzy Extractors: Source uncertainty and security},
howpublished = {Cryptology ePrint Archive, Paper 2018/461},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/461}},
url = {https://eprint.iacr.org/2018/461}
}

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