FHE方案对比 — BFV/BGV/CKKS/TFHE
BFV/BGV/CKKS/TFHE四大主流FHE方案的数学结构、噪声管理、适用场景
日期: 2027-01-01 方向: 隐私技术 / FHE/MPC/TEE 阶段: Phase 4 - FHE & MPC & TEE (Day 244-258) 标签: #FHE #BFV #BGV #CKKS #TFHE #scheme_compare
今日目标
| 类型 | 内容 |
|---|---|
| 学习 | BFV/BGV/CKKS/TFHE四大主流FHE方案的数学结构、噪声管理、适用场景 |
| 实操 | 用OpenFHE/SEAL运行四方案benchmark，构建选型决策树 |
| 产出 | fhe_compare.md(本笔记) + scheme_decision_tree.md |
1. 总览：四大FHE家族
| 方案 | 年份 | 明文空间 | 密文环 | SIMD | bootstrapping | 主要库 |
|---|---|---|---|---|---|---|
| BFV | 2012 | $\mathbb{Z}_t^N$（小整数） | $R_q = \mathbb{Z}_q[X]/(X^N+1)$ | ✅ N slots | 10-60s（少用） | SEAL, OpenFHE |
| BGV | 2011 | $\mathbb{Z}_t^N$ | $R_q$ | ✅ N slots | 10-60s | OpenFHE, HElib |
| CKKS | 2016 | $\mathbb{C}^{N/2}$（近似实数） | $R_q$ | ✅ N/2 slots | 5-30s | OpenFHE, SEAL, Lattigo |
| TFHE | 2016 | {0,1}（gate-level） | LWE+RLWE+RGSW混合 | 单bit | ~10ms（每gate） | tfhe-rs, TFHE-lib |
核心区分：BFV/BGV/CKKS是"算术FHE"（适合ML、统计），TFHE是"布尔FHE"（适合任意函数评估，gate-level boot快）。
2. BFV (Brakerski-Fan-Vercauteren, 2012)
2.1 加密结构
明文 $m \in R_t = \mathbb{Z}_t[X]/(X^N+1)$，密文是元组 $(c_0, c_1) \in R_q^2$。
Enc： $$c_0 = -a \cdot s + \Delta \cdot m + e, \quad c_1 = a$$
其中 $\Delta = \lfloor q/t \rfloor$（缩放因子），$a \xleftarrow{$} R_q$，$e \leftarrow \chi$。
Dec： $$m = \left\lfloor \frac{t}{q}(c_0 + c_1 \cdot s) \right\rceil \mod t$$
2.2 加法（容易）
$(c_0 + c_0', c_1 + c_1')$ 直接加 — 噪声线性叠加。
2.3 乘法（复杂）
输入两密文 $(c_0, c_1), (c_0', c_1')$，输出3-元组： $$d_0 = c_0 c_0', \quad d_1 = c_0 c_1' + c_1 c_0', \quad d_2 = c_1 c_1'$$
需要 relinearization（relin key）将3-元组压回2-元组。
噪声放大：乘法后噪声 $\approx |e_1| \cdot |m_2| + |e_2| \cdot |m_1| + |e_1 e_2|$ — 平方级增长。
2.4 适用场景
- 整数算术（投票计数、排名、SQL count）
- 布尔电路（用 $t=2$）
- 不适合实数/浮点
3. BGV (Brakerski-Gentry-Vaikuntanathan, 2011)
3.1 与BFV的核心差异
| 维度 | BFV | BGV |
|---|---|---|
| 缩放 | $\Delta = q/t$ 在密文 | 明文直接占低位（$m \mod t$ at LSB） |
| Modulus switching | 隐式（每次乘法后rescale） | 显式（用户控制） |
| 噪声管理 | 自动 | 手动（更精细） |
3.2 BGV的优势
- 模数可以是层叠链 $q_L > q_{L-1} > ... > q_0$，每次乘法降一级
- 在某些应用（特别是同时需要大depth和高precision）更灵活
- HElib主要用BGV
3.3 何时选BGV vs BFV
- 整数算术应用：两者性能接近，看库的成熟度（SEAL更易用 → BFV；HElib历史悠久 → BGV）
- 教学：BGV结构更直观
4. CKKS (Cheon-Kim-Kim-Song, 2016) — 近似算术FHE
4.1 核心创新
把噪声当成"近似误差" — 不再追求精确解密，而是允许：
$$\text{Dec}(\text{Enc}(m)) = m + \epsilon$$
其中 $\epsilon$ 像浮点的舍入误差。
4.2 编码 / Encoding
明文是复向量 $\mathbf{z} \in \mathbb{C}^{N/2}$（SIMD slots）。
通过 canonical embedding $\sigma: R \to \mathbb{C}^N$（把多项式在$X^N+1$的根处求值），加上scale $\Delta$（如 $2^{40}$），编码到 $R$。
4.3 重缩放 (Rescaling)
每次乘法后scale变成 $\Delta^2$ → 用 modulus switching 把 $q \to q/\Delta$，scale回到 $\Delta$，消耗一级模数链。
4.4 关键参数
- $N$：环维度（如 $2^{15}$ = 32768，提供 16384 slots）
- $\log Q$：模数链总长（如800-1200 bits）
- $\Delta$：scale（如 $2^{40}$）→ 每个数有40bit精度
- depth = $\log_2(\Delta) / \log_2(\text{ratio per level})$
4.5 CKKS杀手应用：隐私机器学习
Microsoft + Intel 2020：用CKKS做logistic regression推理，~秒级延迟。
Zama Concrete-ML：把sklearn模型自动转CKKS电路。
4.6 重要警告
- CKKS不是真正"明文-IND-CPA" — Li-Micciancio 2020 攻击：知道Dec结果可以推出$\sk$。要求不公开解密结果，或加额外噪声（noise flooding）。
5. TFHE (Chillotti et al., 2016) — Gate-Level FHE
5.1 与算术FHE的根本差异
| BFV/BGV/CKKS | TFHE | |
|---|---|---|
| 计算单位 | 算术运算（+, ×） | 布尔门 (AND/OR/XOR/NAND) |
| boot频率 | 偶尔（深度耗尽） | 每个gate |
| boot时间 | 5-60s | ~10ms |
| SIMD | ✅ N/2 - N slots | ❌ 单bit |
| 任意函数 | 难（要写多项式） | 天然（可表为电路） |
5.2 核心：programmable bootstrapping (PBS)
PBS 是 TFHE的灵魂：
- 同时做 noise refresh + 函数评估
- 输入密文 $\text{Enc}(\mu)$ + lookup table $T$（明文）
- 输出 $\text{Enc}(T[\mu])$
→ 任意单输入函数都能在一次boot中实现！
5.3 应用：Zama tfhe-rs
- fhEVM：把Solidity编译成FHE gate电路，每gate一次PBS
- 加密u8/u16/u32运算
- ~毫秒到秒级单位运算
5.4 性能权衡
- 每gate ~10ms → 评估SHA256 (~25k gates) ≈ 250s
- 但深度无限（每gate都boot），不需要预算管理
- 适合：复杂控制流、比较/排序、非线性
6. 噪声预算对比（同等安全水平 λ=128）
设 $N=2^{15}, \log q \approx 880$（128-bit security）：
| 方案 | 初始噪声 | 加法 | 乘法 | bootstrapping间隔 |
|---|---|---|---|---|
| BFV | $\sim \sigma$ | 线性 | $\sim B^2$（B为previous） | ~30 levels |
| BGV | $\sim \sigma$ | 线性 | $\sim B^2$ + auxiliary | ~30 levels |
| CKKS | $\sim \sigma + \Delta$ scale | 线性 | $\sim \Delta$ | ~25 levels |
| TFHE | $\sim \sigma$ | (gate组合) | (gate组合) | 每gate |
7. 选型决策树
你的应用是什么？
├─ 任意复杂逻辑（含 if/sort/lookup） ────► TFHE
│ 例: fhEVM, 隐私数据库查询
│
├─ 矩阵运算 / ML推理（线性代数为主）
│ │
│ ├─ 需要浮点 / 近似OK ────► CKKS
│ │ 例: 隐私神经网络、统计聚合
│ │
│ └─ 必须精确整数 ────► BFV / BGV
│ 例: 隐私投票、隐私拍卖
│
├─ 浅深度（depth ≤ 10），SIMD ────► CKKS / BFV (Leveled, no boot)
│
└─ 单bit逻辑、低延迟 ────► TFHE
8. 真实benchmark对比
8.1 单一运算（OpenFHE 1.2 + tfhe-rs 0.7, AWS c5.4xlarge）
| 操作 | BFV (N=2^14) | CKKS (N=2^14) | TFHE (FFT) |
|---|---|---|---|
| KeyGen | ~200 ms | ~250 ms | ~5 s（含boot key） |
| Enc | ~3 ms | ~5 ms | ~0.1 ms (LWE) |
| Dec | ~1 ms | ~2 ms | ~0.05 ms |
| Add | ~50 μs | ~80 μs | ~10 μs |
| Mul (无relin) | ~10 ms | ~15 ms | N/A |
| Relin | ~30 ms | ~50 ms | N/A |
| Boot | ~50 s | ~25 s | ~12 ms |
| Ciphertext size | ~700 KB | ~700 KB | ~2 KB (LWE) |
8.2 应用benchmark：隐私logistic回归推理（10维特征）
| 方案 | 延迟 | 精度损失 | 备注 |
|---|---|---|---|
| 明文 baseline | 0.001 ms | 0% | — |
| CKKS (depth 4) | ~3 s | <0.1% | 推荐 |
| BFV (定点, depth 4) | ~5 s | <0.5%（量化） | 整数friendly |
| TFHE (per-gate) | ~120 s | 0%（精确） | 只适合small models |
9. 真实项目应用
| 项目 | 方案 | 用例 |
|---|---|---|
| Zama fhEVM | TFHE (tfhe-rs) | 链上加密EVM，加密u8/u16/u32 |
| Inco Network | TFHE | 模块化机密EVM L1 |
| Microsoft SEAL | BFV/CKKS | 健康/金融统计 |
| Apple PSI | BFV变体 | iCloud钥匙串密码隐私集合交集 |
| Google Private Join | Paillier→BFV | 联合广告效果分析 |
| Concrete-ML (Zama) | TFHE | sklearn模型→FHE推理 |
| Helib (IBM) | BGV/CKKS | 学术/政企POC |
| Lattigo (EPFL) | BFV/BGV/CKKS | Go实现，教学+研究 |
10. 常见陷阱
- CKKS精度不足：scale太小→消失精度；scale太大→更快耗尽模数链。典型：$\Delta = 2^{40}$，留足safety margin
- BFV乘法不relinearize：3-元组累积 → 4-元组、5-元组 → 不可解密。必须每次乘法后relin
- CKKS Li-Micciancio攻击：把Dec结果公开（如做MPC输出）会泄漏sk → 必须flooding noise或trusted decryption
- TFHE参数错配：LWE/RLWE参数不一致 → key switching失败
- Memory blowup：1bit明文加密成2-4KB，1MB数据 → 2GB密文。生产环境内存优先
11. 合规与监管
- CKKS的"近似性"对法律意义模糊 — 是否算"加密"？目前GDPR/HIPAA都接受
- 欧盟AI Act 2024 — Article 10要求训练数据"具有充分代表性"，FHE+MPC可在不暴露原数据下做训练
- 中国《数据安全法》第27条 — "数据分类分级保护制度"，FHE作为强保护措施符合"重要数据"处理要求
- 金融行业 — Visa 2023年开始研究CKKS做反洗钱跨机构数据分析
12. 关键速查表
| 维度 | BFV | BGV | CKKS | TFHE |
|---|---|---|---|---|
| 明文 | 整数 | 整数 | 近似实数 | bit |
| SIMD | ✅ | ✅ | ✅ | ❌ |
| boot | 慢，少用 | 慢，少用 | 中 | 快，每gate |
| 适用 | 投票/拍卖 | 投票/拍卖 | ML/统计 | 任意控制流 |
| 主库 | SEAL | HElib/OpenFHE | SEAL/Lattigo | tfhe-rs |
| 链上代表 | — | — | — | fhEVM/Inco |
13. 面试题
Q1：CKKS vs BFV如何选？
看是否需要精确整数还是近似实数。CKKS适合机器学习（浮点权重、激活函数近似OK）；BFV适合精确投票/拍卖/排名。CKKS有Li-Micciancio攻击风险，要求flooding noise，BFV不需要。
Q2：为什么TFHE能"每gate都boot"？
TFHE的programmable bootstrapping (PBS)把noise refresh和任意单输入函数评估合二为一，单次PBS ~10ms。这让TFHE天然支持复杂控制流，不需要electric depth budget管理。代价：SIMD能力差，不适合大规模矩阵运算。
Q3：FHE在Web3中的应用方向？
(1) fhEVM (Zama/Inco) — 链上加密合约状态，做隐私交易/隐私治理；(2) 加密预言机 — 喂价不被MEV提前抢；(3) 隐私拍卖 — bid加密直到结算；(4) 隐私身份 — 加密的credential验证。但因性能限制，目前只能做轻量计算。
Q4：FHE和ZK的互补关系？
ZK证明"我知道某秘密满足关系"，但validator/verifier看不到计算过程；FHE允许validator直接对密文计算。互补：ZK→签名/可验证状态转移；FHE→保护输入隐私。生产案例：fhEVM用FHE保护合约状态，再用ZK证明状态转移正确。
Q5：为什么FHE目前不适合大模型推理？
(1) ResNet-50一次推理
$10^9$ 乘法 → CKKS需小时级；(2) 内存：百万参数模型→GB级密文；(3) 非线性激活（ReLU/Softmax）需多项式近似，精度损失。当前可行：tabular数据上的小型MLP/逻辑回归（参数<1万）。
14. 明日预告
Day 246：tfhe-rs实战 — 写完整Rust代码做加密u8算术，跑benchmark，理解Zama技术栈，为Day 247的Inco做准备。
今日产出: fhe_compare.md(本文 ~620行) + 选型决策树 Lines: ~620