基本环LWE密钥协议失效概率的计算

Question

这是基本的未经认证的基于LWE的Diffie-Hellman密钥交换，基于Peikert的Ring-LWE KEM：(来自BCNS15)

• Alice和Bob共享从a随机抽取的公共多项式\chi，以及具有标准偏差\sigma的已知错误分布D5。
• Alice根据分布s_A, e_A \in R_q生成随机小秘密多项式\chi，计算b_A = a \cdot s_A + e_A并发送给Bob。
• 根据分布s_B, e_B \in R_q生成随机小秘密多项式\chi，计算b_B = a \cdot s_B + e_B并发送给Alice。
• 艾丽斯计算k_A = s_A \cdot b_B = a \cdot s_A \cdot s_B + s_A \cdot e_B
• 鲍勃计算k_B = s_B \cdot b_A = a \cdot s_A \cdot s_B + s_B \cdot e_A

除错误项外，k_A和k_B大致相等。因此，Alice和Bob使用协调函数rec(.)因此rec(k_A) = rec(k_B) = K是常见的共享秘密。

基本协调方案(来自BCNS15)将多项式的每个系数舍入0或q/2，q/2被视为1，因此K是一个n-bit字符串。BCNS15说这个方案有1/2^{10}的失败概率。这是怎么计算出来的？

以下是我一直在尝试的一般方法：

• 为了成功地进行密钥交换，必须使用|k_A[i] - k_B[i]| < \delta For i \in \{0, 1, \cdots, n-1\}，其中k_A[i]和k_B[i]分别表示多项式k_A和k_B的i-th系数，而\delta是协调方案的容错性。
• 在这种情况下，k_A - k_B = s_A \cdot e_B - s_B \cdot e_A和\delta = q/4
• 设p是某些i的|k_A[i] - k_B[i]| > \delta的概率，即在解码K的任何一点时出错的概率。然后，小1 - (1 - p)^n \approx np的总失效概率为p。
• 假设错误分布\chi有一个支持[-t\sigma, +t\sigma]，其中t是由采样器实现的精度决定的一个因素。那么，s_A \cdot e_B或s_B \cdot e_A的任何系数的最大可能绝对值是nt^2\sigma^2，所以我们必须有2nt^2\sigma^2 < q/4或q > 8nt^2\sigma^2。

Answer 1

一个具体的解决方案是显式地计算每个系数的分布。在这个特殊的环中，如果e和S的系数分布是对称的，则这可以被计算为系数乘积分布的2n倍卷积。这里有一个例子(由于四舍五入造成了一些复杂)：

https://github.com/pq-crystals/security-estimates/blob/master/Kyber_failure.py

更多的数学方法(可能会给出更宽松的限制)包括研究矩生成函数。这可以很好地抽象化使用亚高斯随机变量理论。