📚 课程目录第3章格中的困难问题

3. 格中的困难问题

格密码的安全性并不依赖“格上某个问题很难解”这一句口号，而是依赖一组定义精确、难度可比较、并且能相互归约的困难问题。理解这些问题的定义与归约关系，是后续判断参数是否安全、选择困难问题作为构造基础的前提。本节围绕三个核心问题展开：最短向量问题（SVP）、最近向量问题（CVP）、最短独立向量问题（SIVP），并说明它们的近似变种与相互归约方向。

一、先固定记号与判定约定

设格 L 由基 B = {b₁, …, b_n} 生成，记 L(B) = { Σ z_ib_i : z_i ∈ ℤ }，维数为 n。向量长度统一取欧几里得范数 ‖·‖。格中最短非零向量的长度记为 λ₁(L)；更一般地，λ_i(L) 表示第 i 个 successive minimum，即在保证前 i−1 个向量线性无关的前提下，第 i 个线性无关短向量的最小长度。全文所有“短”“近”均指欧氏长度，方向与正负号不影响长度判定。

二、三个核心问题的定义

SVP（最短向量问题）：给定格 L，求一个非零向量 v ∈ L，使得 ‖v‖ = λ₁(L)。判定版本则问：是否存在非零 v ∈ L 满足 ‖v‖ ≤ r。SVP 只关心格本身，不涉及外部目标点，因此它是“格内禀”的困难问题。

CVP（最近向量问题）：给定格 L 与目标点 t ∈ ℝⁿ，求 v ∈ L 使 ‖t − v‖ 最小。判定版本问：是否存在 v ∈ L 使 ‖t − v‖ ≤ r。CVP 引入了目标点，衡量的是“格点逼近任意点的能力”，在编码译码、噪声消减中直接出现。

SIVP（最短独立向量问题）：给定格 L 与整数 k，求 k 个线性无关的格向量 v₁, …, v_k，使 max_i ‖v_i‖ 尽可能小，其最优值即 λ_k(L)。当 k = 1 时 SIVP 退化为 SVP；当 k = n 时要求给出整组短基，这正是格基约化追求的目标。

三者的直观区别：SVP 问“格内最短的非零向量有多短”，CVP 问“格点离给定点多近”，SIVP 问“能同时找到多少个互相独立的短向量”。SVP 与 SIVP 是格的内禀性质，CVP 依赖外部目标点。

三、近似变种：从精确到可判定

精确 SVP 与 CVP 在一般格上都是 NP 困难的，直接作为密码构造的基础并不方便。密码学实际使用的是它们的近似版本，用近似因子 γ = γ(n) ≥ 1 刻画“允许差多少”：

SVP_γ：求非零 v ∈ L 使 ‖v‖ ≤ γ · λ₁(L)。
CVP_γ：求 v ∈ L 使 ‖t − v‖ ≤ γ · dist(t, L)。
SIVP_γ：求 k 个线性无关格向量，使 max_i ‖v_i‖ ≤ γ · λ_k(L)。

此外还有判定版本 GapSVP_γ：给定 r，承诺 λ₁(L) ≤ r 或 λ₁(L) > γr 二者必居其一，要求判定属于哪种情形。Gap 版本把“求值”弱化为“区分”，是许多密码安全性证明中更自然的困难假设形式。γ 越大问题越容易，γ 接近 1 时问题越接近精确版本、越困难。

四、相互归约关系

归约方向决定了“哪个问题更难”。若问题 A 可归约到问题 B（记 A ≤ B），则解 B 的算法可用来解 A，说明 B 至少和 A 一样难。核心结论如下：

SVP ≤ CVP：给定格 L，构造嵌入格 L' = L ⊕ ℤ·c（c 为足够大的常数向量），把 SVP 转化为在 L' 上对目标点 t = c 求最近向量，所得最近向量之差即给出短向量。因此 CVP 不比 SVP 容易。
SIVP_γ ≤ CVP_γ：反复调用 CVP 预言机，每次求得一个短向量后将其从格中“剔除”（投影到正交补），迭代 k 次即得 k 个线性无关短向量。这说明 CVP 是三者中最“强”的困难问题。
GapSVP_γ ≤ SVP_γ：精确/近似求解 SVP 后与阈值 r 比较即可判定 Gap 版本，故 Gap 版本是更弱的假设。
SVP 是 SIVP 的特例：k = 1 时 SIVP 即 SVP，因此 SVP ≤ SIVP；反过来 SIVP 要求整组短基，通常比 SVP 更难，二者在近似因子足够大时可相互转化。

归约方向容易记反：箭头从“较容易/较弱的问题”指向“较难/较强的问题”，含义是“前者可归约到后者”。CVP 位于归约链的上游（更难），SVP 与 GapSVP 位于下游（更弱）。在安全性论证中，若方案基于 CVP 困难性，则它同时继承了 SVP 与 SIVP 的困难性；反之不成立。

五、参数安全分析中的实际用法

在评估一个格密码方案时，通常按以下逻辑使用上述关系。首先确定方案的安全性最终归约到哪个问题，例如 LWE 类方案常归约到 GapSVP_γ 或 SVP_γ，而基于格的签名有时直接依赖 SIS/SIVP 类假设。其次根据归约链判断：如果攻击者能解 CVP_γ，则也能解 SVP_γ 与 SIVP_γ，因此只需评估最弱环节的实际攻击代价。最后把近似因子 γ 与格维数 n、模数 q、噪声宽度等参数对应起来，用格基约化（如 BKZ）的复杂度估算所需安全强度。

举一个教学示例（参数为合理假设，非实测结果）：设维数 n = 512，模数 q = 12289，噪声参数使归约得到的近似因子约为 γ ≈ n/log n 量级。此时 GapSVP_γ 的判定间隙较宽，攻击者需要运行 BKZ 分块大小约数百的约化才能触及该间隙，对应估算的安全级别在 128 位上下。若把 γ 调小（更接近精确 SVP），问题变难、安全性提高，但方案可用的参数空间也随之收窄，需要在安全性与效率之间权衡。这一权衡正是后续参数选择章节的核心。

问题	输入	目标	归约地位
SVP_γ	格 L	非零 v，‖v‖ ≤ γλ₁	较弱，可归约到 CVP
CVP_γ	格 L、目标点 t	v，‖t−v‖ ≤ γ·dist	较强，归约链上游
SIVP_γ	格 L、整数 k	k 个无关短向量	k=1 退化为 SVP
GapSVP_γ	格 L、阈值 r	判定 λ₁ ≤ r 或 > γr	最弱，判定化形式

掌握这些定义与归约方向后，面对一个具体方案时就能回答两个关键问题：它的安全性最终依赖哪个格问题，以及该问题在给定参数下是否仍处于困难区间。这是格密码参数安全分析的第一步，也是后续讨论具体攻击算法与安全估算方法的共同基础。