全同态加密：在密文上计算
Fully Homomorphic Encryption — Computing on Ciphertexts
2009 年，Craig Gentry 在斯坦福的博士论文里第一次给出了全同态加密（Fully Homomorphic Encryption, FHE）的可行构造：不解密，也能对密文做任意计算，解密后得到的结果等于对明文做同样计算。这件事被称作密码学的圣杯，不是修辞——在此之前，人们只知道如何在密文上做加法，或者只知道做乘法，不能两者都做、还保持可解密。
2020 年代真正改变的，不是“圣杯是否存在”，而是账单写在哪一行。自举（bootstrapping）从“理论上能刷新噪声”变成了可以在开源库里计时的原语；方案族也从“一种格上的电路”裂成 CKKS、TFHE、BGV 三条几乎不能互相替代的工程路线。开放问题随之从“能不能算”换成“一次自举要摊到多少个槽位上、两种方案之间切换是否本质上就是再自举一次”。
破除误解：同态不是“加密很强所以可以随便算”
同态加密常被说成“数据始终加密，所以计算一定安全”。这个句子漏掉了最贵的那一步。
半同态方案可以无限次做加法，或者有限次做乘法；全同态要求任意电路。Gentry 的关键观察是：密文带着噪声，每次乘法都让噪声长大；噪声一旦淹没明文，解密失败。自举的意思是——把“解密电路本身”同态地跑在密文上，用一把加密的密钥把噪声刷新回去。它不是加速技巧，而是让计算深度从“模数链还剩几层”变成“理论上任意深”的那道闸门。
另一句常见口号是“FHE 已经实用了”。2023–2025 年的库与硬件加速确实把部分推理从小时压到秒级，但相对明文仍慢几个数量级。实用发生在摊销成立的场景：同一套公钥、大批量槽位、电路深度事先知道。它不是端侧手机上的通用计算，也不是把任意 Python 函数丢进密文里就能跑。
现场：噪声预算，而不是电路清单
把 FHE 理解成“加密版 CPU”会写错问题。它更像一条有漏的水管：每个门都漏一点噪声，水管的直径是模数。水位到顶之前你还能算；到顶了就必须自举，或者在 leveled 方案里预先排好模数链、算完就停。
Gentry 2009 的构造建立在理想格上，随后十年的工作把它拆成更干净的假设与更短的密文。BGV（Brakerski–Gentry–Vaikuntanathan，2012）与几乎同时的 BFV 走精确整数 / 有限域的 SIMD 路线：一次密文里塞进许多槽位，槽位上做模运算。CKKS（Cheon–Kim–Kim–Song，2017）放弃精确，改做近似实数 / 复数，把舍入当成方案的一部分，因此更接近神经网络里的浮点。TFHE 与 CGGI 一类方案则走布尔 / 小整数，用可编程自举（programmable bootstrapping）把查找表写进刷新过程——比较、符号函数、不光滑激活，不必先展开成深电路。
2020 年代的研究现场，几乎都围绕这张对照表，而不是再发明一种“从零开始的全同态”。
| 方案族 | 明文语义 | 自举画像 | 典型工作负载 |
|---|---|---|---|
| CKKS | 近似实数向量 | 延迟高、槽位多，摊销吞吐最好 | 加密推理、统计 |
| BGV / BFV | 精确模算术 SIMD | 吞吐介于中间，可编程自举弱 | 精确计数、私有查询 |
| TFHE / CGGI | 比特或小整数 | 单次延迟最低，可编程查找表 | 比较、决策树、不连续函数 |
Al Badawi 与 Polyakov（IACR ePrint 2023/149）把这件事写进了可复现的计时：在 OpenFHE 一类库里，CKKS 自举适合“一次刷新成千上万个槽位”，DM/CGGI 适合“一次刷新一个小整数但要立刻做任意函数”。没有哪一行是绝对更快，只有哪一行的摊销单位对上了你的电路。
谁在做，做到了哪一步
开源工具链在 2020 年代第一次让非密码学家能跑通基准，而不是只读论文里的渐近记号。Microsoft SEAL 把 BFV/CKKS 做成可嵌入的库；HElib 长期承担 BGV 的实验床；OpenFHE 试图把多方案放进同一套 API，并在 1.1 版附近加入 CKKS 与 CGGI 之间的方案切换。Zama 把 TFHE 做成 Concrete / TFHE-rs 与面向智能合约的实验栈。这些名字不应当被读成产品排行榜——它们是公开的计时与接口，让“自举要几毫秒”第一次能被第三方复核。
硬件加速是另一条线：用 GPU 或专用电路去扛数论变换与自举里的自举密钥。论文数字变动很快，可靠的结论只有定性的一条——加速改变的是常数，不自动取消噪声增长，也不自动让方案切换变便宜。
与机密计算对照着看更清楚。可信执行环境把明文关进芯片里的隔离域，信任基是硅与远程证明；FHE 把计算留在不可信的主机上，信任基是格问题与实现。两者都在 2020 年代被说成“数据可用不可见”，但失败模式完全不同：一边怕侧信道与微架构，一边怕噪声参数选错、实现与方案证明之间的缝。
2024–2025 年的公开计时，第一次让“自举要多久”可以按方案族分开读，而不是混成一句“FHE 变快了”。OpenFHE 把 BGV、BFV、CKKS 与 FHEW/TFHE 放进同一套实现，并提供 CKKS 与 FHEW 之间的方案切换示例。它对研究的意义不是排行榜，而是让 2023/149 那种跨方案对照可以在公开代码上复现。
硬件数字必须标成声明级别。Zama 在技术博客中称：4 比特消息、约 128 比特安全下，单卡 GPU 上的 TFHE 自举已进入亚毫秒（约 800 微秒量级）。这是公司自己的计时，槽位、失败概率与安全定义都写在他们的设定里，不能直接拿去和 CKKS 上数万槽的一次刷新对照。能确定的只有：布尔与小整数路线的延迟，已经被 GPU 从几十毫秒推进到了亚毫秒声明；高维近似线性代数仍走 CKKS 的摊销账。
面向区块链的 fhEVM 是另一类声明。早期实现要求验证者跑改过的 EVM，公司称吞吐大约每秒两笔；后来的协处理器把一层上的同态运算改成指针，把真正的格运算放到链下，并宣称接近每秒二十笔加密交易。一层不跑格运算，解密密钥由门限多方持有——这把“密文上的智能合约”从密码学方案变成了分布式系统。独立复核仍然稀缺。开放问题是：声明吞吐对应谁的硬件、何种电路深度、失败如何回滚。
代价与争议：摊销、方案切换、近似算术
摊销是 2020 年代最诚实的性能语言。 报一个“自举 0.X 秒”而不说槽位数、精度与失败概率，等于没报。CKKS 把成千上万个明文打包进一条密文，于是一次昂贵的刷新可以分摊到整条向量上；TFHE 的单次自举可以很快，但若你的应用是高维线性代数，槽位摊销的账会反过来。开放问题不是“再快一个数量级”，而是：哪些电路结构允许把自举次数降到与深度无关、只与数据并行度有关。 打包、旋转、共轭——这些看起来像实现细节的算子，决定了摊销能不能成立。
方案切换可能与自举一样硬。 Halevi 与 Shoup 在 2010 年代中期就把“SIMD 方案之间更便宜的转换”列为开放问题。Eldefrawy、Genise 与 Manohar（PQCrypto 2023；IACR ePrint 2023/988）给出了相当强的证据：若能在 BGV/BFV 与 CKKS 之间高效同态切换，就可以用一次切换完成这些方案的自举，从而绕开目前最贵的线性变换。于是“先切到更合适的方案再算”这条工程直觉，并不能免费获得。CKKS 与 TFHE 之间的切换在 OpenFHE 里被做成了可用特性，因为它连接的是两类不同的明文——多项式友好的近似向量，与查找表友好的小整数——但这条通路的代价同样必须写进电路预算，而不是当编译器魔法。
CKKS 的“对”是近似的。 把神经网络丢进 CKKS，误差来自方案舍入、自举、以及模型本身的量化，三者缠在一起。解密得到“看起来合理的分类结果”，并不自动给出与明文推理的逐比特一致。精确方案（BGV/BFV）不会送你这个人情，比较和 ReLU 却会变得极贵。于是 2020 年代的争议很具体：为了机器学习去用近似方案，正确性陈述必须改写成概率误差界；若监管或审计要求逐比特可复核，你可能根本不该用 CKKS。
实现安全是另一层。同态只保证在方案假设下密文不泄露明文，不保证时序、内存访问与自举密钥的处理。把 FHE 说成已经替代访问控制，是把密码学原语误当成系统。
未知的边界
- 自举的摊销能否在端侧成立，还是永远只属于批量外包？手机上的噪声预算、密钥尺寸与能耗，目前没有接近明文的证据。
- SIMD 方案之间是否存在“不是自举”的切换，还是 2023 年的相对硬度结果已经标出了渐近边界？
- 可编程自举把任意函数写进查找表，精度一升，表就爆。高精密连续函数是否必须回到 CKKS，这条分工会不会被新的自举改写？
- 格上的参数选择、失败概率与后量子安全的具体级别，如何对工程师可审计，而不是只存在于各库的默认表？
- FHE 与零知识证明、机密计算的组合——密文上算、再证明算对了、或在 TEE 里跑自举——哪一种混合在带宽与延迟上先站住，仍是开放的系统设计问题。
跨域连接
- 线性代数：明文被编码成环上的向量，槽位上的加法与乘法对应格上的线性与双线性作用。旋转与共轭不是语法糖，而是为了在打包向量里搬动坐标。噪声预算因此是一个线性代数对象：每次乘法都在放大一个误差向量的范数，能算多深取决于范数何时撞上模数。
- 概率论：解密失败被写成失败概率，而不是一次偶然的坏随机数。自举把噪声分布重新拉回可解密区域，但新的分布仍是随机的。所以“正确”在 FHE 里常常是高概率陈述——参数表上的位数，其实是在买更小的失败概率，而不是买绝对算术。
- 证明：方案论文证明的是理想算法在格假设下的语义安全；库里跑的是带启发式参数、近似算术与工程裁剪的电路。证明覆盖不到的那一段——编码、自举密钥、浮点舍入——才是 2020 年代事故真正出现的地方。同态正确性不能从论文标题自动继承到实现。
- 信息不对称：外包计算的经典结构是：拥有数据的一方不愿交出明文，拥有算力的一方不愿被当成完全可信。FHE 把这层不对称写成密码学接口，而不是合同条款。它改变的是“看不见也能算”，不是“算完就自动可审计”——后者仍要零知识证明或可验证外包，另付一套代价。
- 信息哲学：密文上的计算强迫我们把“知道”与“能对数据施加函数”拆开。服务器可以变换数据，却在方案的意义上不知道明文。这种拆分是操作上的，不是心理学上的：它不回答机器是否理解数据，只规定谁持有解密密钥。把 FHE 说成机器在密文里“思考”，是把接口误读成认知。
参考文献
- Gentry, C. A Fully Homomorphic Encryption Scheme. 博士论文，Stanford University, 2009.
- Brakerski, Z., Gentry, C. & Vaikuntanathan, V. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ITCS 2012. DOI: 10.1145/2090236.2090262.
- Cheon, J. H., Kim, A., Kim, M. & Song, Y. Homomorphic Encryption for Arithmetic of Approximate Numbers. ASIACRYPT 2017. DOI: 10.1007/978-3-319-70694-8_15.
- Chillotti, I., Gama, N., Georgieva, M. & Izabachène, M. TFHE: Fast Fully Homomorphic Encryption over the Torus. J. Cryptol. 33, 2020. DOI: 10.1007/s00145-019-09319-x.
- Al Badawi, A. & Polyakov, Y. Demystifying Bootstrapping in Fully Homomorphic Encryption. IACR ePrint 2023/149.
- Eldefrawy, K., Genise, N. & Manohar, N. On the Hardness of Scheme-Switching Between SIMD FHE Schemes. PQCrypto 2023. DOI: 10.1007/978-3-031-40003-2_8.
延伸阅读
- Halevi, S. Homomorphic Encryption. 收入 Tutorials on the Foundations of Cryptography, 2017.（方案族与电路模型的教程视角）
- Gentry, C. Computing Arbitrary Functions of Encrypted Data. CACM 53(3), 2010.（面向非密码学家的早期综述）
- Zama. Bootstrapping TFHE ciphertexts in less than one millisecond. 公司技术博客（GPU 自举计时，属厂商声明）。
- Zama. Introducing the fhEVM Coprocessor. 公司技术博客（链上吞吐为厂商声明，不是独立测量）。