Computational fuzzy extractors
Computational fuzzy extractors
复制标题
计算模糊提取器
DOI：
10.1016/j.ic.2020.104602
复制
发表时间：
2020
影响因子：
1
通讯作者：
Reyzin, Leonid
中科院分区：
文献类型：
--
作者：
Fuller, Benjamin;Meng, Xianrui;Reyzin, Leonid
模糊抽取器从嘈杂的信源中获得强密钥。它们的安全性通常被定义为信息理论，在已知的否定结果、存在结构和多项式时间结构之间存在差距。我们问，使用计算安全能否弥合这些差距。·否定的结果：模糊抽取器中的噪声容限通常是通过一个称为安全草图的信息协调组件来实现的。我们证明了使用伪熵定义的安全草图(Hçstad等人，SIAM J.Comput.·正结果：我们的否定结果可以通过直接构造和分析计算性模糊抽取器来避免。我们修改了码偏移量结构(Juels和Wtenberg，CCS 1999)以使用随机线性码。安全性基于错误学习问题，当噪声源是均匀的或符号固定的(即，每个维度要么是一致的，要么是固定的)时，安全是成立的。
Fuzzy extractors derive strong keys from noisy sources. Their security is usually defined information-theoretically, with gaps between known negative results, existential constructions, and polynomial-time constructions. We ask whether using computational security can close these gaps. We show the following:•Negative result:Noise tolerance in fuzzy extractors is usually achieved using an information reconciliation component called asecure sketch.We show that secure sketches defined using pseudoentropy (Håstad et al., SIAM J. Comput. 1999) instead of information-theoretic security are still subject to upper bounds from coding theory.•Positive result:We show that our negative result can be avoided by constructing and analyzing a computational fuzzy extractor directly. We modify the code-offset construction (Juels and Wattenberg, CCS 1999) to use random linear codes. Security is based on the Learning with Errors problem and holds when the noisy source is uniform or symbol-fixing (that is, each dimension is either uniform or fixed).