格上的有界距离解码

从带噪点找回原来的格点 ​

平面上的方格点可以写成整数坐标的组合。若原本发送的是一个格点，接收时却受到小幅噪声扰动，解码就要从附近的实数点找回原来的格点。高维格公理库欧氏格Euclidean lattice · 几何数论格 · 点格内积空间中由线性无关向量的整数线性组合构成的离散加法子群。把这幅图景推广到任意线性无关的基向量。

有界距离解码（bounded-distance decoding，BDD）给这个任务附加一项承诺：目标点离格足够近。它把“最近点可能并列”的几何歧义排除，但没有自动提供找到答案的高效算法。

为什么半个最短距离足以保证唯一 ​

任意两个不同格点 $u,v$ 之差仍是非零格向量，因此 $\Vert u-v{\Vert }_2\ge {\lambda }_1(L)$。假设它们都位于 $t$ 周围半径 $\alpha {\lambda }_1(L)$ 的开球中，三角不等式给出

矛盾。所以承诺半径内最多有一个格点；承诺保证至少有一个，合起来就得到唯一答案。

严格条件 $\mathrm{dist}(t,L)<{\lambda }_1(L)/2$ 本身仍保证唯一；若允许距离等于半个最短距离，则两个最短相邻格点的中点会同时最近。因此，“小于”和“小于等于”不能在这个端点随意互换。

取 $L=2{\mathbb{Z}}^2$，有 ${\lambda }_1(L)=2$。目标 $t=(0.6,0.7)$ 到原点的距离为 $\sqrt{0.85}\approx 0.922<1$，所以落在唯一解码半径内；取 $\alpha =0.49$ 也满足上面的 $\alpha$-BDD 承诺。目标 $(1,0)$ 则正好位于 $(0,0)$ 与 $(2,0)$ 的中间，出现两个最近点。

半最短距离是统一适用的充分条件，不是每个目标都有唯一最近点的必要条件。例如 $(0.8,0.8)$ 到 $2{\mathbb{Z}}^2$ 的原点距离大于 $1$，最近点仍然唯一。它也说明：两个坐标分别小于 $1$，并不等于欧氏误差小于 $1$；坐标条件描述方框，范数条件描述圆盘。

唯一答案为什么不等于逐坐标取整 ​

对标准格 ${\mathbb{Z}}^2$，在标准正交坐标下分别取整确实能找到最近点。但输入基未必正交。同一个 ${\mathbb{Z}}^2$ 也可以由

生成。取 $t=(0.1,0.1)$，其最近格点是原点，距离 $\sqrt{0.02}\approx 0.141$，甚至满足 $\alpha =1/4$ 的 BDD 承诺。

然而，基坐标为 $B^{-1}t=(-0.9,0.1)$。把这两个系数分别四舍五入得到 $(-1,0)$，再映回原空间是 $B(-1,0)=(-1,0)$，显然不是最近点。错误不在于噪声太大，而在于倾斜的基坐标把欧氏距离扭曲了。

因此，简单系数取整的保证依赖基的几何质量。基约化与最近平面算法利用更好的基、正交化结构来控制误差；具体能解多大半径，需要算法自己的定理，不能直接从“最近点唯一”推出。某些格密码陷门提供额外的良好基或解码结构，因此持有秘密辅助信息者与只有公开基者，也未必具有相同的算法能力。[1][2]

与最近向量、编码和密码学的关系 ​

最近向量问题公理库最近向量问题Closest vector problem · CVP · 格最近向量问题给定格基和目标点，寻找与目标欧氏距离最小的格点。（CVP）允许任意目标点，要求找到最近格点；BDD 是它在近距离承诺下的限制。一个精确 CVP 算法能解相同格上的 BDD，但只处理承诺输入的 BDD 算法没有义务解决任意 CVP 实例。

在噪声表达式 $t=v+e$ 中，$v\in L$ 是信号，$e$ 是误差。BDD 要恢复 $v$；它与综合译码公理库综合译码Syndrome decoding利用校验矩阵消去码字成分，以综合定位错误陪集并选择首领；区分合法输出、正确恢复与一般译码困难性。的共同图景是“在离散合法集合中寻找带噪观测的来源”。两者的空间和距离不同：这里是欧氏格，线性码常在有限域中使用 Hamming 距离，不能把半径或复杂性结论直接互换。

LWE公理库Learning With Errors 问题Learning With Errors · LWE从带小噪声的随机线性方程中恢复秘密或区分其分布的平均情形问题。 的样本也包含结构化线性信号与小误差，但还涉及模运算、分布和参数选择。某些解码表述及归约把它与格上的近距离问题连接起来；这不表示任意 BDD 实例就是同一分布下的 LWE 实例。用于密码学时，必须同时说明维数、模数、噪声和解码半径之间的关系。[1][2]