Lattice作为全同态加密的基础代数结构，值得学习一下；最关键的一点，LBC至今为止不能被量子计算机破解。这正如20年前的椭圆曲线代数结构，正如40年前的RSA代数结构一样。
Lattice的本质是高维空间中几何学和代数学的组合，学起来会超级困难，一点也不亚于高考数学的挑战难度。密码学本身要求研究者对代数学有比较深入的理解，学起来很晦涩，所以我会尽全力将搜罗到的一些知识整合得更完整可读一些，并适当掺加一点自己的见解（如果都对的话）
在格理论密码系统出现之前，没有合适的问题可以用于构造同态加密系统。
没有哪个密码体系能有如此的抗量子攻击，格密码的算法效率令RSA望尘莫及，以及拥有超强的安全保障
格 定义
$$
格(lattice)设 v_1,…,v_n \in R^m是线性无关向量组。\我们称 v_1,…,v_n生成了 lattice L：
即L 中的元素是 v_1,…,v_n的整系数线性组合。\
我们定义L 的一个基(basis)是任何一个能生成 L的向量组。\显然 lattice 的两个基会拥有相同的向量个数；基所包含的的向量个数称为 L的纬度(dimension).
$$
$$
L= \lbrace a_1v_1+a_2v_2+…+a_nv_n:a_1,a_2,…,a_n \in Z\rbrace
$$
$$
n维的格L是R^n的一个子集且满足：\quad \（1）L是一个加法子群 \quad （2）L是离散的【L的邻域中不包含其他的点】
$$
格的基
格就是从R^m中选择n个线性无关的向量，选取这些向量的全部整数组合构成的点集。（基向量的任意线性组合的集合）
$$
L=L(B):=B⋅Z^k={\sum _{i=0}^{k}z_ib_i:z_i∈Z}
$$
这组生成格的线性无关的向量就是格的基，格可以有很多组基，但格的维数是相同的。
格的两组基之间可以通过一个行列式为 ±1的矩阵进行转换，其基变换矩阵中的元素均为整数【格的基向量不是唯一的】
· 这 k个向量是格 L 的一组基
· 格 L 的秩为 k
· 格 L 的位数为 m
如果 m=n，那么我们称这个格式满秩的
从上图中可以看出这个二维的格中有两组基， v1’和 v2’的明显正交性更好（接近于正交），这样的基我们认为是优质基，反之 v 1 和 v 2 之间夹角就比较小，这类基，通常认为是劣质基。
在此补充一下线性代数相关的内容，因为Lattice涉及到很多行列式、基有关。
线性空间
线性空间(vector spaces)
$$
一个线性空间 V，是R^m
的一个子集，满足
a_1v_1+a_2v_2 \in V \quad \forall v_1,v_2 \in V,a_1,a_2 \in R \quad
\也就是说，一个线性空间，是对向量加法、标量乘法封闭的R^m
的子集。
$$
线性组合(linear combinations)
$$
v_1,v_2,…,v_k \in V的一个线性组合是满足以下形式的向量：\\lbrace w=a_1v_1+a_2v_2+…+a_kv_k, \quad a_1,…,a_k \in R \rbrace称为\lbrace v_1,…v_k \rbrace 的张成空间
$$
线性无关(linearly independence)
$$
称一个向量集合v_1,…v_k \in V线性无关，当且仅当方程\a_1v_1+a_2v_2+…+a_kv_k=0的唯一解是a_1=a_2=…=a_k=0.否则这个向量集合线性相关
$$
基(bases)
$$
向量空间V 的一个基，是可以张成V 的线性无关向量集合v_1,…v_n
. \也就是说，任何一个向量 都可以写成v_1,…v_n
的线性组合的形式，其线性组合的系数是唯一的。
$$
任何一个线性空间 V 都有基。
任何两个基，含有的向量个数是相同的。基的向量个数称为 V 的维度(dimension).
$$
设 v_1,…v_n是 V的一个基， 是 w_1,…w_n 中的一个向量组。我们把 w_j 写成 v_i 的线性组合的形式：
$$$$
w_1=a_{11}v_1+a_{12}v_2+…+a_{1n}v_n
$$$$
w_2=a_{21}v_1+a_{22}v_2+…+a_{2n}v_n
$$
$$
w_n=a_{n1}v_1+a_{n2}v_2+…+a_{nn}v_n
$$
$$
则w_1,…w_n也是V的一个基，当且仅当下列矩阵的行列式不为零
$$
$$
\begin{pmatrix}
a_{11 }& a_{12} & \cdots & a_{1n} \
a_{21} & a_{22} & \cdots & a_{2n} \
\vdots & \vdots & \ddots & \vdots \
a_{n1} & a_{n2} & \cdots & a_{nn} \
\end{pmatrix}
$$
度量向量长度和向量夹角
点积(dot product)
$$
设v,w \in V \subset R^m \quad 记v,w的坐标如下：v=(x_1,x_2,..x_m),\quad w=(y_1,y_2,…,y_m)
.
$$
$$
记 V与 W的点积为: \quad v·w=x_1y_1+x_2y_2+…+x_my_m
$$
$$
若 v·w=0，我们称 v与 w正交(orthogonal).
$$
欧几里得范数(Euclidean norm)
$$
向量 v的长度，或称欧几里得范数，为 ||v||=\sqrt {x_1^2+x_2^2+…+x_m^2}, \quad v·v=||v||^2
$$
$$
记 \theta为向量v,w 之间的角（这里我们把 v,w的起始点都放在原点0）。则 v·w=||v|| ·||w||cos \theta
$$$$
(Cauchy-Schwarz 不等式) 两向量的点积的绝对值，不大于向量长度的积。\ \quad |v·w|\leq ||v||·||w||
$$正交基(orthogonal basis)
$$
线性空间V 的一个正交基，是满足以下条件的基v_1,…v_n
：v_i·v_j=0 \quad \forall i \neq j
$$
额外地，若这个基还满足||v||=1 ，则我们称这个基规范正交(orthonormal).
Lenstra–Lenstra–Lovasz（格基规约算法 ）
在 lattice 里面找短向量的算法，称为 lattice reduction（格基规约）算法