LWE
参考资料：
LWE以及RLWE
LWE
设\(n,m\)以及\(q\)为正整数（其中\(q\)一般为质数），\(\chi\)为一个\(\mathbb{Z}^{m}\)上的概率分布，并设\(\pmb{s}\in(\mathbb{Z}/q\mathbb{Z})^n\)是一条“秘密向量”，在\((\mathbb{Z}/q\mathbb{Z})^{m\times n}\)上均匀随机选取矩阵\(\pmb{A}\)，并在\(\mathbb{Z}^m\)上选取一个分布服从\(\chi\)的小向量\(\pmb{e}\)作为噪声，计算： \[ \pmb{b}\equiv \pmb{A}\pmb{s}+\pmb{e}\pmod{q} \] 并给出\((\pmb{A},\pmb{b})\)，那么一般的LWE问题（一般称为搜索LWE，Search-LWE）即为给定\((\pmb{A},\pmb{b})\)，还原出\(\pmb{s}\).
环LWE（Ring-LWE，RLWE）
设\(n\)为一个大于等于\(1\)的整数，\(q\)为一质数，得到商环： \[ R=\frac{\mathbb{Z}[x]}{(x^n+1)},R_q=\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{(x^n+1)} \] 而\(\chi\)为\(R\)上的一个概率分布，选取随机秘密多项式\(s(x)\in R_q\)以及随机多项式\(A(x)\in R_q\)，并在\(R_q\)上选取一个分布服从\(\chi\)的多项式\(e\)作为噪声，计算： \[ b(x)=A(x)s(x)+e(x) \] 搜索RLWE问题即为给出若干组\((A_i(x),b_i(x))\)，并从中恢复出\(s(x)\).
通过格方法求解LWE及其变种
LWE
观察LWE的问题形式： \[
\pmb{b}\equiv \pmb{A}\pmb{s}+\pmb{e}\pmod{q}
\] 作为攻击者，我们要通过已知的\(\pmb{A},\pmb{b}\)来恢复\(\pmb{s}\)，且\(\pmb{e}\)是一个未知的小向量，显然这是一个CVP问题，首先将原问题转换为： \[
\pmb{b}+q\pmb{k}=\pmb{A}\pmb{s}+\pmb{e}
\] 即： \[
q\pmb{k}-\pmb{A}\pmb{s}+\pmb{b}=\pmb{e}
\] 显然可以构造出如下格基： \[
\pmb{B} = \left(\begin{matrix}
q\pmb{I}_m&0&0\\
-\pmb{A}^T&\pmb{I}_n&0\\
\pmb{b}&0&1
\end{matrix}\right)
\] （实际上是利用Kannan嵌入法来将CVP转换为SVP求解）。对上述格基有如下关系： \[
(\pmb{k}^{T},\pmb{s}^{T},1)\pmb{B}=(\pmb{e}^{T},\pmb{s}^{T},1)
\] 通过格基规约算法（如LLL，BKZ等）即可得到短向量\((\pmb{e}^{T},\pmb{s}^{T},1)\)，sage实现如下： q = ...
L = block_matrix(ZZ, 3, 3, [[q, 0, 0], [-A.transpose(), 1, 0], [matrix(b), 0, 1]])
res = L.LLL()
v = res[0]
其中HNF是Hermite Normal Form（埃尔米特标准型）的缩写，在之前的讨论中我们构造出的格基大小为\((n+m+1)\times(n+m+1)\)，当\(n,m\)都比较大的时候如果想要规约出目标向量是比较困难的，即使可以规约出目标向量也需要比较长时间，如果利用这种算法那么得到的格基大小将是\((m+1)\times(m+1)\)，会相对较容易规约出目标向量，该目标向量会包含误差向量\(\pmb{e}\)，该算法的sage实现如下：
m = len(b[0]) |
求解出的s即为我们所需要的。经测试发现，相较于之前讨论得到的算法这种算法求解LWE的效果更好.
RLWE
在通过格来求解RLWE之前，需要了解商环中多项式乘法的矩阵表示（事实上商环中多项式乘法的矩阵表示在NTRU | Triode Field中有简单提及，在这里作详细说明）：
设一商环\(R=\mathbb{Z}[x]/f(x)\)（其中\(f(x)\)为\(\mathbb{Z}\)中的一个首一\(n\)次多项式），设\(f(x)\)的系数分别为：\((a_0,a_1,\cdots,a_{n-1},1)\)，那么很显然可以知道在该商环中有： \[
x^{n}=-(a_0+a_1x+\cdots+a_{n-1}x^{n-1})
\] 那么对于该商环中任意两多项式： \[
\begin{aligned}
g(x)=b_0+b_1x+b_2x^2+\cdots+b_{n-1}x^{n-1}\\h(x)=c_0+c_1x+c_2x^2+\cdots+c_{n-1}x^{n-1}
\end{aligned}
\] 设对\(\mathbb{Z}[x]\)中有\(g(x)\cdot h(x)=k_0+k_1x+k_2x^2+\cdots+k_{2n-2}x^{2n-2}\)，则有如下关系： \[
k_{i}=\sum_{s+t=i}b_sc_t
\] 那么可以得到上述多项式乘法的矩阵表示： \[
(b_0,b_1,b_2,\cdots,b_{n-1})
\left(\begin{matrix}
c_0&c_1&c_2&\cdots&c_{n-1}\\
&c_0&c_1&\cdots&c_{n-2}&c_{n-1}\\
&&c_0&\cdots&c_{n-3}&c_{n-2}&c_{n-1}\\
&&&\ddots&\vdots&\vdots&\vdots&\ddots\\
&&&&c_{0}&c_1&c_2&\cdots&c_{n-1}
\end{matrix}\right)=(k_0,k_1,k_2,\cdots,k_{2n-2})
\] 但是这只是对一般的多项式乘法生效的，对于商环\(R\)中的多项式，则还需要对\((k_0,k_1,\cdots,k_{2n-2})\)进行进一步处理，已知在\(R\)中有： \[
x^{n}=-(a_0+a_1x+\cdots+a_{n-1}x^{n-1})
\] 所以对\(x^{n+1}\)，有： \[
\begin{aligned}
x^{n+1}&=-(a_0x+a_1x^2+\cdots+a_{n-2}x^{n-1}+a_{n-1}x^{n})\\
&=-[a_0x+a_1x^2+\cdots+a_{n-2}x^{n-1}-a_{n-1}(a_0+a_1x+\cdots+a_{n-1}x^{n-1})]
\end{aligned}
\] 展开就可以计算出各项系数，同理，有： \[
\begin{aligned}
x^{n+2}&=-(a_0x^2+a_1x^3+\cdots+a_{n-2}x^{n}+a_{n-1}x^{n+1})\\
\end{aligned}
\] 将先前求出的\(x^{n+1}\)与\(x^n\)代进去即可求出\(x^{n+2}\)，以此类推可以求出\(x^{n+3},x^{n+4},\cdots,x^{2n-2}\)在\(R\)中的表示，设在\(R\)中\(g(x)\cdot h(x)=s_0+s_1x+s_2x^2+\cdots+s_{n-1}x^{n-1}\)，有如下关系： \[
(k_0,k_1,k_2,\cdots,k_{2n-2})
\left(\begin{matrix}
1&&&\\
&1&&\\
&&\ddots\\
&&&1\\
t_{n,0}&t_{n,1}&\cdots&t_{n,n-1}\\
t_{n+1,0}&t_{n+1,1}&\cdots&t_{n+1,n-1}\\
\vdots&\vdots&&\vdots\\
t_{2n-2,0}&t_{2n-2,1}&\cdots&t_{2n-2,n-1}
\end{matrix}\right)=(s_0,s_1,\cdots,s_{n-1})
\] 其中\(t_{n,0}\)到\(t_{2n-2,n-1}\)需要通过前面所说步骤进行计算，具体代码如下（参考了2024-NSSCTF-Round-18-Basic-wp-crypto | 糖醋小鸡块的blog中New Year Ring 3的代码）： MR = Matrix(ZZ, 2*n-1, n)
for i in range(n):
MR[i, i] = 1
for i in range(n, 2*n-1):
for j in range(i-n, n):
MR[i, j] = -a[j-(i-n)]
tmp = vector(ZZ, n*[0])
for j in range(i-n):
tmp2 = -a[n-1-j] * vector(ZZ, MR[i-j-1])
tmp += tmp2
for j in range(n):
MR[i, j] += tmp[j]matrix()方法来获得多项式\(g(x)\)的乘法矩阵\(\pmb{M}=\pmb{M}_L\pmb{M}_R\)，在获得这个矩阵之后，RLWE问题就可以转换为一般的LWE问题了： \[
b(x)=A(x)s(x)+e(x)\Leftrightarrow\pmb{b}=\pmb{s}\pmb{M}+\pmb{e}
\] 其中\(\pmb{}\)\(\pmb{b},\pmb{s},\pmb{e}\)分别为\(b(x),s(x),e(x)\)的系数（行）向量.
以NSSRound#18 Basic-New Year Ring2 | NSSCTF为例：
加密代码如下：
from Crypto.Util.number import * |
可以看到这很显然是RLWE问题，这里的环是： \[
R=\frac{\mathbb{Z}_p[x]}{x^{64}+2x^3+2x+4}
\] 可以通过如下代码构造格并进行规约获得目标向量并获得flag： A = [...]
b = [...]
p = 171384865635734387982308861436753436427
n = 64
PR.<x> = ZZ[]
f = x^n + 2*x^3 + 2*x + 4
R = PR.quotient(f)
g = R(A)
M = g.matrix()
L = block_matrix(ZZ, 3, 3, [[p, 0, 0], [M, 1, 0], [matrix(b), 0, 1]])
res = L.LLL()
flag = ""
for i in range(n, 2*n):
if res[i, i] != 0:
flag += chr(abs(res[0, i]))
print(flag)