适用于环- LWE的LWE门

Question

在Micciancio和Peikert的格子的陷阱:更简单，更紧，更快，更小一文中，他们给出了关于LWE陷阱存在性的定理。

定理5.1:有一个算法\mathsf{GenTrap}(1^n,1^m,q)，给定任何n\geq 1, q\geq 2和m=\mathcal{O}(n\log q)，输出一个矩阵\mathbf{A}\in\mathbb{Z}^{n\times m}_q和一个陷阱门\mathbf{R}，这样：

1. \mathbf{A}与一致选择的矩阵是不可区分的；
2. 有一个算法\mathsf{Invert}，给定\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e} (有\mathbf{s}\in\mathbb{Z}^{n}_q、\mathbf{e}\in\mathbb{Z}^m和||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q}))和陷阱\mathbf{R}，输出\mathbf{s}和\mathbf{e}.

他们提到，论文中的结果可以直接适用于环的设置(环-LWE)，然而，他们没有给出细节。在环的设置中，与这一结果相等的结果是什么？

Answer 1

与普通矩阵不同，类似的矩阵(但更大)：

+a -h -g -f -e -d -c -b
+b +a -h -g -f -e -d -c
+c +b +a -h -g -f -e -d
+d +c +b +a -h -g -f -e
+e +d +c +b +a -h -g -f
+f +e +d +c +b +a -h -g
+g +f +e +d +c +b +a -h
+h +g +f +e +d +c +b +a

哪一种方法可以推导出它的等价性，并将其相乘成一个用X^8+1表示的多项式。在这里，多项式是“环”。

而不是n x m的平面矩阵，而是用多项式的1 x 2矩阵。

注:矩阵表示多项式环与普通矩阵的算术区别在于前者在乘法上是可交换的，而后者则不是。