Replacing Probability Distributions in Security Games via Hellinger Distance
Replacing Probability Distributions in Security Games via Hellinger Distance
复制标题
DOI：
10.4230/lipics.itc.2021.17
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kenji Yasunaga
中科院分区：
文献类型：
--
作者：
Kenji Yasunaga
密码原语的安全性通常通过假设“理想”概率分布来证明。我们需要用现实世界系统中近似的“真实”分布来替换它们，而不损失安全级别。我们证明海林格距离对于这个问题很有用，而统计距离主要用于密码学文献中。首先，我们证明，为了保持给定安全博弈的 λ 位安全性，对于 Hellinger 距离来说，接近理想分布的 2 − λ/ 2 就足够了，而统计距离通常需要 2 − λ 。结果可以通过 Micciincio 和 Walter 的位安全框架应用于搜索和决策原语 (Eurocrypt 2018)。我们还表明，当距离很小时，Hellinger 距离比 max-log 距离给出更严格的接近度评估。最后，我们证明剩余的哈希引理可以增强到 Hellinger 距离。也就是说，散列函数的通用族提供了强大的随机性提取器，具有海灵格距离的最佳熵损失。根据结果，随机性提取器中的 λ 位熵损失足以保护 λ 位安全性。目前基于统计距离的理解是，2 λ 位的熵损失是必要的。
Security of cryptographic primitives is usually proved by assuming “ideal” probability distributions. We need to replace them with approximated “real” distributions in the real-world systems without losing the security level. We demonstrate that the Hellinger distance is useful for this problem, while the statistical distance is mainly used in the cryptographic literature. First, we show that for preserving λ -bit security of a given security game, the closeness of 2 − λ/ 2 to the ideal distribution is sufficient for the Hellinger distance, whereas 2 − λ is generally required for the statistical distance. The result can be applied to both search and decision primitives through the bit security framework of Micciancio and Walter (Eurocrypt 2018). We also show that the Hellinger distance gives a tighter evaluation of closeness than the max-log distance when the distance is small. Finally, we show that the leftover hash lemma can be strengthened to the Hellinger distance. Namely, a universal family of hash functions gives a strong randomness extractor with optimal entropy loss for the Hellinger distance. Based on the results, a λ -bit entropy loss in randomness extractors is sufficient for preserving λ -bit security. The current understanding based on the statistical distance is that a 2 λ -bit entropy loss is necessary.