BGV 2012 — 不用自举也能做全同态加密

待复核

是什么

想象你有一个密封的手套箱——你把两个积木锁进去，然后戴着手套在里面拼积木，全程不打开箱子。最后取出拼好的成品，用钥匙解锁，结果跟你在外面直接拼一模一样。全同态加密（Fully Homomorphic Encryption，简称 FHE）就是这个”密封手套箱”：数据始终处于加密状态，但你可以对密文做任意运算，解密后得到的结果和直接对明文运算完全一致。

BGV 方案是 Brakerski、Gentry 和 Vaikuntanathan 在 2012 年 ITCS 会议上提出的全同态加密方案。它最大的突破是：不再需要 Gentry 2009 年原始方案里最昂贵的”自举”（bootstrapping）操作，改用一种叫”模数切换”（modulus switching）的轻量技巧来控制噪声增长，从而大幅降低计算开销。

为什么重要

不理解 BGV，下面这些事都没法解释：

为什么 gentry-fhe-2009 提出的第一代 FHE 方案虽然理论上突破了，但实际跑起来慢到不可用——因为每隔几步就要做一次自举，自举本身就是一次完整的同态解密，代价巨大
为什么 2012 年之后 FHE 从”纯理论玩具”开始变成”有可能工程化”——BGV 把核心瓶颈从自举换成了模数切换，速度提升了好几个数量级
为什么 Microsoft SEAL、HElib 这些开源 FHE 库都把 BGV（或它的近亲 BFV）作为默认方案——因为它是第一个”能跑”的全同态方案
为什么云计算隐私保护总是在提”同态加密”——BGV 证明了”把数据加密后交给不信任的服务器计算”在理论和工程上都走得通
为什么 dwork-dp-2006 的差分隐私和 FHE 经常一起出现——一个保护”统计查询的输出”，一个保护”计算过程中的输入”，是隐私保护的两条腿

前置知识

读这篇论文需要先理解三个概念：

对称加密与公钥加密：aes 是对称加密（一把钥匙加密解密），RSA 是公钥加密（公钥加密、私钥解密）。FHE 建立在公钥加密基础上，但额外要求”密文上能做运算”。
格密码（Lattice-based Cryptography）：BGV 的安全性建立在”格上的困难问题”上，具体是 LWE（Learning With Errors）问题。你可以理解为：往一组线性方程里加一点点噪声，找精确解就变得极其困难。这个困难性甚至被认为能抵抗量子计算机。
噪声与同态运算的矛盾：每做一次同态运算（特别是乘法），密文里的噪声就会增大。噪声一旦超过阈值，解密就得不到正确结果。整个 FHE 的核心挑战就是”怎么控制噪声不爆炸”。

核心要点

BGV 方案可以拆成四步来理解：

加密 = 明文 + 噪声：把明文 m 编码成一个”带噪声的格点”。噪声很小时，解密能准确还原 m；噪声太大时，解密失败。类比：你在白纸上写了一个数字，然后在上面撒一层薄薄的灰——灰少的时候还能看清数字，灰多了就看不清了。
同态加法 ≈ 噪声相加：两个密文相加，噪声也相加，增长是线性的——还好，不会立刻爆炸。
同态乘法 ≈ 噪声相乘：两个密文相乘，噪声会相乘——指数级增长，做几次乘法噪声就要超过阈值。这就是 Gentry 原始方案必须靠自举来”重置”噪声的原因。
模数切换（BGV 的核心创新）：不重置噪声，而是”缩小尺度”。把密文从一个大模数 q 切换到一个小模数 q’，噪声的绝对值按比例缩小。类比：你在一张很大的纸上写字，字的抖动（噪声）有 5 毫米。现在把整张纸等比缩小到一半——字也缩小了，但抖动同比缩到 2.5 毫米。每做完一次乘法，就缩小一次纸，噪声就被压下去了。

这四步加起来的效果是：每层乘法消耗一级模数，预设足够多的模数级别（叫做”模数链”），就能支持任意深度的电路运算——不需要自举。

实践案例

