参考资料：
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]测试发现，\(m\)越大这种方法就越容易规约出目标向量，但是这种算法实际效果并不好，在参考资料2中提及了另外一种通过Kannan嵌入法求解LWE的方法，论文中提及算法如下：
其中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])
B = block_matrix(ZZ, 2, 1, [[A.transpose()], [q]])
B_HNF = B.hermite_form(include_zero_rows=False)
L = block_matrix(ZZ, 2, 2, [[B_HNF, 0], [matrix(b), 1]])
res = L.LLL()[0]
if res[-1] == -1:
e = -vector(res[:-1])
else:
e = vector(res[:-1])
cvp = vector(b) - e
AA = matrix(Zmod(q), A)
cvp = vector(Zmod(q), cvp)
s = AA.solve_right(cvp)求解出的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]获得两矩阵之后只需要通过如下计算就可以得到商环\(R\)中多项式\(g(x)\cdot h(x)\)的矩阵表示：
$$
(b_0,b_1,b_2,\cdots,b_{n-1})\pmb{M}_L\pmb{M}_R=(s_0,s_1,\cdots,s_{n-1})
$$
其中：
$$
\begin{aligned}
&\pmb{M}_L=\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)\\
&\pmb{M}_R=\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)
\end{aligned}
$$
事实上在sage中可以通过商环多项式的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{b},\pmb{s},\pmb{e}\)分别为\(b(x),s(x),e(x)\)的系数（行）向量.
以NSSRound#18 Basic-New Year Ring2 | NSSCTF为例：
加密代码如下：
from Crypto.Util.number import *
from random import *
from secret import flag
p = getPrime(128)
n = 64
assert len(flag) < n
PRp.<x> = PolynomialRing(Zmod(p))
f = x^n+2*x^3+0*x^2+2*x+4 #welcome to 2024!
PR = PRp.quo(f)
assert f.is_irreducible()
A = [randint(0, p) for i in range(n)]
E = [randint(-4, 4) for i in range(n)]
S = [ord(flag[i]) for i in range(len(flag))]
B = PR(A)*PR(S)+PR(E)
print(A)
print(B.list())
print(p)
#[...]
#[...]
#p = 171384865635734387982308861436753436427可以看到这很显然是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)测试发现对于任意一个方阵\(\pmb{M}’\)，\(\left(\begin{matrix}\pmb{M}’\\q\pmb{I}\end{matrix}\right)\)的HNF（去除所有0向量）都是单位矩阵，所以对于上述矩阵\(\pmb{M}\)，我们并不能通过求矩阵\(\left(\begin{matrix}\pmb{M}\\q\pmb{I}\end{matrix}\right)\)的HNF来减小格的规模，所以要优化求解效率的话只能借助效率更高的规约算法（例如flatter）了。