Gentry 2009 — 第一个全同态加密方案

待复核

是什么

全同态加密（Fully Homomorphic Encryption, FHE）是一种让你在加密数据上直接做计算、算完解密就是正确结果的加密技术。

日常类比：你把一份试卷锁进透明但防拆的保险箱寄给阅卷老师，老师戴着特制手套伸进箱子批改打分，全程看不到试卷内容，但改完你开箱拿出来的分数和明文批改完全一致。类比边界：现实中没有这种箱子，FHE 靠数学保证安全性而非物理材料。

2009 年，Craig Gentry 在斯坦福的博士论文里给出了第一个真正能同时支持加法和乘法、次数不受限的全同态加密方案，解决了密码学界悬而未决 30 年的公开问题。

用数学符号说：对加密 Enc、解密 Dec、同态求值 Eval 与任意函数 f，FHE 保证 Dec(Eval(f, Enc(x))) = f(x)。不管 f 多复杂，结果都对。

为什么重要

不理解 FHE，下面这些问题就没法回答：

为什么云计算厂商总说”你的数据我看不到”却很难让人信服——FHE 是真正做到这一点的技术路线
为什么联邦学习（mcmahan-fedavg-2017）里有人提出用同态加密替代安全聚合——因为 FHE 能让服务器在密文上直接做梯度聚合
为什么差分隐私（dwork-dp-icalp-2006）和 FHE 经常一起出现——它们从不同角度保护隐私：DP 保护统计结果不泄露个体，FHE 保护计算过程不泄露原始数据
为什么医院之间想联合分析病历数据却迟迟落不了地——性能问题是 FHE 的最大瓶颈，Gentry 的方案虽然理论完美但实际跑起来极慢

核心要点

Gentry 的方案分四步理解：

“有点同态”的加密（Somewhat Homomorphic Encryption, SHE）：先造一个能做有限次加法和乘法的加密方案。类比：一把锁开始很灵活，但每拧一次就生锈一点。这里的”锈”就是噪声——每次运算，密文里的噪声都会增长，超过阈值就解密不出来了。
噪声是核心矛盾：加法让噪声线性增长（还好），乘法让噪声平方级增长（要命）。做几十次乘法后，噪声淹没信号，密文报废。为什么乘法更贵？因为两个密文相乘时，噪声项之间也会交叉相乘，产生高次项。
自举（Bootstrapping）——Gentry 的核心突破：把解密过程本身也当成一个电路，用 SHE 在密文上”同态地执行解密”。效果：噪声被重置回初始水平，就像给生锈的锁上了润滑油。只要 SHE 的能力足够跑一次自己的解密电路（叫”可自举”），就能无限次刷新噪声，从而支持任意深度的计算。
“压缩”解密电路：原始 SHE 的解密电路太深，SHE 自己跑不动。Gentry 用数学技巧（Squashing + 稀疏子集和假设）把解密电路压扁到 SHE 能处理的深度，打通最后一环。

四步连起来：SHE → 噪声爆炸 → 自举刷新噪声 → 压缩让自举可行 → FHE 成立。

一个简化的伪代码帮助理解自举的核心思路：

# 伪代码：自举的核心逻辑
c_noisy = HomomorphicEval(f, c_fresh)   # 密文带噪声，快要爆了
bk = Encrypt(secret_key)                # 自举密钥 = 加密后的私钥
c_refreshed = HomomorphicEval(Decrypt, c_noisy, bk)  # 同态解密
# c_refreshed 和 c_noisy 加密同一个明文，但噪声回到初始水平

实践案例

案例 1：加密数据库上的求和（教学伪代码）

医院把血糖值加密后存云端；研究方只拿回「加密的总和」，本地再解密。

# 教学伪代码（不是某个库的真实 API）
sk, pk = KeyGen()
c1 = Enc(pk, 5.2)          # 病人 A 血糖
c2 = Enc(pk, 7.1)          # 病人 B 血糖
c_sum = HomAdd(c1, c2)     # 云端只做密文加法
assert Dec(sk, c_sum) == 12.3

逐部分解释：

KeyGen 在医院本地完成，私钥 sk 从不上传
云端只执行 HomAdd，看不到 5.2 / 7.1
解密仍在医院侧；这就是「计算外包但不交明文」

案例 2：隐私保护的机器学习推理

用户想用云端诊断模型，但不想上传明文 X 光片。流水线：用户 Enc(x) → 云端 Eval(model, c_x) → 用户 Dec(c_y) 得到诊断。云端既看不到图片，也看不到结论。这和 abadi-dpsgd-2016 互补：DP-SGD 护训练数据，FHE 护推理输入。

案例 3：加密投票（密文加法）

# 每位选民提交 Enc(vote_i)；计票方只做密文累加
c_total = Enc(pk, 0)
for c_vote in ballots:
    c_total = HomAdd(c_total, c_vote)
tally = Dec(sk_committee, c_total)   # 委员会联合解密

逐部分解释：

单票始终是密文，计票服务器只接触 HomAdd
最终只公开总数；工业上常再配零知识证明防篡改
同类思路也出现在 Private Join and Compute 等 MPC 构建块里

踩过的坑