案例 1：加密整数上的四则运算

假设 Alice 有两个秘密数 a = 3, b = 5，她想让云服务器帮她算 a * b + a，但不想让服务器知道 a 和 b 的值。

用 BGV 方案的流程：

Alice 用公钥加密 a 和 b，得到密文 ct_a 和 ct_b
把 ct_a、ct_b 发给云服务器
云服务器在密文上计算 ct_result = ct_a * ct_b + ct_a（每次乘法后做一次模数切换）
云服务器把 ct_result 还给 Alice
Alice 用私钥解密，得到 18（= 3 * 5 + 3）

全程服务器只看到密文，不知道 3、5、18 中的任何一个。

案例 2：模数切换 vs 自举的代价对比

Gentry 2009 方案每次自举需要同态地执行一次完整的解密电路——解密电路本身深度就不小，导致自举变成了整个系统最慢的瓶颈。打个比方：为了降低手术中的出血量（噪声），每开一刀就要做一次完整的体检（自举）。

BGV 的模数切换只需要做一次”缩放 + 取整”——复杂度是 O(n) 的简单线性运算，比自举快几个数量级。相当于每开一刀只需要擦一下汗（模数切换），而不是做完整体检。

案例 3：FHE 在隐私机器学习中的角色

一家医院想用加密的患者数据做病情预测。训练阶段用 abadi-dpsgd-2016 的 DP-SGD 保护隐私；推理阶段用 BGV 方案——患者把自己的体检数据加密后发给服务器，服务器用训练好的模型在密文上做推理，返回加密的预测结果，患者自己解密查看。全程服务器既看不到患者数据，也看不到预测结果。这就是”隐私保护的端到端 ML 管线”。

数学直觉

BGV 的加密可以用一行公式概括（简化版）：

ct = (a, b) 其中 b = a·s + m + e (mod q)

s 是私钥（一个秘密向量）
a 是随机向量
m 是明文
e 是一个很小的噪声
q 是模数

解密：b - a·s = m + e (mod q)，因为 e 很小，可以准确恢复 m。

模数切换的核心操作：把 (a, b) 从 mod q 缩放到 mod q’（q’ < q），噪声 e 也按 q’/q 比例缩小。数学上是先乘 q’/q 再四舍五入到最近的整数。

还有一个关键操作叫密钥切换（key switching / relinearization）。同态乘法之后，密文的”维度”会膨胀——原来是关于秘密向量 s 的线性函数，乘完变成了关于 s 的二次函数。密钥切换把这个二次密文”压”回一次密文，方法是预先发布一组特殊的”切换密钥”。你可以类比为：两个一元一次方程相乘得到一个一元二次方程，密钥切换就是用预先准备好的辅助信息把它”降次”回一元一次。

踩过的坑

“同态加密能替代所有隐私保护”是错的：FHE 只保护”计算输入”不被执行者看到，但它不保护”计算结果”——结果谁拿到了谁就知道。如果你想保护结果也不泄露个体信息，还是需要 dwork-dp-2006 的差分隐私。两者解决的是不同层面的问题。
“模数切换完全消灭了自举”的理解不准确：BGV 证明了在电路深度已知时可以不用自举。但如果你需要支持任意深度（事先不知道要算多少层），还是得用自举来”刷新”模数链。后来 Gentry-Sahai-Waters 2013 (GSW) 方案进一步简化了自举过程。
噪声预算需要提前规划：模数链的长度必须在加密之前就确定好，它决定了你能做多少层乘法。链太短——算到一半噪声爆了；链太长——密文体积和密钥尺寸都会膨胀。工程上需要根据具体电路深度来”预算”噪声。
密文体积不是免费的：BGV 的密文通常比明文大几千倍甚至上万倍。传输和存储成本很高，网络带宽经常成为瓶颈。实际部署时必须同时优化计算和通信两个维度。

适用 vs 不适用场景

适用：

