TFHE 2016 — 把全同态加密的自举时间从分钟级压到 0.1 秒

待复核

是什么

TFHE 是一套让你在完全不解密的情况下，对加密数据做任意逻辑运算的方案。日常类比：想象一个密封的手套箱——你把零件锁进箱子，通过手套在箱子里组装，全程看不到零件原样，但最终取出的成品和你亲手明文组装的一模一样。

“全同态加密”（FHE）就是这个手套箱的数学版本。问题在于，每次操作都会给密文加一点噪声，操作多了噪声淹没信号，结果就废了。2009 年 Gentry 发明了”自举”（bootstrapping）——在噪声快爆之前，同态地跑一遍解密电路把噪声洗掉。但早期自举一次要几分钟，根本没法用。

Chillotti 等人 2016 年这篇论文把自举压到 0.1 秒以内，让 FHE 第一次有了实用的可能。核心手段是用更轻量的”外积”替换原来的”内积”，并把密文搬到环面（Torus）上简化噪声管理。这篇论文获得了 Asiacrypt 2016 最佳论文奖，之后催生了 TFHE 开源库、Zama 的 TFHE-rs 和 Concrete 等工业级实现。

为什么重要

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

为什么云计算能在”不看你数据”的前提下帮你跑机器学习——TFHE 是 Zama Concrete 和 TFHE-rs 这些加密 ML 库的理论基础
为什么 FHE 从 2009 年发明到 2016 年才开始被工程界认真对待——之前自举太慢，TFHE 把它降了三个数量级
为什么第三代 FHE 方案（GSW / FHEW / TFHE）能抛弃第二代的 SIMD 批处理模式，转向逐门自举——因为单次自举终于够快了
为什么现代隐私计算方案经常把”环面”（Torus）挂在嘴边——TFHE 把 LWE 密文搬到环面上，简化了噪声管理

核心要点

外积替内积：之前 GSW 方案用”内积”（两个 GSW 密文相乘），计算量大。TFHE 发现可以用更轻的”外积”——一个 GSW 密文乘一个 LWE 密文，结果仍是 LWE 密文。类比：原来要两个大箱子对撞，现在只需要一个大箱子推一个小球，效果一样但省力得多。
门自举（Gate Bootstrapping）：每执行一个逻辑门（AND / OR / NAND），立刻做一次自举把噪声洗掉。类比：每炒完一道菜就洗一次锅——虽然洗锅花时间，但因为单次洗锅够快（0.1 秒），总体反而比”攒一堆脏锅最后一起洗”更可控。这让电路深度不再是瓶颈。
环面上的噪声管理：把密文定义在实数模 1 的环面 T = R/Z 上。噪声就是环面上的一个小偏移。自举的本质是把这个偏移”弹”回原点附近。环面的周期性让取模运算天然免费，减少了大量中间计算。这是论文名字里”Torus”的由来。类比：环面就像一个钟面——12 点再走一步回到 1 点，不需要额外的”归零”操作，周期性是内置的。

实践案例

案例 1：用 TFHE 跑一个加密的 NAND 门

# 伪代码：TFHE 门自举流程
ct_a = encrypt(bit_a, secret_key)   # 加密比特 a
ct_b = encrypt(bit_b, secret_key)   # 加密比特 b

# 同态 NAND：先做线性组合，再自举
ct_sum = ct_a + ct_b                # LWE 加法，噪声叠加
ct_result = bootstrap(ct_sum, bk)   # 自举：噪声重置，同时算出 NAND
# ct_result 解密后 == NAND(bit_a, bit_b)

逐部分解释：

encrypt 把一个明文比特编码为 LWE 密文——一组整数向量加一个小噪声项
ct_a + ct_b 是 LWE 加法，噪声也叠加，所以 ct_sum 的噪声比原来大
bootstrap 是核心：它同态地执行一个”测试多项式”的求值，把噪声洗掉的同时顺便算出 NAND 结果——一石二鸟
输出的 ct_result 噪声回到初始水平，可以继续参与下一个门运算，不会越攒越大

案例 2：自举的”盲旋转”核心步骤

输入: LWE 密文 c = (a_1, ..., a_n, b)，自举密钥 BK
1. 初始化：把测试向量 v 编码为多项式 ACC = v * X^b
2. 盲旋转：对 i = 1..n：
     ACC = ACC * BK[i]    （外积：RGSW × RLWE → RLWE）
     效果：把 ACC 旋转 a_i 步，但服务器不知道旋转了多少
3. 提取：从 ACC 取出常数项 → 得到噪声被重置的新 LWE 密文
4. 密钥切换：把 RLWE 密钥下的密文转回 LWE 密钥

关键：第 2 步就是”盲旋转”（blind rotation）。每一步外积只涉及一个 RGSW × RLWE 乘法，比完整的 GSW 内积快得多。n 次外积串起来，论文实测盲旋转约 13ms，加上密钥切换总共不到 0.1 秒。

案例 3：TFHE 在加密机器学习中的应用

场景：医院想用云端模型诊断，但不能泄露患者数据

