LWE 搜索—判定归约

判定器看似只回答“一批样本像不像 LWE”，变换却把一个秘密坐标的猜测编码成两种截然不同的分布。猜对时只是沿秘密超平面同步移动 $a$ 与 $b$；猜错时，多出的非零斜率乘均匀 $r$，把等式右侧洗成均匀噪声。逐个尝试候选，便把区分能力变成恢复能力。

素数条件服务于“每个非零差都有逆”。在合数环 ${\mathbb{Z}}_q$ 中，错误候选之差可能是零因子，$r(g-s_i)$ 只覆盖一个真子群，变换后的样本既非标准 LWE 也非均匀。某些合数、素数幂或 CRT 版本有专门归约，但必须按其因子结构重写，不能沿用上述一句可逆性。

反方向上，搜索器若恢复候选秘密，可用独立样本检查残差是否符合集中误差族，从而构造判定器；这也需要误差与均匀分布可区分、验证样本独立等条件。因此“搜索与判定等价”始终是带参数的定理族，不是两个定义相同。

取 $q=5$、秘密 $s=(2,4)$，测试第一坐标。对任一样本 $(a,b)$，选独立 $r$ 并做上述变换。候选 $g=2$ 时

所以整批仍有原误差分布。若误猜 $g=1$，则残差为 $e-r$；当 $r$ 遍历 ${\mathbb{Z}}_5$ 时，$e-r$ 对每个固定 $e$ 都均匀遍历五个剩余类。判定器的接受率因而可分辨两个候选。真实归约要用多批样本估计接受概率，单个样本没有足够统计意义。

若改成 $q=6$ 且真实坐标为 $1$、候选为 $3$，差为 $2$。$2rmod6$ 只取 $0,2,4$，错误猜测不会产生均匀残差；素数证明在此断裂。若 $q\approx 2^n$，即使模数为素数，枚举所有候选也变成指数时间，经典结论的效率同样丢失。

这套坐标随机化也不能直接搬到结构化 Ring-LWE公理库环上 Learning With ErrorsRing Learning With Errors · Ring-LWE · RLWE · 环 LWE在数域整数环的有限商上以环乘法隐藏秘密、并按 canonical embedding 指定误差的结构化学习问题。。商环中的非零猜测差可能不是单位；更重要的是，随机改一个系数不一定保持“由环乘法矩阵产生样本”和 canonical-embedding 误差族。Ring-LWE 的搜索—判定结果要利用理想分解、环自同构及误差不变性，并只在相应数域与模数条件下成立。

search-to-decision 归约允许以更适合安全游戏的判定假设支撑加密，同时把攻击判定分布的算法转化为恢复秘密的算法。归约损失会影响优势、样本数和运行时间，具体方案不能只写“search = decision”后忽略这些量。

将它与最坏情形归约串接时应画出方向：最坏情形格实例通过（原始结果中的量子）算法调用搜索 LWE 求解器，再由本页的经典算法用判定 LWE oracle 实现搜索求解。后续经典困难性结果改变了前半段的条件，不能反向改写历史定理。