云上的隐私计算——医疗数据分析、金融风控模型训练，数据方不信任计算方时，FHE 让数据全程加密
安全多方计算（MPC）的构建块——很多 MPC 协议用 FHE 作为底层原语
隐私保护的机器学习推理——模型或数据加密后做推理，abadi-dpsgd-2016 保护训练阶段，FHE 保护推理阶段
区块链上的隐私交易——用 FHE 在链上做加密状态的计算

不适用：

需要极高吞吐的实时系统——FHE 目前仍比明文计算慢 3-6 个数量级，延迟敏感场景不可用
计算逻辑频繁变化——每次电路结构改变都需要重新设置参数和模数链
只需要保护传输过程——TLS/HTTPS 就够了，不需要 FHE 这么重的方案
数据量极大但计算简单——简单统计用差分隐私或安全聚合就能解决，FHE 大材小用

历史小故事（可跳过）

2009 年：Craig Gentry 在斯坦福的博士论文第一次构造出全同态加密方案，震动密码学界。但他的方案基于”理想格”，安全假设较强，且自举操作让实际运行极慢——加密一个比特需要几十分钟。
2011 年：Brakerski 和 Vaikuntanathan 提出 BV 方案，第一次把 FHE 建立在标准 LWE 假设上（不再需要理想格），安全基础更坚实。同年他们还提出了”张量积”技巧来处理密文乘法后的维度膨胀（relinearization）。
2012 年：Brakerski、Gentry、Vaikuntanathan 三人合作，在 BV 方案基础上加入模数切换技巧，形成 BGV 方案。核心洞见是”不要在每次噪声变大时去消灭噪声（自举），而是在噪声变大之前把尺度缩小（模数切换）“。这一步把 FHE 从理论突破推向工程可能。
2012 年同年：Fan 和 Vercauteren 提出 BFV 方案，与 BGV 思路相似但编码方式不同；两者成为此后十年 FHE 工程实现的两大主力。
2013 年：Gentry-Sahai-Waters 提出 GSW 方案，进一步简化了自举过程，为后来的 TFHE（2016）铺路——TFHE 能在 13 毫秒内自举一个门电路，让 FHE 终于”摸到”实时计算的门槛。

学到什么

噪声管理是 FHE 的核心战场——所有 FHE 方案的区别归根到底是”怎么处理噪声增长”：自举（暴力重置）、模数切换（缩小尺度）、还是近似计算（CKKS 方案容忍一点误差）
模数切换的思想可以类比到工程中很多场景——“不要等问题变大了再修，而是在问题还小的时候就缩小它的生长空间”，这种”预防优于治疗”的思路在噪声控制、内存管理、错误预算等领域都适用
安全假设决定了方案的长期生命力——BGV 基于标准 LWE 问题，这个假设即使量子计算机出现也被认为安全（后量子安全），这是它能成为 NIST 后量子密码标准候选基础的原因
理论突破到工程落地需要多步简化——Gentry 2009 证明了”能做”，BGV 2012 证明了”能快做”，TFHE 2016 证明了”能实时做”。每一步都是把上一步的瓶颈操作替换成更轻量的等价操作

关联

gentry-fhe-2009 —— 第一个 FHE 构造方案，BGV 是对它的关键优化（去掉自举）
dwork-dp-2006 —— 差分隐私保护统计输出，FHE 保护计算输入，两者互补
aes —— 对称加密；BGV 论文中把”同态执行 AES”作为效率 benchmark
abadi-dpsgd-2016 —— 差分隐私保护训练过程，FHE 保护推理过程，构成隐私 ML 的两个阶段

反向链接

cheon-ckks-2017 —— CKKS — 让加密数据也能做浮点运算
chillotti-tfhe-2016 —— TFHE 2016 — 把全同态加密的自举时间从分钟级压到 0.1 秒
fan-vercauteren-bfv-2012 —— Fan-Vercauteren BFV — 让加密数据上做整数运算变得实际可用
gentry-fhe-2009 —— Gentry 2009 — 第一个全同态加密方案
paillier-1999 —— Paillier 1999 — 能在密文上直接做加法的公钥加密
regev-lwe-2005 —— Regev LWE 2005 — 把带噪声方程变成后量子密码地基