1. 医院用 TFHE 加密患者特征向量，连同自举密钥一起上传
2. 云端在密文上逐门执行决策树 / 小型神经网络推理
3. 每个逻辑门后自动自举，噪声不会累积
4. 云端返回加密的诊断结果
5. 医院用私钥解密，得到明文诊断——云端全程没碰过明文

Zama 的 Concrete ML 库就是这个思路的工程实现。它用 TFHE 的”可编程自举”（programmable bootstrapping）在自举的同时顺便算一个查找表，从而把非线性激活函数（ReLU、sigmoid）也同态化了。这意味着不只是线性运算，连神经网络里的非线性层也能在密文上跑。

踩过的坑

自举密钥太大：TFHE 的自举密钥（bootstrapping key）约 24MB，传输和存储都是负担——这是用空间换时间的代价，对带宽受限的场景是硬伤。
只擅长比特级运算：TFHE 逐门自举适合布尔电路，但做大整数乘法或浮点运算效率远不如第二代 FHE（如 BGV / CKKS）的 SIMD 批处理模式。
参数选择极敏感：LWE 维度 n、多项式度 N、噪声标准差 sigma 要精确匹配——选错一个要么安全性崩盘，要么噪声洗不干净导致解密失败。
和 FHEW 容易混淆：TFHE 是 FHEW（Ducas-Micciancio 2015）的改进版，两者共享门自举思路，但 TFHE 用外积替代内积、引入环面抽象，性能高约 10 倍。名字和概念高度相似，初学者很容易搞混。

适用 vs 不适用场景

适用：

隐私保护的布尔电路计算——加密查询、加密决策树、加密比较
需要任意深度电路但单次运算简单的场景——逐门自举让深度无上限
对延迟容忍度在亚秒级的加密推理——0.1 秒/门对小模型可接受
需要精确结果（非近似）的场景——TFHE 是精确计算，不像 CKKS 有近似误差

不适用：

大规模矩阵 / 向量运算——CKKS 的 SIMD 批处理一次能打包上千个数，吞吐高得多
需要极低延迟（微秒级）的场景——0.1 秒仍然比明文慢 6 个数量级
密钥管理困难的端侧设备——自举密钥 24MB 对 IoT 不友好
已有可信执行环境（TEE / SGX）的场景——硬件隔离更简单直接

历史小故事（可跳过）

2009 年：Craig Gentry 发表博士论文，首次证明 FHE 可行，但自举一次要 30 分钟，纯理论价值。
2012 年：Brakerski-Gentry-Vaikuntanathan（BGV）和 Fan-Vercauteren（BFV）提出第二代 FHE，用模切换替代部分自举，性能提升但仍然慢。
2013 年：Gentry-Sahai-Waters（GSW）提出第三代方案，自举简化但仍需数秒。
2015 年：Ducas-Micciancio 发表 FHEW，首次实现门自举，降到约 0.69 秒/门。
2016 年：Chillotti 等发表本文，外积 + 环面优化把自举压到 0.1 秒以下，获 Asiacrypt 最佳论文。此后 TFHE 成为第三代 FHE 的代名词。
2018-至今：Zama 成立，推出 TFHE-rs（Rust）和 Concrete（Python），把 TFHE 从学术方案变成工程产品。可编程自举让 TFHE 能直接跑 ML 推理。

学到什么

“洗噪声”是 FHE 的核心瓶颈——谁能把自举做快，谁就让 FHE 离实用近一步。从 30 分钟到 0.1 秒，用了七年三代方案的迭代
外积替内积是一个通用的优化思路：当两个操作数的”重量”不对称时，用轻的那个当被操作数，复杂度可以降一个量级。这个思路在其他密码学和线性代数问题中也常见
逐门自举 vs 批量自举是空间-时间的取舍：TFHE 选了”每步都洗、每步都轻”，牺牲吞吐换可控延迟和无限深度。而 BGV/CKKS 选了”攒一批再洗”，用吞吐换单次延迟
数学抽象（环面）能简化工程——把密文放到 T = R/Z 上让取模运算免费，是这篇论文最优雅的洞见。好的数学抽象不只是理论好看，它能直接减少代码行数和运行时间

关联

gentry-fhe-2009 —— TFHE 的自举思想直接来自 Gentry 的原始 FHE 构造
brakerski-bgv-2012 —— 第二代 FHE 方案，TFHE 的前辈；适合 SIMD 批处理场景
fan-vercauteren-bfv-2012 —— 另一个第二代方案，与 TFHE 互补（批量精确算术 vs 逐门布尔）
cheon-ckks-2017 —— 支持近似算术的 FHE，适合 ML 中的浮点场景，常与 TFHE 搭配使用
aes —— 对称加密基础，FHE 的一个经典 benchmark 是同态计算 AES 电路
diffie-hellman-1976 —— 公钥密码学起点，LWE 困难问题是其精神后继
sgx-2013 —— 硬件级隐私计算的替代路线，与 FHE 的纯软件路线形成对比
rsa —— 经典公钥加密，FHE 可看作”让 RSA 的密文也能做加法和乘法”的终极推广

反向链接

regev-lwe-2005 —— Regev LWE 2005 — 把带噪声方程变成后量子密码地基