04 基本计算格问题：SVP、CVP 与 SIVP#

适用范围：计算格与格密码中的基本计算问题，使用欧氏范数。整理日期：2026-10-16。 前置笔记：03 逐次极小值与 Minkowski 定理。

上一篇说明短向量的存在与长度界；本篇明确计算任务：输入什么、需要找到什么，以及“近似”如何衡量。

约定：输入格基 $B\in\mathbb Z^{m\times n}$ 列满秩，$\Lambda=\mathcal L(B)$，使用欧氏范数。CVP 还输入目标向量 $t\in\mathbb Q^m$。

使用整数或有理数输入，是为了能够用有限比特表示问题。有理输入可以通过统一缩放转为整数输入。近似因子记为 $\gamma=\gamma(n)\ge1$；$\gamma=1$ 对应精确求解，$\gamma$ 越大，对输出质量的要求越宽松。[1，第 9—10 页，§4]

#SVP：寻找一个最短非零格向量

最短向量问题（Shortest Vector Problem，SVP）：

给定 $B$，找到

$$v\in\Lambda\setminus\{0\}, \qquad \|v\|_2=\lambda_1(\Lambda).$$

其近似搜索版本 $\mathrm{SVP}_\gamma$ 要求找到

$$\boxed{ v\in\Lambda\setminus\{0\}, \qquad \|v\|_2\le\gamma\lambda_1(\Lambda) }.$$

“非零”条件不可省略，否则总可以输出 $0$。输出也不必是输入基中的某一列，它可以是基向量的任意非零整数线性组合。[1，第 9—10 页，Search SVP 与 Search SVP$_\gamma$]

#CVP：寻找距离目标最近的格向量

定义目标 $t$ 到格的距离：

$$\operatorname{dist}(t,\Lambda) = \min_{v\in\Lambda}\|t-v\|_2.$$

最近向量问题（Closest Vector Problem，CVP）：

给定 $B,t$，找到

$$v\in\Lambda, \qquad \|t-v\|_2=\operatorname{dist}(t,\Lambda).$$

近似搜索版本 $\mathrm{CVP}_\gamma$ 要求找到

$$\boxed{ v\in\Lambda, \qquad \|t-v\|_2 \le\gamma\operatorname{dist}(t,\Lambda) }.$$

这里衡量的是到目标的距离，而非输出向量自身的长度；零向量也可以是合法答案。特别地，令 $t=0$ 时，CVP 的最优解就是 $0$，所以不能直接通过这一替换把 CVP 当作 SVP。[3，PDF 第 7—8 页，§5、Definition 9]

#SIVP：寻找一组线性无关的短格向量

最短独立向量问题（Shortest Independent Vectors Problem，SIVP）的近似版本 $\mathrm{SIVP}_\gamma$：

给定 $B$，找到 $n$ 个线性无关格向量 $v_1,\ldots,v_n$，满足

$$\boxed{ \max_{1\le i\le n}\|v_i\|_2 \le\gamma\lambda_n(\Lambda) }.$$

它以 $\lambda_n$ 为基准，因为 $\lambda_n$ 是容纳 $n$ 个线性无关格向量所需的最小半径。

需要区分：

• 线性无关不等于原格的一组基。 输出向量可以只生成原格的一个真子格。
• 所有向量共用 $\lambda_n$ 这一长度基准。 即使 $\gamma=1$，也不要求逐个满足 $\|v_i\|_2=\lambda_i(\Lambda)$。

如果要求每个向量分别满足

$$\|v_i\|_2\le\gamma\lambda_i(\Lambda),$$

对应的是逐次极小值问题（SMP），要求更强。[2，PDF 第 10 页，Definition 13、15]

#搜索、优化与判定：输出要求不同

以精确 SVP 为例：

• 搜索版本：输出一个最短非零格向量 $v$。
• 优化版本：求出最短长度 $\lambda_1(\Lambda)$。
• 判定版本：给定阈值 $r>0$，判断是否有 $\lambda_1(\Lambda)\le r$。

近似判定通常写成承诺问题 $\mathrm{GapSVP}_\gamma$。输入 $B$ 和正有理数 $r$，区分

$$\begin{cases} \text{YES},&\lambda_1(\Lambda)\le r,\\ \text{NO},&\lambda_1(\Lambda)>\gamma r. \end{cases}$$

若

$$r<\lambda_1(\Lambda)\le\gamma r,$$

输入落在承诺之外，算法无需给出规定的判定结果。

因此，$\mathrm{SVP}_\gamma$ 要求输出向量，$\mathrm{GapSVP}_\gamma$ 要求区分两类输入；讨论二者关系时需要说明具体归约。[1，第 9—10 页，§4]

类似地，$\mathrm{GapCVP}_\gamma$ 区分

$$\operatorname{dist}(t,\Lambda)\le r \quad\text{与}\quad \operatorname{dist}(t,\Lambda)>\gamma r.$$

[1，第 10 页，Promise CVP$_\gamma$]

#沿用一个二维例子

取上一篇的格

$$\Lambda=\mathbb Z\times3\mathbb Z, \qquad \lambda_1=1,\quad\lambda_2=3.$$

三个搜索问题分别可以这样理解：

• SVP：输出 $(1,0)$，其长度为 $1$。
• CVP：若目标 $t=(2/5,13/5)$，则最近格点为 $(0,3)$，距离为 $2\sqrt2/5$。
• SIVP$_1$：输出 $(2,0)$ 和 $(0,3)$ 也合法。它们线性无关，最大长度为 $3=\lambda_2$。

最后一组向量生成的是

$$2\mathbb Z\times3\mathbb Z\subsetneq\Lambda,$$

并且长度分别为 $2,3$，没有逐个达到 $\lambda_1,\lambda_2$。这同时说明了 SIVP 对“格基”和“逐次最短”的两点区别。

#来源与阅读位置

1. Oded Regev，Lattices in Computer Science，Lecture 1: Introduction，Fall 2004。主阅读位置为 §4、第 9—10 页，涵盖 SVP、CVP 的搜索、优化、判定与近似版本。原文
2. Daniele Micciancio，Minkowski's theorem，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 10 页 Definition 13、15，补充 SIVP 与 SMP。原文
3. Daniele Micciancio，The dual lattice，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 7—8 页 §5、Definition 9，对照 CVP 定义。原文

来源于 2026-09-27 核对，正文按已确认的草稿整理。

下一篇计划：《05 格基约化与 LLL 算法》，从什么样的基更利于寻找短向量开始，再连接正交化、尺寸约化和 Lovász 条件。

#引用此笔记

• 00 概览与阅读路线
• 05 格基约化与 LLL 算法
• 06 Babai 最近平面算法与近似 CVP
• 13 SIS 问题与短整数关系