用入门教材揭秘基于格的 FHE：LWE 硬度与基本加密方案的逐步简化证明

全同态加密（FHE）允许在加密数据上直接进行计算，而无需解密，这在隐私保护计算中至关重要。基于格的 FHE 方案因其后量子安全性和理论基础而备受关注。本文以入门教材视角，逐步简化 LWE（Learning With Errors）问题的硬度证明，并介绍基本加密方案，帮助工程人员建立直觉，避免复杂数学细节。

LWE 问题的定义与直觉

LWE 问题源于格论，是基于格 FHE 的核心假设。想象一个 n 维向量空间中的离散点集（格），由基向量生成。LWE 模拟 “带噪声的学习”：给定矩阵 A ∈ Z_q^{m×n}（q 为模数）和向量 b = A s + e mod q，其中 s 是秘密密钥，e 是小噪声向量（从离散高斯分布采样）。攻击者需区分（A,b）是否来自 LWE 分布，还是随机均匀分布。

工程直觉：噪声 e 确保加密的安全性，但过大则解密失败。典型参数：n=256（维度），q≈2^{32}（模数），噪声标准差 σ≈3√n，确保噪声小于 q/4 以支持解密。

LWE 硬度的简化证明步骤

LWE 的硬度基于最坏情况格问题，如 GapSVP（Gap Shortest Vector Problem）：判断格中最短向量长度是否小于阈值 γ。经典规约证明显示，解决平均情况 LWE 等价于最坏情况格问题，即使在经典计算机上（Regev 等，2013）。

步骤 1：从 GapSVP 到 SIS（Short Integer Solution）。假设能解决 SIS（找到短向量 x 使 A x =0 mod q），则可构造格实例，寻找短向量对应格中的解。

步骤 2：LWE 到 SIS 的规约。LWE 样本可用于生成 SIS 实例。通过嵌入和噪声控制，将 LWE 的平均硬度规约到格的最坏硬度。简化的量子规约（Regev,2005）使用傅里叶分析：LWE 决策版本通过量子降维（从 n 到 O (√n)）降低到搜索 LWE，然后到 SVP。

证据：若存在多项式算法解决 LWE，则可高效近似 SVP 到因子 O (n)，这是格问题的已知最优近似。实际中，BKZ 格约化算法可攻击小 n 实例，但 n>500 时安全。

工程清单：验证硬度 —— 使用 LWE 估计器工具估算 BKZ 块大小 β>100 确保 128 位安全。风险：小 q 或大噪声易受格约化攻击，回滚策略：增加 n 或 q。

基于 LWE 的基本加密方案

Regev 方案（2005）是 LWE 的公钥加密基础。密钥生成：秘密 s ∈ Z_q^n，公钥 (A, b= A s + e)。

加密明文 m（0 或 1）：选择短向量 r，密文 c = (A^T r, b^T r + m * floor (q/2)) mod q。

解密：c_2 - s^T c_1 mod q，若噪声小则≈ m * floor (q/2)。

同态性：加法自然支持（c1 + c2 解密 m1 + m2 mod q）；乘法需键切换（key-switching）管理二次噪声增长。

简化证明：语义安全基于 LWE 决策假设 —— 攻击者无法区分加密 0 和 1，因为噪声使 b^T r + m * floor (q/2) 似随机。

参数落地：对于 128 位安全，n=300, q=2^{13}, 噪声 χ= 均匀 [-1,1]。支持 L=5 级乘法（leveled FHE），噪声预算 < q/4。监控点：噪声范数 ||e||<√(2n)σ。

FHE 扩展：噪声管理与引导

Gentry 方案（2009）将 LWE 加密扩展到 FHE，通过引导（bootstrapping）刷新噪声：当噪声接近阈值时，评估解密电路自身，生成新低噪密文。

步骤：1. 构建支持加 / 乘的有些同态加密（SHE）。2. 用 SHE 加密解密密钥。3. 同态评估解密函数，刷新密文。

工程直觉：引导开销高（每乘法后需刷新），优化为 CKKS 方案（Ring-LWE 变体），支持浮点近似计算。参数：环度 N=2^{14}, q=[X1...Xk]（RTF 分解），支持深度 D=20 电路。

引用："LWE 问题的经典硬度证明显示，即使多项式模 q，LWE 也至少如标准最坏情况格问题硬"（Brakerski 等，2013）。

清单：实现 FHE—— 用 HElib 库，设置 n=1024, 模链 q_i 下降控制噪声。回滚：若噪声溢出，切换到部分同态模式。阈值：乘法后噪声增长 2 倍，引导阈值 q/2。

工程直觉与局限

基于格 FHE 的优势：抗量子，通用计算。但局限：计算慢（毫秒级操作），密文大（KB 级）。直觉：视噪声为 “预算”，每运算消耗一点，引导如 “充值”。

实际参数：NIST PQC 标准中，Kyber（LWE-based KEM）用 n=256, q=3329，支持 FHE 扩展。监控：用噪声估计器跟踪 ||e||，若 > 阈值则刷新。

通过这些简化步骤，工程人员可从教材视角把握 LWE-FHE 本质：硬度源于格几何，方案靠噪声平衡安全与功能。未来，优化如 TFHE 将推向实用。

（字数：1025）