同态加密基础：从部分同态到全同态加密的数学原理
概述
2009 年，Craig Gentry 在其博士论文中提出第一个全同态加密（Fully Homomorphic Encryption, FHE）方案，解决了一个困扰密码学界 30 余年的公开问题：能否在不解密的情况下，对加密数据执行任意计算？
这个问题的意义远超学术范畴。如果数据在加密状态下仍可被计算，那么一个不可信的远程服务器可以处理用户数据却对其内容一无所知——"可算不可见"从理论可能变为工程现实。
同态加密并非凭空出现。从 1978 年 RSA 算法隐含的乘法同态特性，到 Paillier 的加法同态，再到 ElGamal 的乘法同态，密码学家们逐渐意识到：加密与计算并非必然对立。Gentry 的贡献在于证明了：通过"引导"（Bootstrapping）技术，有限次同态计算可以扩展为无限次，从而实现真正的全同态加密。
本文从数学基础出发，系统梳理同态加密从部分同态（PHE）、类同态（SHE）到全同态（FHE）的演进脉络，解析主流方案（BFV/BGV/CKKS/TFHE）的设计思想与适用场景，并讨论这一领域从理论到工程落地的关键挑战。
同态加密的定义
形式化定义
一个同态加密方案包含四个算法：
KeyGen(1^λ) → (pk, sk) // 密钥生成
Enc(pk, m) → c // 加密
Dec(sk, c) → m // 解密
Eval(pk, f, c₁, c₂, ..., cₜ) → c_f // 密文计算核心性质：对于任意允许的函数 f 和任意明文 m₁, m₂, ..., mₜ：
Dec(sk, Eval(pk, f, Enc(pk, m₁), ..., Enc(pk, mₜ))) = f(m₁, ..., mₜ)即：先计算后解密 = 先解密后计算。这个看似简单的性质蕴含着深刻的数学结构。
同态能力的层次
根据支持的运算类型和次数，同态加密分为三个层次：
| 类型 | 缩写 | 支持的运算 | 典型方案 |
|---|---|---|---|
| 部分同态（Partially Homomorphic） | PHE | 仅加法 或 仅乘法 | RSA（乘法）、Paillier（加法）、ElGamal（乘法） |
| 类同态（Somewhat Homomorphic） | SHE | 有限次加法和乘法 | BGV（早期版本）、BFV（无引导时） |
| 全同态（Fully Homomorphic） | FHE | 无限次加法和乘法 | Gentry 方案、BFV+引导、CKKS+引导、TFHE |
部分同态加密：历史起点
RSA 的乘法同态
RSA 算法天然具有乘法同态性：
Enc(m₁) · Enc(m₂) = m₁^e · m₂^e = (m₁ · m₂)^e = Enc(m₁ · m₂)这意味着两个密文的乘积解密后等于对应明文的乘积。这个性质在 RSA 设计之初并未被视为特性，反而一度被认为是安全隐患（因为它允许攻击者操纵密文）。
安全影响：RSA 的乘法同态直接导致了选择密文攻击（CCA）的威胁。现代 RSA 加密必须使用 OAEP 填充来破坏同态结构。
Paillier 的加法同态
1999 年，Pascal Paillier 提出的加密方案具有加法同态性：
Enc(m₁) · Enc(m₂) = Enc(m₁ + m₂ mod n)Paillier 基于合数剩余类问题（Decisional Composite Residuosity Assumption, DCRA），其安全性与因子分解难度无关。
应用场景：电子投票（计票方可以在不知道单个选票的情况下计算总和）、隐私保护的统计分析。
ElGamal 的乘法同态
ElGamal 方案基于离散对数问题，具有乘法同态：
(c₁^r, c₂^r · g^m') = Enc(m · m')在阈值密码学和重加密混合网（Re-encryption Mix-net）中有重要应用。
部分同态的局限性
PHE 的核心限制是只能做一种运算。RSA 只能做乘法，Paillier 只能做加法。现实中的计算通常需要两种运算交替进行（如：计算平均值需要先加后乘），PHE 无法直接满足。
从部分同态到全同态：核心障碍
噪声问题
Gentry 之前的所有尝试都面临同一个障碍：噪声增长。
在同态加密方案中，密文包含"噪声"——一种微小的随机扰动，它是安全性的基础（使密文看起来随机），但每次同态运算都会增加噪声：
新鲜密文噪声: ε
加法后噪声: ε₁ + ε₂（线性增长）
乘法后噪声: ε₁ × ε₂（二次增长）当噪声超过某个阈值时，解密就会失败。SHE 方案允许有限次运算（噪声未超标前），但无法支持任意深度的计算。
为什么不能直接"重加密"？
直觉上，如果能在噪声超标前"重置"噪声，就能支持更多运算。但问题是：在不解密的情况下如何降低噪声？ 这正是 Gentry 的突破所在。
Gentry 的突破：引导（Bootstrapping）
核心思想
Gentry 提出的引导（Bootstrapping）技术的本质是：
用同态加密方案本身来解密自己的密文，输出一个噪声重置的"新鲜"密文。形式化描述：
c* = Eval(pk, Dec, c, sk_enc)其中 sk_enc 是用同一方案加密后的私钥。方案同态地执行自己的解密算法，输出一个新的密文 c*，其加密的是与原密文相同的明文，但噪声重置为初始水平。
为什么这能工作？
关键在于：解密电路深度 < 方案支持的计算深度。
如果方案能同态执行最多 L 层运算，而解密只需要 L-1 层，那么方案就可以同态地解密自己——消耗一层计算能力来"刷新"密文，剩余的计算能力仍可用于后续运算。
Gentry 的具体方案
Gentry 的方案基于理想格（Ideal Lattice）上的困难问题：
- 基础方案：构造一个 SHE 方案，其解密电路相对简单
- 稀疏子集和问题（Sparse Subset Sum Problem, SSSP）：作为安全性基础
- 压缩公钥技术：通过"稀疏化"使公钥中的信息量减少，从而降低解密电路深度
- 引导：同态执行解密，实现噪声重置
性能与现实
Gentry 的原始方案极其缓慢：密文计算比明文计算慢约 10¹² 倍。这在理论上有里程碑意义，但离工程应用遥不可及。后续 15 年的研究主要围绕性能优化展开。
第二代 FHE 方案：格密码的回归
2012 年后，基于格密码（Lattice-based Cryptography）的 FHE 方案取代了 Gentry 的理想格方案，成为主流。这些方案的安全性基于 LWE（Learning With Errors） 问题或其变体 RLWE（Ring-LWE）。
BGV 方案（Brakerski-Gentry-Vaikuntanathan, 2011）
设计思想：通过"模数切换"（Modulus Switching）控制噪声增长，避免昂贵的引导操作。
核心机制：
密文模数 q → 切换为更小的 q' → 噪声按比例缩小模数切换的关键洞察：如果密文 c 模 q 加密了明文 m，那么将 c 乘以 q'/q 后四舍五入到整数，就得到了模 q' 的新密文，其噪声大致按 q'/q 比例缩小。
优势：
- 可以在不引导的情况下执行多层运算
- 支持精确的整数算术（模 p 的整数域）
- 参数灵活，可根据计算深度精确配置
BFV 方案（Brakerski/Fan-Vercauteren, 2012）
BFV 是 BGV 的变体，采用不同的噪声管理策略：
- 缩放因子 Δ：明文 m 编码为 ⌊Δ·m⌉，其中 Δ 是一个大整数（通常为 t 的某次幂）
- 噪声上界：始终保持在固定范围内，通过"舍入"操作控制
- 明文空间：ℤₜ[x]/(xⁿ + 1)，即模 t 的整数多项式
[[c₀ + c₁·s]]_q ≈ Δ·m + e解密时计算 ⌊Δ⁻¹ · [[c₀ + c₁·s]]_q⌉ mod t 即可恢复明文。
与 BGV 的区别：
- BFV 在加密时缩放明文，BGV 在运算时缩放密文
- BFV 的噪声管理更直接，参数选择更直观
- 两者在功能上等价，性能相近
CKKS 方案（Cheon-Kim-Kim-Song, 2016）
CKKS 是专门为实数/复数近似计算设计的 FHE 方案，在机器学习推理场景中广泛使用。
核心创新：将明文视为 ℂⁿ/² 中的向量（通过 CRT 编码），利用环 ℤ[x]/(xⁿ + 1) 的结构进行 SIMD 批处理。
近似计算的本质：
CKKS 解密结果 ≈ m + e_approx其中 e_approx 是可控的近似误差。这不是缺陷而是特性——CKKS 天然容忍微小误差，与机器学习等近似应用场景完美契合。
关键技术：
- 重缩放（Rescaling）：每次乘法后除以缩放因子 Δ，保持噪声水平
- 重线性化（Relinearization）：将密文从 3 个元素压缩回 2 个元素（乘法后密文膨胀）
- 自同构（Automorphism）：实现密文内部的旋转操作（循环移位），用于向量运算
| 特性 | BFV/BGV | CKKS |
|---|---|---|
| 明文类型 | 精确整数 | 近似实数/复数 |
| 舍入方式 | 精确舍入 | 近似舍入 |
| 适用场景 | 精确计算（投票、统计） | 近似计算（ML推理、信号处理） |
| SIMD 支持 | 是（需整数编码） | 是（自然复数向量） |
TFHE 方案（Chillotti-Gama-Georgieva-Izabachène, 2016）
TFHE 采用完全不同的技术路线：基于环面（Torus）上的门限全同态加密。
核心特点：
- 极快的引导操作：单次引导在毫秒级完成（约 10-100ms）
- 逐门（Gate-by-gate）计算：每个逻辑门（AND/OR/XOR 等）都通过引导刷新噪声
- 布尔电路原生支持：天然适合二进制电路
优势：引导速度快，适合深度电路（如 AES 加密的布尔电路实现） 局限：密文尺寸较大，对于大整数算术不如 BFV/CKKS 高效
主流方案对比
┌─────────────────────────────────────────┐
│ 同态加密方案谱系 │
├──────────┬──────────┬──────────┬─────────┤
│ BFV │ BGV │ CKKS │ TFHE │
┌───────────────────┼──────────┼──────────┼──────────┼─────────┤
│ 明文类型 │ 精确整数 │ 精确整数 │ 近似实数 │ 布尔/整数│
│ SIMD 批处理 │ ✓ │ ✓ │ ✓ │ ✗ │
│ 引导速度 │ 慢(秒级) │ 慢(秒级) │ 慢(秒级) │ 快(毫秒)│
│ 适合电路深度 │ 中等 │ 深 │ 中等 │ 很深 │
│ 密文膨胀 │ 中等 │ 中等 │ 中等 │ 较大 │
│ 主要应用场景 │ 整数统计 │ 深度计算 │ ML推理 │ 布尔电路│
│ 代表开源库 │ SEAL │ SEAL │ SEAL/HElib│ Concrete│
└───────────────────┴──────────┴──────────┴──────────┴─────────┘数学基础：为什么格密码？
LWE 问题
所有现代 FHE 方案的安全性都基于 LWE（Learning With Errors）问题或其变体。
LWE 问题定义：给定 (A, b = A·s + e mod q)，其中 A 是随机矩阵，s 是秘密向量，e 是从窄分布 χ 中采样的噪声向量，恢复 s。
为什么 LWE 适合 FHE？
- 加法同态：两个 LWE 密文相加，结果加密的是明文的和
- 最坏情况到平均情况的归约：Regev (2005) 证明，解决平均情况 LWE 至少与解决最坏情况格问题（如 GapSVP）一样难
- 量子抗性：格问题目前没有已知的量子算法能高效求解
环结构优化
原始 LWE 的密钥和密文尺寸都是 O(n²)。通过引入多项式环 Rq = ℤq[x]/(xⁿ + 1)，可以将尺寸降到 O(n)：
- RLWE：在环上定义 LWE，密钥和密文都是环元素
- NTT 加速：利用数论变换（Number Theoretic Transform）实现 O(n log n) 的多项式乘法
- SIMD 打包：通过中国剩余定理（CRT），一个密文可以打包数千个明文值
工程挑战与现实
性能差距
尽管 15 年来 FHE 性能提升了约 10⁶ 倍，但密文计算仍比明文计算慢约 1000-100000 倍（取决于方案和优化程度）。
| 操作 | 明文时间 | FHE 时间 | 慢倍数 |
|---|---|---|---|
| 整数加法 | < 1ns | ~10μs | ~10,000× |
| 整数乘法 | < 1ns | ~100μs | ~100,000× |
| AES 一轮 | ~1ns | ~10ms | ~10,000,000× |
参数选择的权衡
FHE 方案面临固有的安全-效率-精度三角权衡：
安全性 (λ)
/\
/ \
/ \
/ 权衡 \
/ 区域 \
/________\
效率 (速度) 精度 (噪声余量)- 更大的 n（环维度） → 更安全，但更慢
- 更大的 q（密文模数） → 更多计算空间（更深电路），但更大密文、更低安全
- 引导频率 → 更频繁的引导 = 更稳定的噪声水平，但更慢
引导的工程实现
引导是 FHE 性能的核心瓶颈之一。以 BFV/CKKS 为例，引导操作通常占单次同态计算总时间的 60-80%。
引导的本质是同态执行解密电路，涉及：
- 密钥切换（Key Switching）：将密文从一种密钥形式转换为另一种
- 模数约减（Modulus Reduction）：降低噪声水平
- 自同构操作（CKKS）：实现旋转以处理 SIMD 打包
国密视角：同态加密与国密算法的关系
国密算法的同密性
当前国密标准（SM2/SM3/SM4）均不具备同态特性：
- SM2 基于椭圆曲线，密文不具备同态结构
- SM4 是对称加密，设计上刻意避免同态性（防止密文操控攻击）
- SM3 是哈希函数，设计上具有抗原像和抗碰撞性
国密环境下的隐私计算路径
在信创/国密合规场景中，隐私计算的需求同样迫切。当前的技术路线：
- 国密传输 + FHE 计算：数据使用 SM4 加密传输，在不可信环境使用 FHE 进行计算
- SM4 的有限同态利用（理论层面）：SM4-CTR 模式下，若两个密文使用相同的密钥和 nonce 进行加密，则
C1 ⊕ C2 = P1 ⊕ P2。但这不是安全的同态加密方案——因为重复使用同一 nonce 会严重破坏 CTR 模式的安全性（等价于 two-time pad 攻击）。此性质仅具有理论分析意义，不能用于实际隐私计算。 - 国密硬件加速 + FHE：利用国密安全芯片保护 FHE 密钥，FHE 提供计算隐私
标准化进展
截至 2026 年，中国密码学会正在推进同态加密相关标准研究，但尚未发布正式的同态加密算法标准。GM/T 0045《密码模块安全要求》中涉及的安全计算场景为 FHE 的合规使用预留了框架。
应用场景
隐私保护的机器学习推理
用户(加密数据) → 云端模型(同态计算) → 加密结果 → 用户(解密)典型场景：医疗影像 AI 诊断（医院数据不出院，AI 公司模型不泄露）。
安全多方计算
FHE 是安全多方计算（MPC）的一种特殊形式：
- 参与方各自加密数据
- 在密文上联合计算
- 结果仅揭示最终输出，不泄露输入
加密数据库查询
Microsoft 的 Always Encrypted（基于确定性加密 + 有限同态）和 CryptDB 项目展示了加密数据库的可行性。FHE 可以支持更复杂的查询（如 WHERE 子句中的比较运算）。
金融风控
银行间联合风控模型：各方加密本地数据，在密文上训练/推理，获取联合评分而不泄露客户信息。
参考来源
- [Gentry 2009] C. Gentry, "Fully Homomorphic Encryption Using Ideal Lattices," STOC 2009.
- [BGV 2011] Z. Brakerski, C. Gentry, V. Vaikuntanathan, "Fully Homomorphic Encryption without Bootstrapping," ITCS 2012.
- [BFV 2012] Z. Brakerski, "Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP," CRYPTO 2012.
- [CKKS 2016] J.H. Cheon, A. Kim, M. Kim, Y. Song, "Homomorphic Encryption for Arithmetic of Approximate Numbers," ASIACRYPT 2016.
- [TFHE 2016] I. Chillotti, N. Gama, M. Georgieva, M. Izabachène, "Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds," ASIACRYPT 2016.
- [Regev 2005] O. Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," STOC 2005.
- [Fan & Vercauteren 2012] J. Fan, F. Vercauteren, "Somewhat Practical Fully Homomorphic Encryption," IACR Cryptology ePrint Archive 2012/144.
- Microsoft SEAL — 开源 FHE 库，支持 BFV/CKKS
- OpenFHE — 开源 FHE 库，支持 BGV/BFV/CKKS/TFHE 等
- FHE.org — FHE 社区与历史记录
相关实践
- 如需了解全同态加密在工程实践中的具体实现与性能数据，请参阅《全同态加密工程实践：从理论圣杯到生产落地的距离有多远》
- 如需了解 LWE 问题的数学基础及其与格密码学的关系，请参阅《Learning With Errors (LWE)：格密码学的共同数学基础》