前言·

上次在用格解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=bAx+e = b

AA是矩阵，x,e,bx, e, b是向量，其实跟LWE类似；e是很短的向量，即e中每个元素都很小；现知道A和b，要求x、e，那么可以构造一个块矩阵：

L=[Ab0β]L = \begin{bmatrix} A & b \\ 0 & \beta \\ \end{bmatrix}

其中β\beta是参数（个人感觉取个e中元素的平均值应该可以？）；然后CVP的问题就可以转换为：

[Ab0β][−x1]=[b−Axβ]=[eβ]\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,β)T(e, \beta)^T很短的话，(e,β)T(e, \beta)^T就大概率是LL中的一个最短向量；参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 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)

上面是方阵版本的，其实m∗nm*n的也可以做，改了一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# Sage
DEBUG = False
m = 44
n = 55
p = 2^5
q = 2^10

def errorV():
  return vector(ZZ, [1 - randrange(3) for _ in range(n)])

def vecM():
  return vector(ZZ, [p//2 - randrange(p) for _ in range(m)])

def vecN():
  return vector(ZZ, [p//2 - randrange(p) for _ in range(n)])

def matrixMn():
  mt = matrix(ZZ, [[q//2 - randrange(q) for _ in range(n)] for _ in range(m)])
  return mt

A = matrixMn()
e = errorV()
x = vecM()
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(m)]).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)

结语·

实测如果AA是随机的格（mod q）的话，维度nn是1000能解（没测上限），但是nn越大的话耗时会越长（1000的话用了20分钟）

但很遗憾NN很大（100好像就不行了）的话对NTRU的格没啥作用，估计和NTRU格的gap在λ0\lambda_0到λN\lambda_N很小有关？（PS：NTRU的格维度是2N2N）