2.1 格与误差学习：新地基

2.1 格与误差学习：新地基

本节摘要：全同态的地基不是整数环，而是格——由基向量整系数组合生成的点阵。带误差学习问题（LWE）及其环上版本（RLWE）把"在格上找最近点"的困难性转化成加密的构造块。本节讲清格、最短向量与最近向量问题，推导 LWE 的采样形式与安全性归约，给出环上版本的性能红利，并落到贯穿全册的参数记号：多项式模数维度、系数模数、噪声分布。

为什么必须是格

破冰之前先问一句：Gentry 为什么不沿用 RSA 或 Paillier 的数论地基？三个理由决定了换地是必然。其一，旧地基的运算守恒只覆盖一种运算，而任意计算需要加乘并存，数论群给不出这样的双重结构。其二，安全性账本不一样：大整数分解与离散对数会被量子算法（Shor 算法）多项式时间解决，而格上的问题在量子模型下仍无多项式算法——这份"后量子"属性当时是副产品，如今已是主要卖点。其三，也是最关键的，Regev 在二零零五年证明了著名的"最坏情况到平均情况"归约：随机生成的 LWE 实例的困难性，可以归约到格上最难实例的困难性。传统密码的安全性论证只能说"攻破它至少不比解某困难问题容易"，而格密码能说"攻破随机实例等于解最坏情况的格问题"。随机生成即最硬，这对需要海量密文做运算的同态场景是量身定制的性质。

格本身并不神秘：取一组线性无关的基向量，它们所有整数系数组合构成的点集就是格。二维直觉最好建立——平面上斜交的两支箭头织出一张斜网，网上的每个结点都是格点。困难问题围绕"基与点的几何关系"展开：最短向量问题问"这张网里离原点最近的结点在哪"，最近向量问题问"给一个不在网上的点，哪个结点离它最近"。理解其困难性的钥匙是"基的形态"：同一张格可以由又短又正交的"好基"表示，也可以由又长又斜的"坏基"表示。用好基，最近点可以像投影子一样快速求出；用坏基，同样的计算变成盲人摸象。把好基留作私钥、坏基公开，"容易与困难"的落差就是密码学的全部戏法——这与上一章"结构决定能力"一脉相承，只是结构从群换成了点阵的几何。

图：二维格上的最近向量问题

误差学习：把"噪声"从敌人做成构件

格上直接构造加密仍然笨重，真正的工程转机是 Regev 提出的误差学习问题。它把格问题包装成一个极其朴素的猜谜：取一个秘密向量，攻击者能看到大量样本，每个样本是一个随机向量，配上"随机向量与秘密向量的内积、再加一点小误差、对模数取余"。任务是恢复秘密向量。没有那一点误差时，这是线性代数课后题——几百个样本高斯消元即可；加了误差后，每个样本都带着一位"测不准"，消元过程像在雾里解方程，所有已知算法都指数级退化。误差的分布通常取离散高斯，标准差参数很小（实用实现里常取三点二左右），小到不影响解密，大到淹没代数攻击。

上一章的"噪声之墙"在此完成角色反转：噪声从方案的缺陷变成了安全性的来源。这也是本册演化主线上最富戏剧性的一次换位——第一代的答案不是消灭噪声，而是与噪声共生：加密者知道噪声小到不干扰解密，攻击者却无法在误差海洋里分离信号。带误差的方程组同时服务两个主人，精确解给持有密钥的人，模糊视图给所有人。

环上版本（RLWE）是性能的第二次跃迁。把秘密向量换成环里的一个多项式，样本变成"随机多项式配上其与秘密的乘积加误差多项式"，所有运算在一个固定的多项式环里进行。红利来自代数结构：一次环上乘法相当于批量完成数千次向量运算，密钥与密文的尺寸按比例缩小。环取"系数模数为二的幂次的多项式、除以某加一的幂次多项式"的标准形态，维度取二的幂（一千零二十四到三万二千七百六十八），这样多项式乘法可以借助数论变换以近乎线性的复杂度完成——第四章会专门拆解这台发动机。安全性上，环上版本在"理想格"假设下与最短向量问题挂钩，假设略强于一般 LWE，但十多年的公开密码分析没有找到实质差距，产业界全盘接受了这笔交换。

参数记号：全册通用的三个旋钮

从本节起，全册反复出现三个参数，先把记号和典型取值钉死。维度（多项式模数的次数，记作环上维度）决定安全强度与单个密文的吞吐量；系数模数（记作模数链的比特长度）决定噪声预算的上限；明文模数（整数明文所在的模）决定能表示的整数范围。社区标准推荐的组合可以列成一张表：

