Towards a Ring Analogue of the Leftover Hash Lemma
Towards a Ring Analogue of the Leftover Hash Lemma
复制标题
DOI：
10.1515/jmc-2020-0076
复制
发表时间：
2020-11
影响因子：
1.2
通讯作者：
Dana Dachman-Soled;Huijing Gong;Mukul Kulkarni;Aria Shahverdi
中科院分区：
文献类型：
--
作者：
Dana Dachman-Soled;Huijing Gong;Mukul Kulkarni;Aria Shahverdi
摘要剩余哈希引理（LHL）用于分析各种基于格的密码系统，如Regev和Dual-Regev加密方案以及它们的防泄漏对应物。当环远离字段时，LHL在环设置中不成立，这对于有效的密码系统来说是典型的。Lyubashevsky等人（Eurocrypt ' 13）证明了一个“正则引理”，它可以用来代替LHL，但只适用于高斯输入。这与LHL相反，LHL适用于输入来自任何高最小熵分布的情况。我们的工作提出了一种将Lyubashevsky等人的“正则引理”推广到某些条件分布的方法。我们假设输入从离散高斯分布中采样，并考虑在输入上给定侧通道泄漏的诱导分布。我们给出了我们方法的三个实例，证明了正则引理适用于三个自然条件分布。
Abstract The leftover hash lemma (LHL) is used in the analysis of various lattice-based cryptosystems, such as the Regev and Dual-Regev encryption schemes as well as their leakage-resilient counterparts. The LHL does not hold in the ring setting, when the ring is far from a field, which is typical for efficient cryptosystems. Lyubashevsky et al. (Eurocrypt ’13) proved a “regularity lemma,” which can be used instead of the LHL, but applies only for Gaussian inputs. This is in contrast to the LHL, which applies when the input is drawn from any high min-entropy distribution. Our work presents an approach for generalizing the “regularity lemma” of Lyubashevsky et al. to certain conditional distributions. We assume the input was sampled from a discrete Gaussian distribution and consider the induced distribution, given side-channel leakage on the input. We present three instantiations of our approach, proving that the regularity lemma holds for three natural conditional distributions.