“同态”不等于”全同态”：RSA 加密天然满足 Enc(a) * Enc(b) = Enc(a * b)，这叫”乘法同态”。Paillier 加密满足加法同态。但它们都只支持一种运算。FHE 要求加法和乘法同时支持，且次数无限——这才是 30 年没人解决的难题。初学者最容易在这里混淆。
自举不是免费的：每次自举需要用一把特殊的”自举密钥”（加密了的私钥）在密文上模拟解密过程。这个操作本身极其昂贵——Gentry 原始方案一次自举需要约 30 分钟（2009 年硬件）。后续工作（BGV、BFV、CKKS 等）的核心优化方向就是让自举更快或尽量少用自举。到 2020 年代 TFHE 方案已经把单次自举压到毫秒级。
安全假设不同于 AES：Gentry 的方案基于”理想格上的困难问题”（Ideal Lattice），后来被简化为 LWE（Learning With Errors）问题。这和 aes 基于的代换-置换网络完全不同。格密码的好处是抗量子计算，坏处是参数选取还在研究中，安全性置信度不如 AES 经过 20 年考验。
密文膨胀严重：加密 1 bit 的明文，密文可能膨胀到几千倍甚至更多。传一条加密消息的带宽成本远超明文+TLS 的组合。这是 FHE 目前不适合实时通信的根本原因。以 Microsoft SEAL 为例，加密一个 32-bit 整数的密文大小约 32KB-256KB，膨胀比在 8000x-64000x。

方案演进速查

Gentry 2009 之后，FHE 方案沿三条路线快速发展：

BGV（2012）：Brakerski-Gentry-Vaikuntanathan 提出”模切换”（modulus switching）技术，每次乘法后降低模数来控制噪声，大幅减少自举次数。实际计算中可以完全避免自举，只要预先知道电路深度。
BFV（2012）：Fan-Vercauteren 简化了 BGV 的编码方式，更适合整数运算。Microsoft SEAL 的默认方案。
CKKS（2017）：Cheon-Kim-Kim-Song 方案支持近似计算——允许解密结果有微小误差，换来对浮点数和向量运算的原生支持。机器学习推理场景的首选。
TFHE（2016）：Chillotti 等人把自举时间压到毫秒级，适合布尔电路和低延迟场景。Zama 的 Concrete 框架基于此方案。

选方案的经验法则：整数精确计算选 BFV，浮点/向量选 CKKS，布尔电路/低延迟选 TFHE。

适用 vs 不适用场景

适用：

云端计算外包：数据所有者不信任云服务商，但需要云的算力
隐私保护的数据分析：医疗、金融等领域的跨机构联合统计
安全多方计算的构建块：配合秘密共享、混淆电路使用
对延迟不敏感的离线批处理任务

不适用：

实时系统（延迟要求毫秒级）——FHE 运算开销比明文大 10^4 到 10^6 倍
大规模数据传输场景——密文膨胀导致带宽成本过高
已有可信执行环境（TEE）且威胁模型允许的场景——TEE 性能远优于 FHE
只需要保护统计结果不泄露个体（而非保护整个计算过程）——用 dwork-dp-icalp-2006 更轻量

历史小故事（可跳过）

1978 年，RSA 三人组（Rivest、Adleman、Dertouzos）在一篇论文里首次提出”隐私同态”（privacy homomorphism）的概念：能不能在加密数据上直接算？之后 30 年，无数密码学家尝试构造这样的方案，全部失败——要么只支持加法，要么只支持乘法，要么支持两者但次数有限。

2009 年，IBM 研究员出身、在斯坦福读博的 Craig Gentry 用一个出人意料的想法破局：既然噪声会爆炸，那就用加密方案同态地给自己做手术（自举），把噪声清零。这个”加密方案能评估自己的解密电路”的递归想法，被认为是密码学史上最优美的构造之一。

论文发表后，Gentry 收到了 ACM 博士论文奖。这篇 200 多页的博士论文后来催生了一整个子领域：BGV（2012）把性能提升了几个数量级；CKKS（2017）让 FHE 能处理近似计算（浮点数）；TFHE（2016）把自举压到毫秒级，适合布尔电路。到 2020 年代，工业界出现了 Microsoft SEAL、Google FHE 编译器、Zama 的 Concrete 等实用框架，FHE 正在从理论走向工程。

学到什么

“在加密数据上计算”是密码学的终极目标之一——Gentry 证明了它理论上可行，打开了大门。在此之前，大多数人认为这不可能做到。
噪声管理是 FHE 的核心工程问题——所有后续方案（BGV、BFV、CKKS、TFHE）都在想办法让噪声长得慢、清得快。可以说，FHE 的发展史就是一部噪声控制史。
自举是把”有限”变”无限”的关键技巧——用系统评估自身来突破自身限制，这种递归思想在计算机科学里反复出现（编译器编译自己、AI 训练 AI）。
理论可行不等于实践可用——Gentry 2009 到真正能用的 FHE 库（2020s），中间隔了十几年工程优化。理论和工程之间的鸿沟，在密码学领域尤其明显。
隐私保护是一个技术栈——FHE 保护计算过程、差分隐私保护统计输出、联邦学习保护数据位置，三者在不同层面协同工作，不是互相替代的关系。

关联

dwork-dp-icalp-2006 —— 差分隐私从统计输出端保护个体，FHE 从计算过程端保护原始数据，两者互补
abadi-dpsgd-2016 —— DP-SGD 在训练阶段加噪声保护隐私，FHE 可在推理阶段保护用户数据，构成完整隐私链
mcmahan-fedavg-2017 —— 联邦学习的安全聚合协议可以用 FHE 实现，让服务器在密文上聚合梯度
aes —— AES 是对称加密的工业标准，FHE 是另一个维度的能力（计算性同态）；两者安全假设完全不同
brakerski-bgv-2012 —— BGV 是 Gentry 方案的直接后继，用模切换（modulus switching）替代自举，大幅提升性能
rsa —— RSA 是最早被发现具有乘法同态性质的加密方案，FHE 把这个性质推广到任意计算
zk-snark —— 零知识证明让你证明”我知道答案”而不泄露答案，FHE 让别人在你的加密数据上算出答案；两者都是”不看数据也能得到结论”的技术

反向链接

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