1.Lattice(格) 基础

基于数学与计算机，现代密码学诞生。

1.1 Lattice

系统性的定义一下Lattice的话，那么我们可以说Lattice是R^n这个空间中的一个离散的、具有加法运算的子群（A discrete additive subgroup）。

结合可视化工具，这里给出辅助理解的图像：

结合向量空间的概念，不难理解**格（Lattice)与基（bases)**的概念

1.2 Lattice 的基本属性

1.2.1 Lattice 的密度

即可理解为对应维度的向量空间内球体内所含有的格点数和球体体积之比（或超球体）

1.2.2 最短距离 λ

将λ视为一个函数，λ1被定义为两格点间最小距离，推广至λn

诸多λ遵循偏序关系: $$ \lambda_1\leqslant\lambda_2\leqslant……\lambda_n-1\leqslant\lambda_n $$ 那么请注意到：取等条件：

选定笛卡尔坐标下的格

此时 $$ \lambda_1 =\lambda_2= …… =\lambda_n =1 $$

1.2.3 距离函数 μ（t,L）

注意到格是一个子群。

任取向量空间内一点，那么我们讨论距离这一点最近的一个格点，给出一些定义：

• 距离函数(Distance Function): μ（t,L），认为μ的本质为数量
• 点 t

$$ \mu (t, L)= \min_{x∈L} \left | t-x \right | $$

1.2.4 覆盖半径 μ（L)

类似地，我们认为t为动点，此时寻找μ的最大值。给出定义：

• 覆盖半径（Covering Radius): μ（L) $$ \mu (L)= \max_{x∈span(L)} μ(t,L) $$

对覆盖的理解：

以格点为圆心，不断扩大半径，可以容易地找到当各个圆刚好覆盖整个向量空间地时候，此时半径恰好为μ（L）。

这和Lattice 的Smoothing 高度相关。

1.3 Minkowski凸集定理

Fundamental Region:

为了辅助理解：

数学上，给出一个拓扑空间和在其上作用的群，一个点在群作用下的像是这个作用的一个轨道。一个基本域是这个空间的一个子集，包含了每个轨道中恰好一点。基本域具体地用几何表现出抽象的轨道代表集。 构造基本域的方法有很多。一般会要求基本域是连通的，又对其边界加上一些限制，例如是光滑或是多面的。——wikipedia

凸集：暂可以理解为是一个多维空间的一部分（一个多维物体）(详细可见References)

叠加了线性变换：

重要应用： 给出了一个Lattice中，最短向量的一个上限值

最短向量

对于一个Lattice，最短向量是指该Lattice中长度最小的非零向量，而（距离原点）距离最远的最短向量则是指该Lattice中长度最小的非零向量与原点的距离最远的那个向量。这个向量通常被称为Lattice的第一个近邻向量或最优向量。

计算Lattice的最短向量和最远的最短向量是一个重要的问题，因为它们在很多应用中都有着重要的作用。其中，计算最短向量是一个NP难问题，而计算最远的最短向量则是一个NP难问题的变体。目前，已经有很多算法被提出来用于解决这些问题，但是在实际应用中，它们的效率和精度都有一定的限制。

这里给出二维的表述：

坐标平面上任何包含原点的、面积大于4的、凸的、关于原点对称的闭区域一定含有异于原点的整点。

1.4Minkowski第二定理

Steven的理解：

结合向量空间，可以认为明可夫斯基第二定理给出了对于所有最短向量的的取值上限。

当然我们对det（L）做一些详细解释，以便结合曾经的明可夫斯基不等式来理解这一定理：

行列式的几何意义 $$ X^T = (a,c),X'^T = (b,d)\ det(X^T,X'^T) = S $$

二维情况下，行列式可以理解为对应平行四边形的面积。（暂不考虑复平面）注意我们这里将这一面积视为有向面积。（考虑到行列式的符号）

行列式的部分性质

• 行列式为零当且仅当两个向量共线（线性相关），这时平行四边形退化成一条直线[9]

• 行列式是一个双线性映射。 $$ det(λX+μY,X') =λdet(X,X')+ μ(Y,X') \ det(X,λX'+μY') =λdet(X,X')+ μ(X,Y') $$

在基本了解行列式之后，不难在向量空间中理解第二定理所给出的不等式。

介绍一下代数层面的理解过程：

明可夫斯基不等式给出了LP空间上的三角不等式的表达，那么第二定理则可以在LP空间以介值的方式进行理解。

明可夫斯基,相信各大赛区的“羟基选手”都很熟悉（bushi），以它来引入某一空间，那么同样的，在此空间内理解第二定理。

2.Problem in Lattice （BasisOfCrypto)

在本章节仅仅罗列了一些难解问题

维基百科中的本章内容

2.1 SVP（Shortest Vector Problem）

SVP定义：

给定一个基为的Lattice ，找到一个这个基构成的格点，使得这个点距离0坐标点的距离最近。

$$ BX :X∈ \mathbb{Z^k}\ \left | Bx \right | \le \lambda_1 $$

可视化：

如果所得到基底不合适，那么计算最短向量就不是一件容易的事情了。

断言：严格的计算最短向量是困难的。 这里并不给出其NP-Hard属性的证明。

Simplify: $$ SVP_γ $$

$$ BX :X∈ \mathbb{Z^k}\ \left | Bx \right | \le γ\lambda_1 $$

这时候的解，则不唯一了。

2.2CVP

（Closest Vector Problem）CVP定义：

给定连续空间中任意的一个点t，找到距离这个点最近的格点Bx。

此时的t处于全集空间内，而寻找距离对应的距离最近的格点，这样一个问题。

约束距离：μ ,Lattice 的覆盖半径。 $$ Bx：x ∈\mathbb{Z^k}\ ||BX -t|| \le \mu $$ 覆盖半径μ给出了所有可能的t中距离格点的最长距离。

