When Are Fuzzy Extractors Possible?
When Are Fuzzy Extractors Possible?
复制标题
DOI：
10.1109/tit.2020.2984751
复制
发表时间：
2016-12
影响因子：
2.5
通讯作者：
Benjamin Fuller;Leonid Reyzin;Adam D. Smith
中科院分区：
文献类型：
--
作者：
Benjamin Fuller;Leonid Reyzin;Adam D. Smith
模糊提取器（Dodis 等人，SIAM J.Computing 2008）将高熵秘密的重复噪声读数转换为相同的均匀分布密钥。密钥安全性的最低条件是猜测与秘密相似的值的难度，因为模糊提取器将这种猜测转换为密钥。我们用一个称为模糊最小熵的新概念来量化这个属性。我们问：模糊最小熵足以构建模糊提取器吗？我们针对不同的设置提供两种答案。 1) 如果为构造提供了定义噪声源的概率分布 $W$ 的描述，则模糊最小熵是从 $W$ 中提取信息论密钥的充分条件。 2）一个更雄心勃勃的目标是设计一个适用于所有可能来源的单一提取器。这个更雄心勃勃的目标是不可能的：存在一系列具有高模糊最小熵的源，没有一个模糊提取器是安全的。这在三种设置中是正确的：a）对于标准模糊提取器，b）对于有时允许错误的模糊提取器，c）以及对于安全草图，这是大多数模糊提取器构造的主要成分。
Fuzzy extractors (Dodis et al., SIAM J. Computing 2008) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key. We quantify this property in a new notion called fuzzy min-entropy. We ask: is fuzzy min-entropy sufficient to build fuzzy extractors? We provide two answers for different settings. 1) If the construction is provided a description of the probability distribution $W$ that defines the noisy source then fuzzy min-entropy is a sufficient condition for information-theoretic key extraction from $W$ . 2) A more ambitious goal is to design a single extractor that works for all possible sources. This more ambitious goal is impossible: there is a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. This is true in three settings: a) for standard fuzzy extractors, b) for fuzzy extractors that are allowed to sometimes be wrong, c) and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.