格

格密码学

Lattice-based cryptography，格密码学，是一种基于格（lattice）的密码学算法，目前是后量子密码学的重要候选方案，与 RSA、Diffie-Hellman 或椭圆曲线密码系统等更广泛使用和众所周知的公钥方案（理论上可以在量子计算机上使用肖尔算法击败这些方案）不同，一些基于格的构造似乎既能抵御经典计算机的攻击，也能抵御量子计算机的攻击。

关于格

传统公钥密码学的安全，往往建立在数学问题的困难性上，RSA基于大整数分解的困难性，Elgamal，ECC基于有限域上离散对数求解的困难性，这些难题均可使用量子计算机并应用秀尔算法破解。虽然大型量子计算机尚未普及，但是后量子密码学已经成为人们关注的焦点。格密码学是后量子密码学的代表之一。

格，是一种类似向量空间的数学空间，实数空间$R$上的向量空间$V$,是一些向量的集合，任意两个向量可以相加，任意一个向量可以和一个实数相乘，运算具有封闭性。在lattice中，与向量空间有所区别，具体来说，就是乘法中的乘数，从实数改为整数。如下图，是几种不同的格空间。

数学表示，给定$n$维实数空间$R^n$中的一组线性无关向量$B=\{b_1,...,b_n\}\subset R^n$，其整数系数线性组合构成的集合被称为格（Lattice），即$L=\Sigma_{i=1}^nb_i \cdot Z={Bx,x\in Z^n}$其中$B=\{b_1,...,b_n\}$被称为格基。同一个格可能有不同的格基。

某种程度上，格可以理解成系数为整数的向量空间。

与格相关的基本计算性难题：
1.SVP: Shortest Vector Problem （在格中寻找最短的非零向量）
最短向量问题(SVP):在格$L$中寻找一个最短的非零向量，即寻找一个非零向量$v\in L$,使它的欧几里得范数$\vert \vert v\vert \vert$最小。

2.CVP: Closet Vector Problem（在格中寻找与指定非格向量最为接近的向量）
最近向量问题(CVP):给定一个不在格$L$中的向量$\omega \in R^m$ ，寻找一个向量$v \in L$，使它最接近$\omega$，即寻找一个向量$v\in L$，使欧几里得范数$\vert \vert \omega - v\vert\vert$最小。