聚LWE和环形LWE有什么区别？

Question

我经常被Poly和Ring-LWE搞糊涂，总是认为它们是同一件事的不同名称。在一些文献中，Poly是圆环LWE的简化版本？有什么关系？

Answer 1

一个主要的区别是在环LWE中，环R是一个数域K的整数\mathcal{O}_K的全环，而在Poly中它是某些不可约f(x)的形式R=\mathbb{Z}[x]/f(x)，这个环是(同构于)数域K=\mathbb{Q}(x)/f(x)的一个阶，但可能不是整数的满环。

另一个重要的区别是，在环LWE中，(无噪声)乘积a_i \cdot s \in R^\vee_q属于环的对偶(分数)理想R^\vee (模q)，而在聚LWE中，所有a_i, s, a_i \cdot s都属于R_q。虽然后者在技术上更简单，但使用双重形式有几个优点。

第三个重要的区别是，在环LWE中，我们通常考虑正则嵌入中本质上是球面的误差分布，而在Poly中，我们通常考虑系数为独立的小值(如高斯)-such误差多项式的误差多项式在正则嵌入中可能是相当“斜”的。同样，后一种选择在技术上一开始看起来更简单，但在密码应用中，前者有一些优点(特别是与“双”形式的环形LWE结合在一起)，即随着错误的积累而更加严格地控制它们。

这两个问题在形式上可以联系起来，在误差分布上有一定的爆破和失真。有关最新信息，请参见https://eprint.iacr.org/2019/878。