“先采用Regev 型高位消息编码。设密文 $c=(v,u 1,\ldots,u n)$,整数秘密向量 $t=(1, s 1,\ldots, s n)$,满足”
形式陈述
Regev 加密把LWE 样本组成公钥,再通过随机子集和加密一位。[1, §5] 设维数
作为公钥加密,算法为:
- 密钥生成:均匀抽
、 ,独立抽 ,令 。公开 ,保留 - 加密
:新鲜均匀抽取 ,输出 - 解密:计算
,按圆周模距离判断它更接近0还是 ,输出对应比特;平局规则预先固定
正确性需要子集误差保持在判决间隔内。一个明确充分条件是
这里
安全证明还需要随机子集有足够熵。令
应使
直觉
每条公钥方程都有相同秘密
消去后只剩一团小噪声。要发送0,把这团噪声放在模圆周的零点附近;要发送1,把它移到大约半圈之外。私钥持有者知道怎样去掉线性掩码,因此能辨认两团;外部观察者的区分能力由 LWE 与子集和的统计接近性一起排除。
例子与边界
在模97中逐项消去
取
| 行 | |||
|---|---|---|---|
| 1 | 1 | 42 | |
| 2 | −1 | 28 | |
| 3 | 2 | 44 | |
| 4 | −2 | 40 |
取
发送1时
49离48只有1,离0的圆周距离为48,因此解出1。发送0时只有
这个例子的
严格的间隔为何是Δ/2
正确消去时总有
0与
若发送1而总误差变为26,则残差为74。它离48为26,离0只需反向走23,解密反而输出0。错误来自噪声跨过判决区间,不是模线性消元本身算错。
推论与应用
两段安全替换各做什么
先用混合论证把公钥
现在记均匀矩阵
这证明
关键是连同公钥比较,而不只是说密文的边缘看起来随机。给最后一坐标加
公钥需要
GSW把许多这样的线性掩码组织成具有 gadget 结构的矩阵,模数切换则进一步分析缩放与舍入如何改变解密残差。两者都仍需独立核算误差预算。
参考资料
- [1] Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, JACM 56(6), 2009,§5,特别是 Lemma 5.1 的精确正确性间隔与随后随机子集和、安全证明。本文把统计误差余量直接写成式 (2)。