Lattice学习记录

格中的短向量

格中有两个基本问题

• 最短向量问题（SVP）：

  在格$L$​​中寻找一个向量，使它的长度最小。

• 最接近向量问题（CVP）：

  给定一个向量$\vec w \in R^m$，在格$L$中寻找一个向量$\vec v$，使得$||\vec w-\vec v||$最小。

当然这两个问题都可能有多解，从二维的平面坐标我们就可以知道这个事情。不过这两个问题，随着维度$n$​​​的变大，计算也就越困难。之所以我们要解决这两个问题，是因为这两个问题求出的向量，在理论和应用数学的不同领域有许多应用。

在实际中，CVP比SVP更难求解一些，所以我们会把CVP转化成SVP求解。在真实世界的情景中，基于NP-Hard或NP-Complete问题的密码系统倾向于依赖于某种问题的特定子类，以实现效率或允许创建一个trapdoor。 完成后，始终存在所选子类的一些特殊属性，使其更容易地解决而不是常规情况。 我们已经在第6.2节中与Knapsack Cryptosystem中感受过了。

这两个问题还有很多变体，这里就不多介绍了。

Hermite’s theorem and Minkowski’s theorem

我们知道，最短向量的具体长度，取决于格$L$​的维度以及行列式。而这两个定理给出了最短向量的界。

• Hermite定理：格$L$的维度为$n$，那么它一定有一个向量$\vec v$满足

• Hermite常数 $\gamma _n$​：对于一个给定的维度$n$​，在格$L$​中一定有一个向量满足

  而$\gamma_n$​​​是满足这个不等式的最小值，也就是说$\gamma_n\le n$​​​​。我们目前已知n=1—8,24 这九个值。对于一般的$\gamma_n$，我们有如下范围

对于Hermite定理，我们有如下推论

其中$v_i$是$L$中的基，这个式子由Hermite定理累乘n次很容易得到。而我们又知道

于是我们就可以在这组不等式两边同时除以$\prod_{i=1}^n ||\vec v_i||$​​，然后开n次根号，我们就得到了

• Hadamard比率：

  我们可以知道$0< H(B)\le1$​​，这个值约接近1，格的这组基就越正交​​。

为了介绍Minkowski定理，我们需要引入几个概念。

• 封闭球：对于任意$\vec a\in R^n$和任意$R>0$，对$\vec a$的封闭球是集合$B_R(\vec a)=\{\vec x\in R^n:||\vec x-\vec a||\le R\}$，也就是和$\vec a$​距离不超过R的空间。

• 令$S$是$R^n$的一个子集：

  • 如果$S$中的向量长度是有界的，那么$S$​是有界的。与之等价的，如果有一个半径$R$​，能让$S$被包含在封闭球$B_R(0)$中，那么$S$是有界的。
  • 若对于$\vec a \in S$，存在$-\vec a\in S$，那么$S$是对称的。
  • 若对于$S$中的任意两点$\vec a,\vec b$，$\vec {ab}$​上每一点都在$S$中，那么$S$是凸性集合。
  • 若对于$\vec a \in R^n$，对于$\vec a$的每个封闭球，都有一个点在$S$里，那么$\vec a$在$S$中。如果$S$有这个性质，那么它是封闭的。

Minkowski’s Theorem

设$L$​是$R^n$​中的一个格，$S$​是$R^n$​中的一个对称凸集，那么$S$​的体积$Vol S>2^ndetL$​时，$S$​中就包含一个非零格向量。如果$S$​是封闭的，那么上面的不等式也可以取等号。

Babai’s algorithm

如果说格$L$​有一组基，其中的向量两两正交，那么SVP和CVP都很容易解决。这个算法就是利用了这点。

现有一个向量$\vec w$​，我们把它分解到格的基上，$\vec w=t_1\vec v_1+t_2\vec v_2+...+t_n\vec v_n\quad (t_i\in R)$​，我们对每个$t_i$​取整，记作$a_i$​，我们就得到新的向量$\vec v=a_1\vec v_1+a_2\vec v_2+...+a_n\vec v_n$​。

以上就是算法的全部，这个算法在基比较正交的时候可以解决一部分apprCVP问题，但是在基不是很正交的时候，就不适用了。

GHH公钥密码系统

Alice选择$L$的一组基$\vec v_1,\vec v_2,...,\vec v_n$​​作为私钥，这组基的Hadamard ratio不是很小。Alice再选择一个由整数构成的矩阵$U$​，$det(U)=±1$​。计算$W=UV$​，并把$U$​中的行向量$\vec w_1,\vec w_2,...,\vec w_n$​​作为公钥，它们是$L$的一组新的基。

Bob选择明文构成的小向量$\vec m$，再选择一个随机的小干扰向量$\vec r$​，计算$\vec e=\vec mW+\vec r$。

Alice解密时，使用Babai算法计算在原来的基中和$\vec e$最近的向量$\vec v$，然后计算$\vec vW^{-1}$恢复明文。