格概述

格在数学上至少有两种含义

• 定义在非空有限集合上的偏序集合 L，满足集合 L 中的任意元素 a，b，使得 a，b 在 L 中存在一个最大下界，和最小上界。具体参见 ： https://en.wikipedia.org/wiki/Lattice_(order)

• 群论中的定义，是 $R^n$ 中的满足某种性质的子集。当然，也可以是其它群。

目前关于格方面的研究主要有以下几大方向

1. 格中计算问题的困难性，即这些问题的计算复杂性，主要包括

   a.SVP 问题 (Shortest Vector Problem)

   b.CVP 问题 (Closest Vector Problem)

2. 如何求解格中的困难性问题，目前既有近似算法，也有一些精确性算法。

3. 基于格的密码分析，即如何利用格理论分析一些已有的密码学算法，目前有如下研究

   a.Knapsack cryptosystems （背包密码）

   b.DSA nonce biases（DSA 随机数偏差）

   c.Factoring RSA keys with bits known （使用已知位对 RSA 密钥进行分解）

   d.Small RSA private exponents（RSA 小私钥指数）

   e.Stereotyped messages with small RSA exponents （具有小 RSA 指数的构造型消息）

4. 如何基于格困难问题设计新的密码体制，这也是后量子密码时代的重要研究方向之一，目前有以下研究

   a.Fully homomorphic encryption（完全同态加密）

   b.The Goldreich–Goldwasser–Halevi (GGH) cryptosystem

   c.The NTRU cryptosystem

   d.The Ajtai–Dwork cryptosystem and the LWE cryptosystem