Regev 的 LWE 公钥加密

每条公钥方程都有相同秘密 $s$。随机选若干行相加后，线性部分仍可用同一个 $s$ 消掉，但外部人不知道选了哪些行，也不知道秘密。

消去后只剩一团小噪声。要发送0，把这团噪声放在模圆周的零点附近；要发送1，把它移到大约半圈之外。私钥持有者知道怎样去掉线性掩码，因此能辨认两团；外部观察者的区分能力由 LWE 与子集和的统计接近性一起排除。

在模97中逐项消去 ​

取 $q=97,n=2,m=4$、$s=(3,5)$，选下面一组教学公钥样本：

取 $r=(1,0,1,1)$。于是

发送1时 $\mathrm{\Delta }=48$，故 $v=29+48=77$。私钥计算 $s^{T}u=3\cdot 15+5\cdot 16=125$，得到

49离48只有1，离0的圆周距离为48，因此解出1。发送0时只有 $v=29$ 改变，残差变成1，解出0。

这个例子的 $m=4$ 明显不足以满足式 (2)：四个选择比特不可能把输出铺满 ${97}^3$ 个点。它只用于验证代数与判决，不用于展示安全参数。

严格的间隔为何是Δ/2 ​

正确消去时总有

0与 $\mathrm{\Delta }$ 之间两条圆弧长度为 $\mathrm{\Delta }$ 和 $q-\mathrm{\Delta }$，较短者是 $\mathrm{\Delta }$。所以距离各中心严格小于 $\mathrm{\Delta }/2$ 的邻域不会混淆。对 $q=97$，这给出24，而不是把 $q/4=24.25$ 当作精确边界。

若发送1而总误差变为26，则残差为74。它离48为26，离0只需反向走23，解密反而输出0。错误来自噪声跨过判决区间，不是模线性消元本身算错。

两段安全替换各做什么 ​

先用混合论证公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。把公钥 $(A,As+e)$ 换成均匀 $(A,b)$。若攻击者能分辨这一步，就得到该参数与样本预算的判定 LWE 区分器；归约可直接用给定公钥运行公开加密。

现在记均匀矩阵 $H=(A\mid b)\in {\mathbb{Z}}_q^{m\times (n+1)}$。对不同二进制向量 $r,r^{\prime }$，差向量至少一项为 $1$ 或 $-1$，该项在任意模 $q$ 下都可逆。因此对每个独立均匀列，$H^T(r-r^{\prime })$ 的对应坐标均匀；同时为零的概率为 $q^{-(n+1)}$。

这证明 $r\mapsto H^{T}r$ 是二通用哈希族。剩余哈希引理的有限输出集版本公理库剩余哈希引理Leftover hash lemma · LHL二通用哈希把弱随机源压缩为公开种子和经典旁信息后仍接近均匀的输出，误差由平均条件最小熵控制；条件化与 Jensen 不等式给出证明，三比特例子精确算出联合距离。取 $\mathcal{Y}={\mathbb{Z}}_q^{n+1}$，在公开 $H$ 的联合分布中给出

关键是连同公钥比较，而不只是说密文的边缘看起来随机。给最后一坐标加 $\mu \mathrm{\Delta }$ 不改变均匀分布，因而两个挑战消息在这个混合世界中的距离至多 $2\eta$。把前后 LWE 替换的优势一起加回，就得到计算保密界。

公钥需要 $(mn+m)\lceil {\log }_{2}q\rceil$ 位量级，单比特密文为 $(n+1)\lceil {\log }_{2}q\rceil$ 位量级。直接加密使用 $O(mn)$ 次模加法，解密用 $O(n)$ 次模乘加。普通 Regev 密文直接相加会累计误差与消息编码；它并没有凭这个性质自动获得不限深度的乘法接口。

GSW公理库GSW 近似特征向量同态加密GSW encryption · GSW approximate-eigenvector encryption把明文变为密文矩阵关于秘密gadget向量的近似特征值，用Flatten维持小系数，并逐门证明NAND误差递推与深度预算。把许多这样的线性掩码组织成具有 gadget 结构的矩阵，模数切换公理库同态密文的模数切换Modulus switching逐坐标缩放舍入LWE型密文，推导消息编码偏移与秘密范数造成的新误差，区分绝对噪声变小、相对噪声和BGV保明文舍入。则进一步分析缩放与舍入如何改变解密残差。两者都仍需独立核算误差预算。