3.1 同态加密 (Homomorphic Encryption, HE)
3.1 同态加密 (Homomorphic Encryption, HE)
本节摘要：能对密文直接计算吗？同态加密让这成为可能。本节讲清楚 HE 原理（密文运算等价明文运算）、部分同态 vs 全同态、主流方案（BFV/CKKS/BGV）、性能挑战、以及工程落地。读完你能判断项目该不该用 HE、用哪种。
一、HE 的核心思想
HE 工作原理
同态加密（HE）：一种加密方案，允许在密文上直接计算，计算结果解密后等于对明文同样计算的结果。
形式化：Enc(m₁) ⊕ Enc(m₂) = Enc(m₁ ⊕ m₂)，其中 ⊕ 是某种运算（加/乘）。
直觉：传统加密后要计算必须先解密——解密就暴露明文。HE 让你在密文上算，算完才解密，全程不暴露明文。
应用场景：
- 外包计算：企业把加密数据发云，云在密文上算，返回加密结果，企业解密。云看不到明文。
- 隐私机器学习：用户加密输入发模型，模型在密文上推理，返回加密结果，用户解密。模型看不到用户输入。
- 医疗/金融数据共享：医院加密病历发研究方，研究方在密文上分析，不接触明文。
二、同态性的类型
按支持的运算分：
1. 部分同态加密（Partially Homomorphic Encryption, PHE）
- 只支持一种运算（无限次）——加或乘。
- 加法同态：Paillier——可无限加法，不能乘。适合求和、统计。
- 乘法同态：RSA、ElGamal——可无限乘法（同态于乘），不能加。适合特定场景。
- 性能好，工程成熟，但功能受限。
2. 些许同态加密（Somewhat Homomorphic Encryption, SHE）
- 支持加和乘，但有限次——乘法深度有限（如只能 2 次乘法）。
- 因为每次乘法密文"噪声"增长，噪声超过阈值解密失败。
- 适合浅电路计算。
3. 全同态加密（Fully Homomorphic Encryption, FHE）
- 支持任意加和乘（任意电路），无限次。
- Gentry 2009 发明——用"自举"（bootstrapping）在噪声接近阈值时"刷新"密文降低噪声。
- 理论突破，但性能慢（早期慢 10⁶ 倍）。
- 现代方案（BFV/CKKS/BGV）优化到慢 1000-10000 倍，可用但仍有性能挑战。
三、全同态的噪声和自举
FHE 的核心难点是噪声管理：
噪声：HE 密文含随机噪声，加密时小，但每次运算（特别是乘法）噪声增长。噪声超过阈值，解密失败（输出乱码）。
自举（Bootstrapping）：Gentry 的关键发明——当噪声接近阈值时，用加密的密钥对密文"再加密"一次，降低噪声。这需要"在密文上计算解密电路"，看似循环但可行（因为解密电路是浅的）。
自举是 FHE 的性能瓶颈——每次自举很慢（ms 级），限制了深度电路。现代优化（自举优化、批处理）让自举更快，但仍是大开销。
层级 FHE（Leveled FHE）：不用自举，按预设乘法深度选参数，噪声刚好够。适合已知深度的电路，避免自举开销。多数实际应用用层级 FHE 而非自举 FHE。
四、主流 FHE 方案
1. BGV（Brakerski-Gentry-Vaikuntanathan）
- 整数运算，支持模切换控制噪声。
- 适合精确整数计算（计数、比较）。
2. BFV（Brakerski-Fan-Vercauteren）
- BGV 的实用变体，整数运算，SIMD 批处理。
- 适合精确整数运算，OpenFHE/SEAL 库支持。
3. CKKS（Cheon-Kim-Kim-Song）
- 近似实数运算——支持浮点，但有微小误差。
- 适合机器学习（浮点推理）、统计分析。
- 性能比 BFV 好（近似换速度），但结果有误差（要容忍）。
- 主流 ML 用 CKKS。
4. TFHE（Fully Homomorphic Encryption over Torus）
- 支持快速比较和非线性函数（如 ReLU）。
- 适合需要分支/比较的电路（如决策树、神经网络激活）。
- 性能好，但参数设置复杂。
选方案：
- 精确整数 → BFV/BGV
- 近似实数（ML）→ CKKS
- 比较密集 → TFHE
五、HE 的性能挑战
HE 性能是工程落地的核心问题：
1. 计算慢：FHE 比明文慢 1000-10000 倍。一个矩阵乘法明文 ms 级，FHE 秒级。
2. 密文膨胀：明文 1KB，密文可能 100KB-1MB（膨胀 100-1000 倍）。存储和通信开销大。
3. 噪声管理：深度电路要自举，自举慢；或用层级 FHE 但要预设深度。
4. 参数调优：HE 参数（多项式度、模链、噪声分布）影响性能和安全，调优复杂。
5. 编程模型：HE 不是"加密后随便算"——要写支持同态运算的电路，普通代码不能直接跑。需要专门库（SEAL/OpenFHE）和电路设计。
6. 非线性难：HE 擅长加乘，但比较、分支、非线性激活（ReLU、sigmoid）难——要近似（如用多项式近似 ReLU）或用 TFHE。
六、加速 HE
性能优化的方向：
1. SIMD 批处理：一个密文打包多个明文（如 4096 个），一次运算处理多个数据。BFV/CKKS 支持，是性能关键。
2. GPU 加速：HE 核心运算是大数多项式乘法，GPU 适合。CUDA 加速库（如 Phantom、Arima）。
3. 专用硬件：FPGA/ASIC 加速 HE——如 DARPA DPRP 项目、Cornami、Zama 的硬件。
4. 算法优化：NTT（数论变换）加速多项式乘法、自举优化（如 CKKS 自举从秒到 ms）。
5. 混合方案：HE + MPC（HE 做重计算，MPC 做关键步骤）、HE + TEE（TEE 加速非关键部分）。
七、HE 的工程落地
1. 库：Microsoft SEAL（最流行，BFV/CKKS）、OpenFHE（前身 PALISADE，全方案）、HElib（BGV）、TFHElib（TFHE）、Concrete（Zama，TFHE 工具）。
2. 应用案例：
- Microsoft Edge 密码监控：用 HE 让浏览器报告泄露密码而不暴露用户密码。
- 医疗联合研究：iDASH 竞赛用 HE 在加密基因组数据上分析。
- 隐私广告归因：Meta 用 HE 做跨平台广告归因，不暴露用户身份。
- 隐私机器学习：Crypton、CrypTen 用 HE 加密推理。
3. 部署要点：
- 选对方案（精确/近似、整数/实数）。
- 用 SIMD 批处理提吞吐。
- 预设电路深度，避免不必要自举。
- 评估性能——HE 适合低频高价值计算（医疗、金融），不适合高频实时。
- 客户端要解密能力——密钥管理是重点。
八、HE 在 PETs 中的定位
1. 外包计算场景：HE 适合"数据加密发云，云算返回"——单方数据，一方计算。
2. 性能权衡：HE 比 MPC 慢但通信少（不需多方交互），比 TEE 快但信任不同（不依赖硬件）。
3. 和 MPC 互补：HE 适合单方数据外包，MPC 适合多方数据联合。混合方案（HE+MPC）取长补短。
4. 不是银弹：HE 慢、编程复杂、非线性难——只适合特定场景（低频高价值、加乘为主）。
⚠️ 常见误读：以为"HE 加密后随便算"。HE 要写支持同态运算的电路，普通代码不能直接跑。且非线性（比较/分支/ReLU）难，要近似或用 TFHE。
💡 关键直觉：HE 让密文上直接计算，结果解密等价明文计算。类型 PHE（部分，Paillier 加/RSA 乘）、SHE（些许，有限深度）、FHE（全同态，任意电路，Gentry 自举刷新噪声）。方案 BFV/BGV（整数）、CKKS（实数 ML）、TFHE（比较）。挑战是慢 1000-10000x、密文膨胀、非线性难、参数调优。加速用 SIMD/GPU/ASIC/混合。适合外包计算/隐私 ML/医疗金融，是低频高价值场景，不是银弹。
要点速记
- HE 核心：密文运算等价明文运算，加密后直接计算，全程不暴露明文。
- 类型：PHE（部分，Paillier 加法/RSA 乘法，无限单运算）、SHE（些许，有限乘法深度）、FHE（全同态，任意电路，Gentry 2009 自举）。
- 噪声和自举：运算让密文噪声增长，超阈值解密失败；自举在噪声接近阈值时刷新降低噪声，是 FHE 性能瓶颈；层级 FHE 避免自举预设深度。
- 方案：BFV/BGV（精确整数）、CKKS（近似实数，ML 主流）、TFHE（比较和非线性）。
- 挑战：慢 1000-10000x、密文膨胀 100-1000x、噪声管理、参数调优、编程模型（要写电路）、非线性难（ReLU 要近似）。
- 加速：SIMD 批处理（一密文打包多明文）、GPU 加速（CUDA 库）、专用硬件（FPGA/ASIC）、算法优化（NTT/自举优化）、混合方案（HE+MPC/TEE）。
- 库：SEAL（最流行）、OpenFHE、HElib、TFHElib、Concrete。
- 案例：Microsoft Edge 密码监控、iDASH 基因组、Meta 广告归因、Crypton 隐私 ML。
- 定位：外包计算场景（单方数据一方计算）、性能介于 MPC 和 TEE 之间、和 MPC 互补、不是银弹（低频高价值、加乘为主）。
同态加密类型