Continuous-Source Fuzzy Extractors: Source uncertainty and insecurity
| Autor: | Lowen Peng, Benjamin Fuller |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
021110 strategic defence & security studies Euclidean space Discrete space 0211 other engineering and technologies 020206 networking & telecommunications Hamming distance 02 engineering and technology Fuzzy logic Euclidean distance Metric space 0202 electrical engineering electronic engineering information engineering Entropy (information theory) Impossibility Computer Science::Cryptography and Security Mathematics |
| Zdroj: | ISIT |
| DOI: | 10.1109/isit.2019.8849421 |
| Popis: | 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 ${\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.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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|