Lattice learning-2

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$ 的一组新的基。