环上 Learning With Errors

普通 LWE 的每个样本给出一个随机向量与秘密的点积；Ring-LWE 用随机环元素 $a$ 的乘法算子一次混合秘密的全部嵌入坐标。选定整数基后，乘法成为一个高度结构化的 $n\times n$ 矩阵，因此一个环样本看似带来多条标量关系，也同时引入循环、理想和共轭结构。

这种结构带来紧凑表示与快速多项式乘法，却不会自动继承无结构 LWE 的所有定理。展开坐标后得到的矩阵只来自“乘以 $a$”这一 $n$ 维算子族，而不是从全部 $n\times n$ 矩阵均匀采样；两者的实例分布因此不同。

canonical embedding 使误差的几何与理想格归约对齐。幂基中的独立同分布系数只有在基近似正交且参数已换算时才接近球形误差；一般数域中基的条件数会把系数小误差拉成强烈各向异性。

取玩具环 $R=\mathbb{Z}[x]/(x^2+1)$、$q=7$，令

利用 $x^2=-1$，有

故样本第二分量为 $b=1+4x\in R_7$。把 $a=u+vx$ 写成系数向量时，“乘以 $a$”对应矩阵

这直观显示环样本的两条标量方程共享结构，并非两个独立均匀 LWE 行。例子只演示代数，$n=2$ 没有安全意义。

商环还可能含零因子。模 $5$ 时 $x^2+1=(x-2)(x+2)$，两个非零类相乘为零。于是普通素数模 LWE 搜索—判定归约理路LWE 搜索—判定归约LWE search-to-decision reduction · LWE 搜索判定转换在素数且多项式大小模数等明确条件下，用判定 LWE 区分器恢复搜索 LWE 秘密的经典归约。中“错误猜测差非零便可逆”的步骤会失败；随机改动单个系数还可能破坏乘法矩阵族和 canonical 误差分布。Ring-LWE 的 search-to-decision 定理必须利用数域自同构、素理想分解及误差族的不变性，并只对相应的环和模数成立。同样的非零性条件在这两个环中产生不同的可逆性结论。

数域选择也不能只看多项式次数。非单生成整数环、坏条件幂基、分歧模数及不正确的复嵌入缩放都会改变误差与归约。实现若改用舍入 Gaussian 或中心二项分布，应把它当作新误差假设或给出到理论族的具体比较。

在适当数域族、模数与误差宽度下，Ring-LWE 的困难性可由理想格上的最坏情形近似问题归约支持。结论涉及的是特定 ideal-SVP/SIVP 类问题与 canonical/dual 误差族，不是一般格 SVP 的同参数副本；原始归约中的量子或经典性质也应按所引定理保留。

环结构允许用 NTT 或其他快速乘法压缩密钥并加速加密、签名和同态运算。性能优势取决于 $q$ 是否支持所需单位根、所选基与常数时间实现；它不证明安全。Module-LWE理路模上 Learning With ErrorsModule Learning With Errors · Module-LWE · MLWE · 模 LWE在数域商环上的有限秩自由模中以结构化内积和嵌入误差隐藏秘密的学习问题。把秘密提升为环模上的向量。本页已固定的 primal Ring-LWE 正是该页同样 primal 定义在模秩 $d=1$ 时的特殊情形：保持 $K,q,\mathcal{S},\chi$ 和样本预算不变，将 $s,a$ 分别视为一维向量 $(s),(a)$，内积就成为乘积 $as$，两种实验完全相同。这个识别不把 primal 表示与另行讨论的 dual 表示混用；更高模秩也仍有自己的归约参数。

具体同态方案还要管理密文表示。重线性化理路同态乘法后的重线性化Relinearization在明确的模数与低位消息模型中，把同态乘法产生的秘密平方项用基数分解和求值密钥压回线性密文，并核算新增噪声。把乘法产生的秘密高次项压回较短解密基，但新增辅助密钥噪声；模数切换理路同态密文的模数切换Modulus switching逐坐标缩放舍入LWE型密文，推导消息编码偏移与秘密范数造成的新误差，区分绝对噪声变小、相对噪声和BGV保明文舍入。则按消息编码选择缩放舍入规则。两页先在标量模型中展开恒等式，迁移到环上时仍须加入所选范数下的乘法放大与误差分布，不能仅因都叫 LWE 就沿用标量界。