You are looking at a specific version 20180907:152844 of this paper. See the latest version.

Paper 2018/461

When are Continuous-Source Fuzzy Extractors Possible?

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. Noisy sources are measured from physical phenomena many of which 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. We show that model inaccuracy may be a serious problem. We demonstrate a family of continuous distributions $\mathcal{W}$ that is impossible to secure. No fuzzy extractor designed for $\mathcal{W}$ extracts a meaningful key from an average element of $\mathcal{W}$. This impossibility result is despite the fact that each element $W\in\mathcal{W}$ 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. Prior work of Fuller, Reyzin, and Smith showed comparable negative results for a discrete metric space equipped with the Hamming metric (Asiacrypt 2016). The geometry of Euclidean space necessitates new techniques.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
fuzzy extractorssecure sketchesinformation-theoryauthenticationerror-toleranceerror-correcting codes
Contact author(s)
benjamin fuller @ uconn edu
History
2019-07-12: last of 3 revisions
2018-05-21: received
See all versions
Short URL
https://ia.cr/2018/461
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.