Robustly reusable fuzzy extractor with imperfect randomness

Cui Nan; Liu Shengli; Gu Dawu; Weng Jian

摘要

Fuzzy extractor (FE) extracts and reproduces a uniform string from a fuzzy source. Robustly reusable fuzzy extractor (rrFE) considers reusability and robustness simultaneously. Reusability of rrFE allows multiple extractions of pseudorandom strings from the same source and robustness detects active attacks. To achieve reusability and robustness, the existing constructions of rrFE make heavy use of perfect random coins (which are uniformly distributed and independent of each other), besides the fuzzy source. However, efficiently sampling unbiased random bits only exists in the ideal world. In this paper, we show how to construct rrFE resorting to imperfect randomness (non-uniform but of high entropy), which is easy to sample in practice. We propose two generic constructions of rrFE in the CRS model, with one construction dealing with perfect randomness and the other dealing with imperfect randomness. We also present two instantiations of rrFE from the DDH and LPN assumptions working with perfect randomness, and another two instantiations of rrFE from DDH and LPN working with imperfect randomness. All instantiations support linear fraction of errors between samples of the fuzzy source. Our DDH-based rrFE (both rrFE with perfect randomness and rrFE with imperfect randomness) are the first tightly secure rrFEs in the standard model, i.e., the reusability and robustness are tightly reduced to the DDH assumption. Compared with the DDH-based rrFE scheme in PKC2019 by Wen et al., our rrFE enjoys tighter security, better efficiency, and support of usage of imperfect randomness. Our LPN-based rrFE (both rrFE with perfect randomness and rrFE with imperfect randomness) are the first rrFEs from the LPN assumption in the standard model.

机译：模糊提取器（FE）从模糊源中提取并再现均匀的串。强大可重复使用的模糊提取器（RRFE）同时考虑可重用性和鲁棒性。 RRFE的可重用性允许从相同的源和鲁棒性检测到激活攻击的多个提取伪随机串。为了实现可重用性和鲁棒性，除了模糊源之外，RRFE的现有结构大量使用完美的随机硬币（其均匀分布并彼此独立）。然而，有效地采样无偏见的随机位仅存在于理想世界中。在本文中，我们展示了如何构建RRFE诉诸于不完美的随机性（不均匀但高熵），这易于在实践中进行采样。我们提出了两个在CRS模型中的RRFE通用结构，一个建筑处理完美的随机性和其他处理不完美随机性的施工。我们还从DDH和LPN假设中展示了RRFE的两种实例化，与完美的随机性，以及来自DDH和LPN的另外两个实例的RRFE与不完美随机性一起使用。所有实例化支持模糊源的样本之间的线性分数。基于DDH的RRFE（具有完美随机性和具有不完美随机性的RRFE的RRFE）是标准模型中的第一个紧密安全的RRFE，即，可重用性和鲁棒性紧密减少到DDH假设。与Wen等人的PKC2019中的基于DDH的RRFE方案相比，我们的RRFE享有更紧密的安全性，更好的效率和对不完美随机性的支持。我们基于LPN的RRFE（具有完美随机性和具有不完美随机性的RRFE的RRFE）是标准模型中LPN假设的第一个RRFE。

Robustly reusable fuzzy extractor with imperfect randomness

摘要

著录项

相关主题

期刊订阅