在 格密码笔记（二） 中，我们已经能感觉到，lattice 有两个核心的（计算上的）问题：在一个 lattice 中找到最短的非零向量；在一个 lattice 中找到与给定的某个非 lattice 向量最近的向量。我们将在这篇博客，讨论各种 lattice 上的计算问题。
lattice 上的问题概述
先来看我们的俩老朋友：SVP 和 CVP.
最短向量问题（The Shortest Vector Problem, SVP）
在 lattice $L$ 中找到一个最短非零向量。亦即，找到一个非零向量 $\newcommand\b{\boldsymbol} \newcommand\v{\b v} \v\in L$ 使得 $\|\v\|$ 最小。
最近向量问题（The Closest Vector Problem, CVP）
给定一个不在 $L$ 中的向量 $\newcommand\w{\b w} \w \in \newcommand\R{\mathbb{R}} \R ^m$，找到向量 $\v \in L$，最小化 $\|\w-\v\|$.
我们应当注意到，SVP 问题可能有多解。例如在 $\mathbb{Z} ^2$ 中，有四个解 $(0,\pm 1), (\pm1,0)$. SVP 问题只需要我们找出一个最短向量，而不要求把所有的最短向量都输出。CVP 也类似：它也可能有多解，我们也只需要输出任何一个。
之前我们已经演示过，如何使用 SVP 来攻破 Merkle-Hellman 子集和密码体系。SVP 和 CVP 都是很困难的问题，当 lattice 的纬度增加，它们的复杂度也快速增加。不过，虽然 SVP 和 CVP 是困难的，但其近似解有的时候也很有用。求近似解的难度比直接求 SVP, CVP 要低一些。
已经知道，CVP 是 NP-hard 的问题。SVP 在“有极大可能性在多项式时间内停机并输出正确结果的概率多项式时间（PPT）算法，也属于多项式时间算法”的语境下也是 NP-hard 的。
计算上，一般认为 CVP 比 SVP 稍微难一点点。SVP 可以归约到 CVP。
我们在攻击 Merkle-Hellman 的时候，子集和问题是一个典型的 CVP，而我们通过一点点技巧，从 $n$ 维升到 $n+1$ 维，于是利用 SVP 解决了问题。
尽管在一般情况下， SVP 和 CVP 都是极度困难的问题，但现实使用中，未必能达到这个困难程度。基于 NP-hard/NP-complete 问题的密码体系，往往是依赖该问题的某个特殊情境（目的是产生陷门，或者使得诚实方可以高效计算），但这也可能会为攻击者大开方便之门。例如，我们知道子集和问题是困难的，但基于“混淆过的超级递增序列”的子集和问题，则可以被攻击者比较快速地解决。
SVP 与 CVP 还有许多变体，我们摘录于下。
最短基问题（Shortest Basis Problem, SBP）
找到最短的基向量 $\v_1, \dots, \v_n$，使得它们（在指定的长度定义下）最短。例如要求最小化 $$\max _{1\leq i\leq n} |\v_i|\qquad \text{or}\qquad \sum_{i=1} ^n |\v_i| ^2$$不同的长度定义会给出不同的 SBP，故 SBP 有大量的版本。
近似最短向量问题（apprSVP）
设 $\psi(n)$ 是 $n$ 的函数。对于维度为 $n$ 的 lattice $L$，找到一个非零向量，其长度不能超过 $\psi(n)$ 倍的（真正的）最短非零向量。也就是说，若我们记 $L$ 的最短非零向量为 $\newcommand\vs{\v _{\text{shortest}}} \vs$，则要寻找向量 $\v\in L$ 满足$$\|\v\| \leq \psi(n) \|\vs\|$$
不同的 $\psi(n)$ 给出不同版本的 apprSVP. 举个例子，我们可能会要求 $$\|\v\| \leq 3\sqrt n \|\vs\|$$
显然，不同版本的 apprSVP 的难度差异可能很大。例如，解决 $\psi(n)=3\sqrt n$ 的 apprSVP 远比解决 $\psi(n)=2 ^{n/2}$ 的 apprSVP 困难。不过，如果维度不太大，解决后者的算法都可能是有实际用处的。
Hermite 定理和 Minkowski 定理
一个 lattice 的最短非零向量到底有多长？这和 $L$ 的维度以及协体积有关。我们来看一个上界：
Hermite's Theorem
每一个 $n$ 维的 lattice $L$，都包含一个非零向量 $\v \in L$ 满足$$\|\v\|\leq \sqrt n \det (L) ^ {1/n}$$
我们可以定义 Hermite 常数 $\gamma _n$，来研究 $n$ 维 lattice $L$ 的最短向量长度上界。$L$ 必定包含一个非零向量 $\v$ 满足：$$\|\v\| ^2 \leq \gamma _n \det (L) ^{2/n}$$
Hermite 定理说明了性质 $\gamma_n \leq n$. 而至于 $\gamma_n$ 的确切值，我们只知道 $1\leq n\leq 8$ 以及 $n=24$ 的情形：$$\begin{array}{ll}
\gamma & \text{value} \\ \hline
\gamma _2 ^2 & \frac43\\
\gamma _3 ^3 & 2\\
\gamma _4 ^4 & 4\\
\gamma _5 ^5 & 8\\
\gamma _6 ^6 & \frac{64}{3}\\
\gamma _7 ^7 & 64\\
\gamma _8 ^8 & 256\\
\gamma _{24} ^{24} & 4
\end{array}$$但是这显然不够我们用，因为密码学用途中，$n$ 往往很大。我们有一个更紧的界：$$\frac{n}{2\pi e}\leq \gamma _n \leq \frac{n}{\pi e}$$
我们上面的讨论都是针对一个最短向量的。而对于一组基（多个向量），也有定理：$$\|\v_1\| \|\v_2\| \cdots \|\v_n\| \leq n ^ {n/2} (\det L)$$这构成了基向量长度之积的上界。之前我们介绍过的 Hadamard 不等式给出了其下界：$$\|\v_1\| \|\v_2\| \cdots \|\v_n\| \geq \det L$$我们定义一组基 $\mathcal{B} = \{ \v_1 ,\dots, \v_n\}$ 的 Hadamard ratio：$$\mathcal{H}(\mathcal{B}) = \left( \frac{\det L}{\|\v_1\| \|\v_2\| \cdots \|\v_n\|} \right) ^{1/n}$$显然有 $0\leq \mathcal{H}(\mathcal B) \leq 1$，而且这个 Hadamard ratio 越接近 1，这组基向量越像正交。
Hermite 定理使用了 Minkowski 定理的结论。接下来我们讨论 Minkowski 定理。
先定义若干记号：
闭球（closed ball） 对于任意 $\newcommand\a {\b a} \a\in\R ^n $ 以及任意 $R > 0$，我们称半径为 $R$、球心为 $\a$ 的“闭球”为 $$\newcommand \B{\mathbb B} \newcommand \BR{\B _R} \BR(\a) = \{ \newcommand\x{\b x} \x \in \R ^n : \|\x-\a\| \leq R \}$$
现在给出一些定义。设 $S$ 是 $\R ^n$ 的子集，那么：
- 称 $S$ 是有界（bounded）的，当且仅当 $S$ 内向量的长度是有界的。
等价描述：$S$ 是有界的，当且仅当 $S$ 包含在 $\BR(\b 0)$ 中。 - 称 $S$ 是对称（symmetric）的，当且仅当对于 $S$ 中的每一个点 $\a$，其相反向量 $-\a$ 也在 $S$ 中。
- 称 $S$ 是凸（convex）的，当且仅当对于 $S$ 中的任意两个点 $\a, \b b$，连接它们的线段完全在 $S$ 内。
- 称 $S$ 是闭（closed）的，当且仅当如下性质成立：若 $\a \in \R ^n$ 是一个点使得任意球 $\BR (\a)$ 都包含 $S$ 中的点，则 $\a$ 在 $S$ 中。
说人话：边界上的点也在 $S$ 中。
现在来看 Minkowski 定理。
Minkowski's Theorem
设 $L\subset \R ^n$ 是一个 $n$ 维 lattice，$S\subset \R ^n$ 是一个有界的、对称的、凸的点集，且满足$$\text{Vol}(S)> 2 ^ n \det L$$则 $S$ 包含一个非零 lattice 向量。
如果 $S$ 还是闭的，则条件松弛到 $\text{Vol}(S) \geq 2 ^n \det L$.
证明如下。设 $\newcommand\F{\mathcal F} \F$ 是 $L$ 的一个基本域，我们可以将 $S$ 中的任意向量 $\a$ 写成如下形式：$$\a = \v_a + \newcommand\w{\b w} \w_a,\qquad \v_a \in L, \w_a\in \F$$现在我们考虑 $S$ 收缩一半的集合：$$\frac12 S = \left\{ \frac12 \a : \a\in S \right\}$$接下来，我们考虑映射 $\frac12 S \to \F$：$$\quad \frac12 \a \mapsto \w_{\frac12 \a}$$不难注意到，把 $S$ 收缩一半会导致其协体积除以 $2 ^n$，于是$$\text{Vol}\left(\frac12 S\right) = \frac1{2 ^n} \text{Vol}(S) > \det L = \text{Vol} (\F)$$
由于 $\frac12 S$ 的协体积严格比 $\F$ 要大，于是必然存在不同的 $\frac12 a_1, \frac12 a_2$ 映射到 $\F$ 的同一个点。于是我们得到了 $S$ 中的两个点：$$\frac12 a_1 = \v_1 + \w,\quad \frac12 a_2 = \v_2 + \w$$立即有 $$\frac12 \a_1 - \frac12 \a_2 = \v_1 - \v_2 \in L$$式子左边的点，相当于 $\a_1, -\a_2$ 的中点。由于 $S$ 是对称的，所以 $-\a_2\in S$；又由于 $S$ 是凸的，从而 $\a_1, -\a_2$ 的中点也在 $S$ 中。于是 $\v_1 - \v_2 \in S$，我们构造出了 $S$ 中的一个 lattice 点。
至此完成 Minkowski's theorem 的证明。
有了 Minkowski 定理之后，我们可以快速证明出 Hermite 定理。设 $L\subset \R ^n$ 是 lattice，$S$ 是 $\R ^n$ 中的超立方体，中心为 $\b 0$，棱长为 $2B$，即$$S = \big\{ (x_1, \dots, x_n) \in \R ^n : -B\leq x_i \leq B \big\}$$那么显然 $S$ 是对称的、闭的、有界的，且协体积$$\text{Vol}(S) = (2B) ^n$$于是，设 $B = \det (L) ^{1/n}$，有 $\text{Vol}(S) = 2 ^n \det L$。应用 Minkowski 定理，知 $S$ 中有 lattice 点 $\a$. 将其坐标记为 $(a_1,\dots,a_n)$，由 $S$ 的定义我们有 $$\|\a\| = \sqrt{a_1 ^2 + \cdots + a_n ^2} \leq \sqrt n B = \sqrt n \det (L) ^ {1/n}$$至此完成 Hermite 定理的证明。