前言
上次在用格解LWE——笔记里讲了一种用"Babai's Nearest Plane Algorithm"解SVP的方法/代码，这次发现了一种用"Embedding Technique"解的，即构造一个Embedding Lattice，然后解SVP。
这个方法是前几天在[1]里看到的，然后里面引的是[2]（但我没看懂这篇。。）
[1] Liu M, Wang X, Xu G, et al. Shortest Lattice Vectors in the Presence of Gaps[J]. IACR Cryptol. ePrint Arch., 2011, 2011: 139.
[2] R.Kannan, Minkowski's convex body theorem and integer programming. Mathematics of Operations Research,
12(3)(1987), pp.415-440.
正文
假设现在要解的问题是：
Ax+e = b
A是矩阵，x, e, b是向量，其实跟LWE类似；e是很短的向量，即e中每个元素都很小；现知道A和b，要求x、e，那么可以构造一个块矩阵：
L = \begin{bmatrix} A & b \\ 0 & \beta \\ \end{bmatrix}
其中\beta是参数（个人感觉取个e中元素的平均值应该可以？）；然后CVP的问题就可以转换为：
\begin{bmatrix} A & b \\ 0 & \beta \\ \end{bmatrix}
\begin{bmatrix} -x \\ 1 \\ \end{bmatrix}
=
\begin{bmatrix} b-Ax \\ \beta \\ \end{bmatrix}
=
\begin{bmatrix} e \\ \beta \\ \end{bmatrix}
所以当(e, \beta)^T很短的话，(e, \beta)^T就大概率是L中的一个最短向量；参考代码：
# Sage
DEBUG = False
# 200->30s ; 300->1m ; 500->3m ; 1000->20m
n = 10
p = 3
q = 2^20
def errorV():
return vector(ZZ, [1 - randrange(3) for _ in range(n)])
def smallV():
return vector(ZZ, [p//2 - randrange(p) for _ in range(n)])
def largeV():
return vector(ZZ, [q//2 - randrange(q) for _ in range(n)])
def largeM():
return matrix(ZZ, [[q//2 - randrange(q) for _ in range(n)] for _ in range(n)])
A = largeM()
e = errorV()
x = smallV()
b = x*A+e
if DEBUG:
print('A = \n%s' % A)
print('x = %s' % x)
print('b = %s' % b)
print('e = %s' % e)
z = matrix(ZZ, [0 for _ in range(n)]).transpose()
beta = matrix(ZZ, [1])
T = block_matrix([[A, z], [matrix(b), beta]])
if DEBUG:
print('T = \n%s' % T)
print('-----')
L = T.LLL()
print(L[0])
print(L[0][:n] == e)
结语
实测如果A是随机的格（mod q）的话，维度n是1000能解（没测上限），但是n越大的话耗时会越长（1000的话用了20分钟）
但很遗憾N很大（100好像就不行了）的话对NTRU的格没啥作用，估计和NTRU格的gap在\lambda_0到\lambda_N很小有关？（PS：NTRU的格维度是2N）
-
原文链接：https://tover.xyz/2021/09/22/CVP-to-SVP/
PS：Tover开博客了：https://tover.xyz/