Continuous-Source Fuzzy Extractors: Source uncertainty and insecurity
Continuous-Source Fuzzy Extractors: Source uncertainty and insecurity
复制标题
DOI：
10.1109/isit.2019.8849421
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Benjamin Fuller;Lowen Peng
中科院分区：
文献类型：
--
作者：
Benjamin Fuller;Lowen Peng
模糊提取器（Dodis等人，Eurocrypt 2004）将高熵源的重复噪声读数转换为相同的均匀分布的密钥。模糊提取器的功能在提供接近源的原始阅读的值时输出密钥。安全性的一个必要条件，称为模糊最小熵，是噪声源的每个值球的概率是小的。许多噪声源最好使用连续度量空间建模。为了构建连续源模糊提取器，先前的工作假设系统设计者具有良好的分布模型（Verbitskiy等人，IEEE TIFS 2010）。然而，仅仅从高熵分布中采样是不可能建立一个精确的模型的，模型的不准确性可能是一个严重的问题。我们证明了一个家庭的连续分布${\mathcal{W}}$是不可能的安全。没有为${\mathcal{W}}$设计的模糊提取器从${\mathcal{W}}$的平均元素中提取有意义的键。这个不可能的结果是尽管{\mathcal{W}}$中的每个元素$W \具有高模糊最小熵的事实。对于用于构造大多数模糊抽取器的安全草图，我们给出了一个定性上更强的否定结果，我们的结果是关于欧氏度量的，并且本质上是信息论的。据我们所知，所有连续源模糊提取器都证明了信息论安全性。Fuller，Reyzin和Smith在配备Hamming度量的离散度量空间中给出了类似的否定结果（Asiacrypt 2016）。连续欧几里得空间需要新的技术。
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.