格密码基础、SVP、CVP、计算困难问题\(Preface\)
由\(Minkowski's\ convex\ body\ theorem\)推导出的\(Minkowski's\ first\ theorem\)证明了一个秩\(n\)的任意格\(\mathcal{L}\)中有\(\Vert\vec{v}\Vert\leq\sqrt{n}(det(\mathcal{L}))^{1\over n}[\vec{v}\in\mathcal{L}\ and\ \vec{v}\neq\vec{0}]\)。然而，它是存在性证明（非构造性的），这是因为它并没有给出多项式时间内的求解算法。事实上，目前没有已知的有效算法可以找到这样的短向量。
\(SVP\)
最基本的涉及格的计算难题是最短向量问题，简称\(SVP\)。给出一个格，目标是找到其中欧几里得长度最短的非零格向量。
然而在现代格密码学中，我们通常研究的是带有近似因子 \(\gamma\) 的\(SVP\)变体（\(SVP_\gamma\)），这主要基于以下两个现实原因的结合：
- 计算复杂性的限制：已知精确\(SVP\)在高维空间中是\(NP-Hard\)的，意味着在多项式时间内找到绝对最短向量是不可行的。
- 密码分析与算法现状：在实际破译格密码方案（如\(LWE\)、\(NTRU\)）时，攻击者通常不需要精确的最短向量，寻找一个“足够短”的近似向量即可攻破方案。同时，现实中可用的多项式时间格基规约算法（如\(LLL\)算法）或次指数时间算法（如\(BKZ\)算法），其输出结果正是一个近似短向量。
因此，为了弥合理想安全性与实际攻击能力之间的数学间隙，必须引入近似因子 \(\gamma (\gamma \ge 1)\)。\(\gamma\) 通常是关于格维度 \(n\) 的函数（如多项式级或指数级），它直接决定了该格问题的求解难度：\(\gamma\) 越小，问题越接近精确\(SVP\)，求解越困难。
下面给出\(SVP_{\gamma}\)的三个变体：
- \(Search\ SVP_{\gamma}\)：给定格基\(B\in\mathbb{Z}^{m×n}\)，求\(\vec{v}\in\mathcal{L}(B)\)，使得\(\Vert\vec{v}\Vert\leq\gamma\cdot\lambda_1(\mathcal{L}(B))\);
- \(Optimization\ SVP_{\gamma}\)：给定格基\(B\in\mathbb{Z}^{m×n}\)，输出一个数值\(d\)，使得\(\lambda_1(\mathcal{L}(B))\leq d\leq \gamma\cdot\lambda_1(\mathcal{L}(B))\)；
- \(Promise/Decisional\ SVP_{\gamma}(Gap\ SVP_{\gamma})\)：给定格基\(B\in\mathbb{Z}^{m×n}\)和有理数\(d>0\)：
- \(YES\)实例：\(\lambda_1(\mathcal{L}(B))\leq d\)；
- \(NO\)实例：\(\lambda_1(\mathcal{L}(B))>\gamma\cdot d\)；
- 注意\(Gap\)问题中存在一个判定间隙，如果\(\lambda_1\)落在\([d, \gamma d]\)之间，算法可以输出任意结果。正是这个间隙\(\gamma\)决定了问题的难度
注意，我们限制了格基是由整数向量组成，而不是实数向量组成。这样的目的是使输入以有限的多位表示（因为计算机无法精确存储无限不循环小数），这样我们就可以将\(SVP\)视为一个标准的计算难题。我们还可以允许格基由有理向量组成。这将导致一个本质上等价的定义，因为通过缩放，可以使所有有理数坐标都是整数。
\(CVP\)
格中另一个基本的难题是最近向量问题，简称\(CVP\)。\(CVP\)是给定一个目标向量\(\vec{t} \notin \mathcal{L}\)，找离它最近的格点。
\[dist(\vec{t}, \mathcal{L}(B)) = \min_{\vec{v} \in \mathcal{L}(B)} \Vert \vec{t} - \vec{v} \Vert \]
- \(\mathcal{L}(B)\)就像是空间中无限延伸、整齐排列的离散点阵；
- \(\vec{t}\) 是空间中的任意一个“目标点”；
- \(dist(\vec{t}, \mathcal{L}(B))\) 就是指：从目标点 \(\vec{t}\) 出发，拉一条直线到离它最近的那个格点 \(\vec{v}\)，这条直线的长度。
在\(CVP\)（最近向量问题）中，我们的终极目标就是找到那个让\(dist\)取到最小值的格点 \(\vec{v}\)。
与\(SVP\)一样，对于任意近似因子\(\gamma\ge1\)，我们可以定义\(CVP\)的三个变体：
- \(Search\ CVP_{\gamma}\)：给定格基\(B\in\mathbb{Z}^{m×n}\)和向量\(\vec{t}\in\mathbb{Z}^m\)，求\(\vec{v}\in\mathcal{L}(B)\)，使得\(\Vert\vec{v}-\vec{t}\Vert\leq\gamma\cdot dist(\vec{t},\mathcal{L}(B))\)；
- \(Optimization\ CVP_{\gamma}\)：给定格基\(B\in\mathbb{Z}^{m×n}\)和向量\(\vec{t}\in\mathbb{Z}^m\)，求数值\(d\)，使得\(dist(\vec{t},\mathcal{L}(B))\leq d\leq\gamma\cdot dist(\vec{t},\mathcal{L}(B))\)；
- \(Promise\ CVP_{\gamma}(Gap\ CVP_{\gamma})\)：给定\((B,\vec{t},r)\)，其中\(B\in\mathbb{Z}^{m×n}\)是格基，\(\vec{t}\in\mathbb{Z}^m\)，\(r\in\mathbb{Q}\)。
- \(YES\)实例：\(dist(\vec{t},\mathcal{L}(B))\leq r\)；
- \(NO\)实例，\(dist(\vec{t},\mathcal{L}(B))> \gamma\cdot r\)。
已知存在多项式时间的规约使得\(SVP_\gamma \le_p CVP_\gamma\)。直观上讲，\(CVP\)比\(SVP\)更难，因为\(CVP\)可以将目标点 \(\vec{t}\) 设为空间中的任意位置，而\(SVP\)相当于目标点固定在原点，且不能输出原点本身。
\(Others\)
\(SVP\)和\(CVP\)都是格中困难的计算问题，还存在一些格中容易计算的问题：
厄尔特标准型(\(HNF\))
任意一个整数矩阵\(B \in \mathbb{Z}^{m \times n}\)，都可以通过初等列变换（且只能是整数倍的加减或交换，等价于右乘一个行列式为 \(\pm 1\) 的幺模矩阵 Unimodular Matrix）转化为一个唯一的标准形式。
定理： 两个格基\(B_1\)和\(B_2\)生成完全相同的格，当且仅当它们的厄米特标准型完全相同，即\(HNF(B_1) = HNF(B_2)\)。
- \(Membership\)：给定格基\(B\in\mathbb{Z}^{m×n}\)和向量\(\vec{v}\in\mathbb{Z}^m\)，判断向量\(\vec{v}\)是否属于\(\mathcal{L}(B)\)。
\(Solution\)：将 \(\vec{v}\) 作为新列加入格基\(B\)形成增广矩阵\([B \vert{} \vec{v}]\)，如果其\(HNF\)与原矩阵\(B\)的\(HNF\)相同，或者通过\(HNF\)回代能求出严格的整数解\(\vec{x} \in \mathbb{Z}^n\)，则输出\(YES\)，否则输出\(NO\)。 - \(Equivalence\)：给定格基\(B_1,B_2\in\mathbb{Z}^{m×n}\)，判断\(\mathcal{L}(B_1)\)是否等于\(\mathcal{L}(B_2)\)。
\(Solution\)：计算这两个格基的\(HNF\)。如果\(HNF(B_1) == HNF(B_2)\)，则它们等价；否则不等价。
格基的等价问题在Lattices中讨论过。
\(Summary\)
跟着六三师傅的博客文章也算是学习完了格密码基础的入门课程，主要就是了解了格的定义、格的相关概念、施密特正交化、连续极小值以及格中的计算困难问题。
在看六三师傅的博客文章的时候，有些定理的证明、概念的定义，笔者按照自己的思考过程和理解进行了注释或记录，此系列文章是笔者为记录自身学习格密码的笔记，便于日后学习使用。
- Lattices
- Gram-Schmidt orthogonalization
- Successive minima
- Computational problems
- 参考资料：格密码基础 4（Lecture 1，Computational problems） - 知乎