对CVP问题做同样的Simplify： $$ Bx：x ∈\mathbb{Z^k}\ ||BX -t|| \le γ\mu $$ 同样的不唯一。

2.2.1 Bounded Distance Decording

(Bounded Distance Decording)

2.2.2 Absolute Distancea Decording

(Absolute Distancea Decording)

2.3SIVP（Shortest Independent Vector Problem)

2.4问题与联系

NP-HARD

Association:

对于这里没有提到的GapSVP和GapSIVP问题，可以在wikipedia中找到详细介绍。

2.4.1漏故而知新

理解了五大问题的基本思想和概念，那么我们把视野放在各个关系的联系上。

从ADD问题到SIVP问题：

几何上不难直观理解，找出SIVP的解，再以所得向量为基向量，不难得到ADD问题得解。

：

2.4.2基于格的信息传递

3.Lattice的几何构造

在2.4中我们提到了取整。

在笛卡尔坐标系下，取整数格，CVP问题变得简单。通过上下取证，我们可以迅速解决问题。

通过把一组基进行变换，找到一组非常接近垂直的基向量的过程，称为 Lattice Basis Reduction

3.1 Gram-Schmidt 正交化

寻找一组正交向量作为基底，在Lattice中也有重大应用。

而应用的原理则为Det(L)的大小不随线性变换而改变。

3.1.1基本形式

代数上：

3.1.2代码

给出基于numpy库和sympy的代码：

Numpy:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def my_gramSchmidt_np(vectors):        #Eg:vecetors = np.array([[1,2],[3,4]]) 
     def proj(x, u):
         u = unit_vec(u)
         return np.dot(x, u) * u
        
     def unit_vec(x):
         return x / np.linalg.norm(x)
     vectors = np.atleast_2d(vectors)
    
     if len(vectors) == 0:
         return []
     if len(vectors) == 1:
         return unit_vec(vectors)
    
     u = vectors[-1]
     basis = my_gramSchmidt_np(vectors[0:-1])
     w = np.atleast_2d(u - np.sum(proj(u, v) for v in basis))
     basis = np.append(basis, unit_vec(w), axis=0)
    
     return basis

Sympy:

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

def my_gramSchmidt_sp(*vectors):
     normalize = True
 
     def project(a, b):
         return b * (a.dot(b, hermitian=True) / b.dot(b, hermitian=True))
 
     def perp_to_subspace(vec, basis):
 
         components = [project(vec, b) for b in basis]
 
         if len(basis) == 0:
             return vec
 
         return vec - reduce(lambda a, b: a + b, components)
 
     ret = []
     vectors = list(vectors)
 
     while len(vectors) > 0 and vectors[0].is_zero_matrix:
         del vectors[0]
 
     for vec in vectors:
         perp = perp_to_subspace(vec, ret)
 
         if not perp.is_zero_matrix:
             ret.append(Matrix(perp))
 
     if normalize:
         ret = [vec / vec.norm() for vec in ret]
 
     return ret
 
 def gram_schmidt_sp(V):
     # YOUR CODE HERE
     if type(V) is not sympy.MutableDenseMatrix:
         raise ValueError
     if len(V.tolist()) != len(V.tolist()[0]):
         raise ValueError
     V = np.array(V)
     V = np.transpose(V)
     V = Matrix(V)
     vlist = V.tolist()
     tmp_list = []
     for i in vlist:
         tmp_list.append(Matrix(i))
     result = my_gramSchmidt_sp(*tmp_list)
     if len(result) == len(tmp_list):
         ma_list = []
         for i in result:
             tmp_list = []
             for j in i:
                 tmp_list.append(j)
             tmp = tmp_list
             ma_list.append(tmp)
 
         result = Matrix(ma_list)
         return result
     else:
         ma_list = []
         for i in result:
             tmp_list = []
             for j in i:
                 tmp_list.append(j)
             tmp = tmp_list
             ma_list.append(tmp)
         result = Matrix(ma_list)
         result = Matrix(result).H
         result = result.row_join(Matrix([[0], [0]]))
         return result

Sagemath:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# 定义向量组
v1 = vector([1, 0, 1])
v2 = vector([1, 1, 1])
v3 = vector([0, 1, 1])
vec_list = [v1, v2, v3]

# 使用 Gram-Schmidt 函数进行正交化
orth_list = GramSchmidt(vec_list)

# 输出正交向量组
for v in orth_list:
    print(v)
#在上面的代码中，我们首先定义了一个向量组，然后使用GramSchmidt函数将其转换为正交向量组。最后，我们遍历正交向量组并将其打印出来。

#需要注意的是，Gram-Schmidt函数只能在有限维向量空间上工作。如果您需要处理无限维向量空间，则需要使用其他方法。

3.2 Lattice Rounding （取整问题）

原基向量再正交化后得到新的基向量，但是同时也产生了新的不同于原来的格。

平移：t，约束条件：

在基于Lattice的信息传输中，使用了取整，蕴含了一个不等式：

取整求解的问题：

当我们做取整操作的时候，因为几何形状的原因，最后的得到的结果格点和CVP问题的真正解会略有误差。比如我们看上图，t的落点在内圈的这个小圆内，那么我们取整得到的一定会是CVP的正确解。

正确解的条件：

上面的表述避免了使用各种不同范数的概念，可根据三维欧几里得空间辅助理解。

下图可辅助理解。

References

• 稀有气体：斯坦福的经验交流
• CTFwiki
• Wikipedia
• 【非线性优化理论】凸集
• Lattice Reduction Attacks on RSA
• A systematic approach to lattice models with solvable boundary states of arbitrary codimension
• An Introduction to Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm