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)
- 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
-
CC BY