Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / fuzzy extractors; secure sketches; information-theory; authentication; error-tolerance; error-correcting codes

Date: received 14 May 2018, last revised 7 Sep 2018

Contact author: benjamin fuller at uconn edu

Available format(s): PDF | BibTeX Citation

Version: 20180907:152844 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]