最近向量问题

格把空间划分成 Voronoi 区域：每个区域内的目标都由同一格点解码，边界上的目标则可能有多个同距答案。CVP 是判断目标落入哪个平移区域，而不只是把某组基坐标独立舍入。

当基正交时，逐坐标舍入确实最优；基倾斜后，一个方向的舍入会改变另一个方向的残差，独立决策可能失败。Babai 最近平面法借助 Gram–Schmidt 逐层舍入，能给近似保证，却不能在一般基上冒充精确 CVP。

与 SVP 相比，CVP 多了任意目标。令 $t=0$ 时最近格点是零，而 SVP 明确寻找非零点，所以“CVP 在零目标上的特例”不是 SVP。二者之间的复杂性归约需要构造额外实例，不能靠这句代入完成。

令 $\mathrm{\Lambda }=2{\mathbb{Z}}^2$，$t=(1.1,2.9)$。候选 $(2,2)$ 的平方距离为

而 $(0,2)$、$(2,4)$、$(0,4)$ 的平方距离依次为 $2.02,2.02,2.42$；其余格点更远，所以唯一最近点是 $(2,2)$。若把目标改成 $(1,1)$，四个点 $(0,0),(2,0),(0,2),(2,2)$ 都距其 $\sqrt{2}$，唯一性消失但 CVP 仍有合法答案。

对低秩格 $\mathrm{\Lambda }=\mathbb{Z}(1,0)\subset {\mathbb{R}}^2$ 与 $t=(0.4,5)$，投影目标是 $(0.4,0)$，最近格点为 $(0,0)$；实际距离是 $\sqrt{{0.4}^2+25}$，不是投影线上的 $0.4$。忽略垂直分量会把近似比与解码噪声尺度都算错。

若已承诺 $\mathrm{dist}(t,\mathrm{\Lambda })<{\lambda }_1(\mathrm{\Lambda })/2$，最近点必唯一，问题进入有界距离解码公理库格上的有界距离解码Bounded distance decoding · BDD · 格有界距离解码在目标到格的距离严格小于半个最短向量尺度的承诺下恢复唯一最近格点。。等号处不能保证唯一，例如 $\mathbb{Z}$ 中 $t=1/2$ 同距于 $0$ 与 $1$。

CVP 是格量化与最近格点解码的基本模型。通信中目标可看作“格点加噪声”，正确性取决于噪声是否留在该点的 Voronoi 区域；密码学陷门则力图让持有秘密结构者能在指定半径内高效解码。

精确 CVP、近似 CVP 与有承诺的 BDD 具有不同输入集合和保证。一个算法在小噪声承诺下成功，不意味着它能处理任意目标；反之，一般 CVP 算法当然可用于 BDD，但可能完全没有密码构造要求的效率与失败概率界。