LWE加密错误

Question

在使用错误加密方案的学习中(例如在Kyber方案中)。有两个矢量：

u = r^t A + e_2

和v= r^t * pk + e_3 + \lfloor \frac{q}{2}\rceil m这样的pk = As +e_1。

我的问题是，如果省略e_3和v = r^t * pk + \lfloor \frac{q}{2}\rceil m ，加密是否仍然安全。

据我所知(以及我目前的理解水平)，答案是肯定的，因为根本的问题是(Mod/Ring/Primal) LWE问题。

Answer 1

不，它不再安全了。Kyber是一个名为"LPR加密“的密码系统的实例化。它的公钥是零(A, As + e_1)的LWE加密。加密通过计算进行

1. u = r^tA + e_2 (so u^t = A^t r + e_2^t)，一种在矩阵A^t (与A明显相关的)下为零的LWE加密，然后
2. v = r^t (As + e_1) + (q/2)m + e_3，一个零的LWE加密使用随机垫(As + e_1)。

为了维护安全，你先

1. 在As + e_1是伪随机的假设下，你可以用一个一致随机的字符串来代替它。
2. 认为v现在是形式\langle r,pk\rangle + (q/2)m+e_3，即是m的LWE加密。您还需要进一步论证，发布(rA^t + e_2)并不会损害安全性，但是暂时忽略这一点(不需要显示建议的不安全性)。

根据您的修改，这第二步将不再起作用，因为\langle r, pk\rangle + (q/2)m不是LWE加密(而是“无噪音LWE加密”)。众所周知，无噪音的LWE加密容易受到简单的攻击，比如使用高斯消除。因此，您可以通过查看(pk, r^tpk + (q/2)m)作为m的无噪音LWE加密，并在此设置中运行标准攻击)来攻击您的密码系统。

我到达上述攻击的方式很简单--看看证据，看看哪一步不再起作用，看看你能不能攻击它。我强烈鼓励您以这种方式思考问题，而不是简单地“它使用LWE，所以它是安全的”，因为这样的推理在密码学中几乎是不合理的。