格

格（Lattice）是给定的一组线性无关的基向量 $v_1,v_2,v_3,…,v_m$的所有整系数线性组合 $a_1v_1+a_2v_2+…+a_nv_n,a_i∈Z$ 所形成的集合。

  • 不同的基底可能会形成不同的格
  • 相同的格会有不同的基底
  1. 格中计算问题的困难性，即这些问题的计算复杂性，主要包括
    1. SVP 问题（最短向量问题）
    2. CVP 问题（最近向量问题）
  2. 如何求解格中的困难性问题，目前既有近似算法，也有一些精确性算法。
  3. 基于格的密码分析，即如何利用格理论分析一些已有的密码学算法，目前有如下研究：
    1. Knapsack cryptosystems
    2. DSA nonce biases
    3. Factoring RSA keys with bits known
    4. Small RSA private exponents
    5. Stereotyped messages with small RSA exponents
  4. 如何基于格困难问题设计新的密码体制，这也是后量子密码时代的重要研究方向之一，目前有以下研究：
    1. Fully homomorphic encryption
    2. The Goldreich–Goldwasser–Halevi (GGH) cryptosystem
    3. The NTRU cryptosystem
    4. The Ajtai–Dwork cryptosystem and the LWE cryptosystem

格基规约算法（LLL）

在所有基向量经过至少一次规约后，LLL 返回新基，按长度进行大致排序。

规约的主要目的是，将这组任意给定的基转化为一组正交性较好的优质基，并使得这个优质基中的各个向量尽量短。

（未完）