读这张表要有两个心眼。第一，安全强度不是随维度平滑增长的，它由"维度与模数之比"共同决定——模数越大（为了更深的电路），同样的维度越不安全，所以深电路与高安全只能靠加维度来两全。第二，槽位列预告了第三章的打包技术：一个密文不是装一个数，而是按中国剩余定理装下维度一半数量的明文槽。参数选择的完整决策流程在第四章安全性一节展开，包括如何用公开的估计器核算核心困难度。

动手采样：亲手生成一个 LWE 实例

纸面记号不如亲手跑一遍。下面这段 Python 在极小参数下生成 LWE 样本，并演示"去误差后可解、带误差后消元失稳"的对照——它是后续所有方案加密算法的最小内核。

import random

# 小参数教学版 LWE：维度 n=4，模数 q=97，噪声取自小范围
n, q = 4, 97
secret = [random.randint(0, q - 1) for _ in range(n)]   # 秘密向量 s

def sample(noise=True):
    a = [random.randint(0, q - 1) for _ in range(n)]
    inner = sum(ai * si for ai, si in zip(a, secret)) % q
    e = random.randint(-2, 2) if noise else 0            # 离散小噪声
    return a, (inner + e) % q, e

# 无误差版本：线性代数直接可解（演示"为什么必须加噪声"）
rows, rhs = [], []
for _ in range(n):
    a, b, _ = sample(noise=False)
    rows.append(a); rhs.append(b)
# 高斯消元后能精确恢复 secret —— 无噪声的 LWE 是课后习题

# 带误差版本：每个方程偏一点，消元误差传播，解出的一组候选全部偏离
for i in range(3):
    a, b, e = sample(noise=True)
    print(f"样本{i}: 噪声 e = {e:+d}, 观测值 = {b}")
# 打印出的观测值与真实内积之差始终在正负二之间抖动——
# 维度放大到数千、样本数十万时，这层薄雾足以挡住所有已知攻击
​

把这段代码的维度与模数换成上表的实用组合，采样逻辑一字不改——它就是 BFV、CKKS、TFHE 共用的加密内核。区别只在"明文放进去的姿势"与"误差管理的方式"，这正是第三章的主题分化。

本节要点回顾

• 要点一：换格地基的三个理由——加乘并存的双重结构、抗量子属性、最坏情况到平均情况的归约（随机实例即最硬实例）
• 要点二：格上困难性的钥匙是基的形态，好基私钥快速解最近向量问题，坏基公钥让搜索爆炸
• 要点三：LWE 把噪声从缺陷反转为安全构件，离散高斯误差让线性方程组从课后题变成指数难题；RLWE 用环结构换取数量级的密钥与运算压缩
• 要点四：全册参数三旋钮——环维度定安全与吞吐、系数模数定噪声预算、明文模数定整数范围；深电路与高安全只能靠加维度两全

延伸：从向量到环的跃迁细节

向量版本到环版本的跃迁，中间有一处容易被教程略过的关键细节：环上样本的"维度折叠"。向量版里，一个密文对应一组独立的标量系数；环版本里，密文是一个多项式，一次环乘等价于做完全部"移位相乘"的卷积。这个折叠带来效率，也带来约束——卷积让所有系数互相纠缠，攻击面与优化空间同时出现（选择特殊的环参数让卷积可被数论变换加速，是第四章的内容）。用建筑比喻：向量版是砖混结构（每面墙独立），环版是整体浇筑（结构一体、省料但拆改不便）。理解这层差别，后面看到"环上版本在理想格假设下安全"的措辞时，就知道那份额外假设正是"浇筑整体性"的价格。

另一处值得补的细节是噪声分布的选择。工程实现普遍用离散高斯分布（而非均匀分布）采样误差，原因有三：高斯的尾部衰减快，解密失败概率可以被紧致控制（参数设计时给出可证明的小失败率）；归约定理的陈述以高斯为标准形态；实现层的采样算法（累积分布表或拒绝采样）高效且可做成常数时间。标准差这个不起眼的参数（常见取三点二左右）直接进入安全估计器的输入——它是"安全强度"与"解密正确性"两本账共同的入账科目。

常见问题：维度的安全档是怎么定的

一个高频疑问：为什么一千零二十四维度的档位会"被蚕食"？安全位不是维度的固定函数，而是维度、模数、噪声分布三者的联合结果——攻击算法的进步改变了这个函数的形状。早期档位（约二十七比特模数配千级维度）在发布时按当时的最好攻击核算达标，数年后筛法类算法的常数项改进让它跌破线，社区随之上调推荐下限。这个过程会持续发生，所以工程纪律是"参数只从现行标准取、核算记录可追溯"（第四章的完整清单）。把安全位理解为"会贬值的资产"而不是"不变的属性"，是与十年前的工程文档拉开差距的认知。