【密码学百科】同态加密：从 Paillier 到全同态加密（FHE）

在传统加密体系中，加密是一道不可逾越的屏障——数据一旦被加密，就必须先解密才能进行任何有意义的计算。这意味着每一次对敏感数据的处理都要求数据以明文形式暴露在计算环境中，从根本上构成了安全隐患。然而，如果我们能够直接在密文上执行加法、乘法乃至任意复杂的计算，使得计算结果解密后等同于在明文上执行相同运算的结果，那么数据的整个生命周期都无需离开加密保护。这就是同态加密(Homomorphic Encryption, HE)的核心承诺。

同态加密的设想最早可以追溯到 Rivest、Adleman 和 Dertouzos 在 1978 年提出的”隐私同态”(privacy homomorphism)概念——仅仅比 RSA 算法的发表晚了一年。然而，从这一设想到真正可用的全同态加密方案，密码学界走过了长达三十余年的艰难探索。2009 年，Craig Gentry 在其博士论文中首次构造出全同态加密(Fully Homomorphic Encryption, FHE)方案，被誉为密码学领域的”圣杯”突破。此后十余年间，BGV、BFV、CKKS、TFHE 等实用方案相继问世，配合专用编译器和硬件加速技术，FHE 正在从理论走向实际部署。

本文是密码学百科系列的第 42 篇。我们将从同态加密的基本概念与分类出发，详细探讨部分同态方案 Paillier 的原理与实现，回顾 Gentry 的突破性构造，深入分析 BGV、BFV、CKKS、TFHE 等现代方案的设计哲学，并展望 FHE 在隐私计算领域的前沿应用。

一、同态加密的概念与分类

先看一张图，把这一节的关键关系串起来。

flowchart LR
    A[明文] --> B[加密]
    B --> C[密文计算]
    C --> D[噪声管理]
    D --> E[解密结果]

从代数同态到加密同态

“同态”(homomorphism)是代数学中的基本概念，指的是两个代数结构之间保持运算关系的映射。设 f 是从群 (G, ·) 到群 (H, ) 的映射，如果对任意 a, b ∈ G 都有 f(a · b) = f(a) f(b)，则 f 是一个同态映射。将这一概念引入加密体系，就得到了同态加密的定义：设 Enc 为加密函数，Dec 为解密函数，如果存在某种运算 ⊕ 使得 Dec(Enc(m₁) ⊕ Enc(m₂)) = m₁ + m₂（或 m₁ × m₂），则称该加密方案对加法（或乘法）具有同态性。

更一般地，一个同态加密方案由四个多项式时间算法组成：密钥生成(KeyGen)、加密(Encrypt)、解密(Decrypt)和求值(Evaluate)。其中求值算法 Evaluate 接受一个电路 C 和一组密文作为输入，输出一个新的密文，使得解密该密文等价于在对应的明文上执行电路 C 所表示的计算。

三个层次的同态加密

根据求值算法所能处理的电路复杂度，同态加密方案被分为三个层次。

部分同态加密(Partially Homomorphic Encryption, PHE) 仅支持单一类型的运算——要么是加法，要么是乘法——且可以执行无限次。PHE 方案的历史最为悠久：RSA 的原始形式（不带填充）天然支持乘法同态，ElGamal 加密方案同样具备乘法同态性，而 Paillier 加密方案则支持加法同态。PHE 方案效率高、实现成熟，但功能受限——单纯的加法或单纯的乘法无法表达通用计算。

有限同态加密(Somewhat Homomorphic Encryption, SHE) 同时支持加法和乘法两种运算，但只能执行有限次数，即所能求值的电路深度有一个上界。SHE 方案的核心限制来源于噪声(noise)的增长：每次同态运算都会在密文中引入或放大噪声，当噪声超过某个阈值时，解密将无法正确恢复明文。因此，SHE 方案只能处理深度受限的电路。尽管如此，对于许多实际场景——例如低次多项式求值、简单的统计计算——SHE 已经足够实用。

全同态加密(Fully Homomorphic Encryption, FHE) 支持对任意电路的同态求值，没有深度限制。从图灵完备性的角度来看，任何可计算函数都可以用布尔电路表示，因此 FHE 在理论上允许在密文上执行任意计算。FHE 的关键技术挑战在于如何克服噪声增长的瓶颈——Gentry 的”自举”(bootstrapping)技术正是为此而生。

理解这三个层次之间的关系至关重要：PHE 是 SHE 的特例，而 SHE 加上自举能力就升级为 FHE。从另一个角度看，任何一个 SHE 方案只要能够同态地执行自身的解密电路（这意味着电路深度上限必须大于解密电路的深度），就可以通过自举变换为 FHE 方案。这一洞察正是 Gentry 突破性工作的理论基石。

二、部分同态方案

在进入全同态加密的深水区之前，让我们先深入理解部分同态加密方案，因为它们不仅有独立的实用价值，更是理解 FHE 的概念基础。

RSA 的乘法同态性

RSA 加密的最朴素形式（即不带 OAEP 等填充方案的教科书式 RSA）天然具有乘法同态性。设公钥为 (n, e)，对明文 m₁ 和 m₂ 的加密分别为 c₁ = m₁^e mod n 和 c₂ = m₂^e mod n，则 c₁ · c₂ = (m₁ · m₂)^e mod n，这恰好是 m₁ · m₂ 的合法密文。需要强调的是，教科书式 RSA 在实际应用中是不安全的——它是确定性加密，不满足语义安全性(semantic security)，因此 RSA 的乘法同态性主要具有理论意义。

ElGamal 的乘法同态性

ElGamal 加密方案在群 Z_p* 上也具有乘法同态性。设公钥为 (g, h = g^x)，对明文 m₁ 的加密选择随机数 r₁ 得到密文 (g^r₁, m₁ · h^r₁)，对 m₂ 的加密选择 r₂ 得到 (g^r₂, m₂ · h^r₂)。将两个密文逐分量相乘得到 (g^(r₁+r₂), (m₁ · m₂) · h^(r₁+r₂))，这正是 m₁ · m₂ 的一个合法 ElGamal 密文，对应的随机数为 r₁ + r₂。与教科书式 RSA 不同，ElGamal 加密是概率性的，因此可以在具备乘法同态性的同时保持 IND-CPA 安全性。

Paillier 加密方案

1999 年，Pascal Paillier 提出了一个基于合数剩余类问题(Decisional Composite Residuosity Assumption, DCRA)的公钥加密方案，它具有加法同态性，是目前最广泛使用的 PHE 方案之一。

密钥生成。 选择两个大素数 p 和 q，计算 n = p · q 以及 λ = lcm(p-1, q-1)。选择 g = n + 1 作为生成元（这是一种简化选择）。计算 μ = (L(g^λ mod n²))^(-1) mod n，其中函数 L(u) = (u - 1) / n。公钥为 (n, g)，私钥为 (λ, μ)。

加密。 对明文 m ∈ Z_n，随机选择 r ∈ Z_n*，计算密文 c = g^m · r^n mod n²。

解密。 给定密文 c，计算 m = L(c^λ mod n²) · μ mod n。

加法同态性。 设 c₁ = Enc(m₁) 和 c₂ = Enc(m₂)，则：

c₁ · c₂ mod n² = g^(m₁+m₂) · (r₁ · r₂)^n mod n²

这正是 m₁ + m₂ 的一个合法 Paillier 密文。换言之，密文空间上的乘法对应明文空间上的加法——这是一个从 (Z_n, +) 到 (Z_n², ×) 的同态映射。

此外，Paillier 方案还支持标量乘法：c^k mod n² = Enc(k · m)，即将密文做幂运算等价于明文与常数相乘。加法同态性加上标量乘法意味着 Paillier 可以在密文上计算任意线性函数，这在电子投票、联邦学习的梯度聚合等场景中具有直接的应用价值。

下面用 Python 实现一个简化版的 Paillier 加密方案来演示其加法同态性：

import math
import random

def generate_prime(bits):
    """生成指定位数的素数（简化实现，仅用于演示）"""
    while True:
        n = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime(n):
            return n

def is_prime(n, k=20):
    """Miller-Rabin 素性测试"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def L(u, n):
    """Paillier L 函数: L(u) = (u - 1) / n"""
    return (u - 1) // n

class Paillier:
    def __init__(self, bits=512):
        p = generate_prime(bits)
        q = generate_prime(bits)
        self.n = p * q
        self.n2 = self.n * self.n
        self.g = self.n + 1
        self.lam = math.lcm(p - 1, q - 1)
        self.mu = pow(L(pow(self.g, self.lam, self.n2), self.n), -1, self.n)

    def encrypt(self, m):
        """加密明文 m"""
        assert 0 <= m < self.n, "明文必须在 [0, n) 范围内"
        while True:
            r = random.randrange(1, self.n)
            if math.gcd(r, self.n) == 1:
                break
        c = (pow(self.g, m, self.n2) * pow(r, self.n, self.n2)) % self.n2
        return c

    def decrypt(self, c):
        """解密密文 c"""
        m = (L(pow(c, self.lam, self.n2), self.n) * self.mu) % self.n
        return m

    def add_ciphertexts(self, c1, c2):
        """密文加法：Dec(c1 * c2 mod n^2) = m1 + m2 mod n"""
        return (c1 * c2) % self.n2

    def scalar_mul(self, c, k):
        """标量乘法：Dec(c^k mod n^2) = k * m mod n"""
        return pow(c, k, self.n2)

# 演示加法同态性
paillier = Paillier(bits=256)

m1, m2 = 12345, 67890
c1 = paillier.encrypt(m1)
c2 = paillier.encrypt(m2)

# 密文相乘 = 明文相加
c_sum = paillier.add_ciphertexts(c1, c2)
result = paillier.decrypt(c_sum)
print(f"Enc({m1}) * Enc({m2}) -> Dec = {result}")
print(f"期望结果: {m1 + m2} = {m1 + m2}")
assert result == m1 + m2, "加法同态性验证失败"

# 标量乘法
k = 7
c_mul = paillier.scalar_mul(c1, k)
result_mul = paillier.decrypt(c_mul)
print(f"Enc({m1}) ^ {k} -> Dec = {result_mul}")
print(f"期望结果: {k} * {m1} = {k * m1}")
assert result_mul == k * m1, "标量乘法验证失败"

print("所有同态性验证通过！")

这段代码清楚地展示了 Paillier 方案的核心特性：在密文空间中执行乘法运算（或幂运算），解密后得到的是明文空间中对应的加法运算（或标量乘法）结果。整个计算过程中，执行运算的一方只接触密文，从未看到任何明文信息。

三、含噪加密：理解 FHE 的安全基石

在深入 Gentry 的 FHE 突破之前，我们需要先建立一个至关重要的前置直觉：为什么 FHE 方案中的噪声不是一个无奈的技术代价，而是整座大厦的安全地基。不理解这一点，就无法真正理解 FHE 为什么这么难。

LWE：噪声即安全

前面介绍的 Paillier 方案基于数论假设（合数剩余问题），它的密文中没有噪声，因此可以支持无限次加法运算。但 Paillier 只能做加法——要实现同时支持加法和乘法的全同态加密，密码学界转向了一类完全不同的数学工具：格(lattice)问题，特别是 Regev 在 2005 年提出的带误差的学习问题(Learning with Errors, LWE)。

LWE 的核心思想可以用一个简单的对比来理解。考虑一个线性方程组 A x = b，其中 A 是公开的矩阵，x 是秘密向量。如果 b = A x 精确成立，任何人都可以用高斯消元法在多项式时间内恢复 x——这毫无安全性可言。但如果我们加入一个小的噪声向量 e，令 b = A x + e，情况就发生了根本性的变化：在噪声的干扰下，恢复 x 变得与最坏情况下的格问题一样困难——这是目前已知最难的计算问题之一，即使量子计算机也无法高效求解。

用一个具体的数值例子来建立直觉：

无噪声（不安全）：
  A = [3, 5; 7, 2],  x = [1; 0],  b = Ax = [3; 7]
  高斯消元 -> 立刻恢复 x = [1; 0]

有噪声（安全）：
  A = [3, 5; 7, 2],  x = [1; 0],  e = [1; -1],  b = Ax + e = [4; 6]
  看到 (A, b) 的攻击者无法区分 x=[1;0]+噪声 还是 x=[0;1]+噪声
  -> 噪声将信息"模糊"到不可恢复

这就是 LWE 的安全性直觉：噪声不是加密方案的缺陷，而是安全性的唯一来源。 没有噪声，就没有安全性。这一认识立刻引出了 FHE 面临的根本困境——我们需要在密文上计算，但计算会改变噪声；而噪声又是我们不能放弃的东西。

噪声预算：一个终将耗尽的资源

基于 LWE 的加密方案中，每个新鲜密文都携带一个初始的小噪声 e。我们可以把每个密文想象成一个容器，容器的总容量就是”噪声预算”(noise budget)——它由加密参数决定（主要是密文模数 q 的大小）。初始噪声只占据容器的一小部分，剩余空间就是可用于计算的预算。

不同运算消耗噪声预算的速度截然不同：

• 同态加法：两个密文的噪声大致相加。如果两个密文各有噪声 e1 和 e2，结果密文的噪声约为 e1 + e2。这是线性增长，非常温和——你可以执行大量加法而不会显著消耗预算。
• 同态乘法：两个密文的噪声近似相乘。结果密文的噪声约为 e1 * e2 加上交叉项。这是乘性增长，极其剧烈——每一层乘法都使噪声量级翻倍甚至平方级膨胀。

一个直觉性的类比：想象你在一间有回声的房间里听人说话。加法运算像是有人在旁边轻声附和，回声略微变大；乘法运算像是把回声本身再放大一遍，几次之后，回声就彻底淹没了原始信号。

这就解释了为什么 SHE（有限同态加密）有电路深度的限制：每一层乘法消耗大量噪声预算，预算耗尽就意味着解密失败。而 FHE 需要解决的核心问题是：如何在噪声即将耗尽时，将密文”刷新”回低噪声状态，同时不暴露明文。

自举的直觉：在锁着的箱子里修理锁

Gentry 在 2009 年给出的答案是一个极其巧妙的递归构造——自举(bootstrapping)。其核心思想是：同态地执行解密算法本身。

具体而言：假设一个密文 c 的噪声即将耗尽。我们把加密后的私钥 Enc(sk) 和密文 c 一起交给同态求值算法，让它在密文空间中”运行”解密电路 Dec(sk, c)。这个过程的输入是加密的，输出也是加密的——但输出是一个全新的密文，它只包含执行解密电路过程中引入的少量新噪声，而原来累积的大量旧噪声被”解密掉”了。

这就像在一个锁着的箱子里修理锁：你不需要打开箱子（暴露明文），就能把锁的状态（噪声水平）重置为出厂设定。代价是：这个”修理”过程本身极其昂贵——自举是 FHE 中计算代价最高的操作，通常比普通的同态乘法慢两到三个数量级。

自举对 SHE 方案有一个关键要求：方案支持的电路深度必须大于其自身解密电路的深度。否则，同态执行解密电路本身就会耗尽噪声预算——你还没修好锁，锁就又坏了。Gentry 将满足这一条件的方案称为”可自举的”(bootstrappable)。这一概念是下一节 Gentry 构造的理论基石。

四、Gentry 的 FHE 突破

三十年的等待

自 1978 年 Rivest 等人提出隐私同态的概念以来，密码学界一直在寻找支持任意计算的全同态加密方案。Boneh、Goh 和 Nissim 在 2005 年提出了一个可以执行任意次加法和一次乘法的方案，被视为迈向 FHE 的重要一步，但距离真正的全同态仍有巨大鸿沟。2009 年，斯坦福大学博士生 Craig Gentry 在其导师 Dan Boneh 的指导下，在博士论文”A Fully Homomorphic Encryption Scheme”中给出了第一个 FHE 构造，这一成果被广泛认为是自公钥密码学诞生以来最重要的理论突破之一。

噪声困境的工程视角

上一节已经建立了含噪加密的基本认识：噪声是 LWE 安全性的来源，但同态运算会放大噪声，最终耗尽噪声预算。Gentry 面临的核心挑战正是如此——如何打破噪声预算对电路深度的硬性限制。

下面的示意图概括了噪声增长与自举触发的完整生命周期：

噪声增长与 Bootstrapping 触发条件

  新鲜密文          同态加法           同态乘法         噪声预算耗尽
 (低噪声)      (噪声线性增长)     (噪声平方级膨胀)     (解密失败)
    |               |                  |                  |
    v               v                  v                  v
 ┌──────┐  Add  ┌──────┐  Mul   ┌──────┐  Mul   ┌──────┐
 │noise │ ───> │noise │ ────> │noise │ ────> │XXXXX│
 │ ░    │      │ ░░   │       │ ░░░░ │       │█████│
 │      │      │      │       │ ░░░░ │       │█████│
 └──────┘      └──────┘       └──────┘       └──────┘
    │                                            │
    ^                                            v
    │           Bootstrapping                    │
    └──────────── (同态解密) ─────────────────────┘
           噪声重置为初始水平
           代价：最昂贵的 FHE 操作

这张图揭示了一个关键的工程现实：FHE 中几乎所有的性能开销都围绕着 bootstrapping 展开。加法运算的噪声增长是温和的（线性），因此可以大量执行；乘法运算的噪声增长是剧烈的（近似平方级），每一层乘法都在迅速消耗噪声预算。一旦噪声逼近阈值，必须触发 bootstrapping 将密文”刷新”回低噪声状态——而这一操作本身的计算代价远超所有其他运算之和。

个人观察： 从我长期跟踪 FHE 发展的经验来看，bootstrapping 的开销是这个领域的「原罪」——它不仅仅是一个工程瓶颈，而是从根本上决定了 FHE 实用化的整条技术路线。围绕这个问题，研究者分化出了两条截然不同的策略：一条是 leveled FHE（如 BGV/BFV），通过精心规划电路深度来彻底回避 bootstrapping，以功能受限换取性能可控；另一条是 TFHE 路线，接受 bootstrapping 的存在但将其极致优化（可编程自举甚至将 bootstrapping 变成了一种计算工具）。这两条路线的分歧本质上反映了一个更深层的判断——你认为未来的 FHE 应用是「浅电路、大批量」（如隐私数据库查询），还是「深电路、通用计算」（如隐私机器学习推理）？前者适合 leveled 方案，后者别无选择，必须直面 bootstrapping。理解这一点，就理解了整个 FHE 生态的技术布局逻辑。

自举：从 SHE 到 FHE 的飞跃

上一节已经介绍了自举的直觉——同态地执行解密算法来刷新密文噪声。这里我们深入 Gentry 构造中自举的具体机制。

假设我们有一个 SHE 方案，它能够处理深度不超过 d 的电路。当一个密文经过若干次运算后噪声即将超过阈值时，我们不在明文世界中解密再重新加密（这需要私钥且会暴露明文），而是执行以下操作：将加密的私钥和待刷新的密文一起输入 SHE 的求值算法，让它同态地执行解密电路。由于解密是在密文上同态执行的，整个过程不需要实际的私钥（只需要加密后的私钥），也不会暴露明文。而解密电路的输出是一个”新鲜”的密文——它只包含与执行解密电路相关的少量噪声，远小于刷新前的累积噪声。

这一方法要求 SHE 方案满足一个关键条件：它必须是”可自举的”(bootstrappable)，即方案所支持的电路深度 d 必须大于其自身解密电路的深度加上至少一层额外运算的深度。Gentry 称这一性质为”紧凑性”(compactness)——方案需要足够强大以至于能在同态模式下运行自己的解密算法并留有余量。

Gentry 的原始构造基于理想格(ideal lattice)。他首先构造了一个基于理想格的 SHE 方案，但该方案的解密电路深度较大，不满足可自举性条件。为此，他引入了”压缩解密电路”(squashing the decryption circuit)的技术：通过在公钥中发布一个关于私钥的”提示”(hint)——本质上是一个稀疏子集和问题的实例——将解密电路的深度降低到 SHE 方案所能处理的范围内。这一步额外引入了稀疏子集和假设(Sparse Subset Sum Assumption)作为安全性前提。

概念验证与实际困难

Gentry 的构造虽然在理论上实现了 FHE，但距离实用相去甚远。2010 年，Gentry 和 Halevi 发表了第一个 FHE 的概念验证实现。结果令人震惊：单次自举操作在一台高性能服务器上需要约 30 分钟，公钥大小超过 2 GB。这一结果清楚地表明，第一代 FHE 方案在性能上完全不具备实用性，但它证明了 FHE 在原理上是可行的，为后续的优化工作奠定了基础。

五、第二代 FHE：BGV 与 BFV

Gentry 的突破激发了密码学界对 FHE 的巨大热情。在随后几年中，一系列基于带误差的学习(Learning with Errors, LWE)及其环变体(Ring-LWE, RLWE)的新方案被提出，它们在效率上实现了数个数量级的改进。其中最具代表性的是 Brakerski-Gentry-Vaikuntanathan(BGV)方案和 Brakerski/Fan-Vercauteren(BFV)方案。

LWE 与 RLWE 基础

LWE 问题由 Regev 在 2005 年提出：给定一系列形如 (aᵢ, bᵢ = ⟨aᵢ, s⟩ + eᵢ) 的样本，其中 s 是秘密向量，aᵢ 是随机向量，eᵢ 是小的噪声项，要求恢复 s。Regev 证明了 LWE 问题的困难性可以归约到最坏情况下的格问题，这为基于 LWE 的密码方案提供了坚实的安全性理论基础。

RLWE 是 LWE 在多项式环 R_q = Z_q[x]/(x^n + 1) 上的变体，其中 n 通常为 2 的幂。RLWE 具有更紧凑的密钥和密文表示（O(n) 而非 O(n²)），且运算可以利用数论变换(Number Theoretic Transform, NTT)进行加速，因此成为实用 FHE 方案的首选基础。

BGV 方案

BGV 方案由 Brakerski、Gentry 和 Vaikuntanathan 在 2012 年提出。其核心创新是模数切换(modulus switching) 技术：在每次乘法运算后，通过将密文从一个较大的模数 q 切换到一个较小的模数 q’，同时按比例缩小噪声。这一操作本质上是用精度（更小的模数意味着更少的可用空间）换取噪声控制。

BGV 的运作方式可以形象地理解为一个”模数阶梯”(modulus ladder)：初始加密使用最大的模数 q_L，每次乘法后切换到下一级更小的模数 q_{L-1}, q_{L-2}, …。预先设定的阶梯级数 L 决定了方案在不需要自举的情况下所能执行的乘法深度。对于已知深度的电路（这在实践中非常常见），BGV 可以精确地配置模数阶梯，完全避免高代价的自举操作。

BGV 方案在明文编码方面采用了所谓的”打包”(packing)技术：利用中国剩余定理(CRT)将多个明文值打包到同一个 RLWE 密文的不同”槽”(slot)中。这实现了单指令多数据(SIMD) 的并行计算效果——一次同态运算同时作用于所有槽中的值，极大地提升了吞吐量。例如，在多项式环 Z_q[x]/(x^n + 1) 中，如果明文模数 t 使得 x^n + 1 在 Z_t 上分解为 n/d 个 d 次不可约多项式，则每个密文包含 n/d 个槽，每个槽存储一个 Z_{t^d} 中的元素。

BFV 方案

BFV 方案（Brakerski 2012, Fan-Vercauteren 2012）在 BGV 的基础上做了一个重要的简化：它使用固定的密文模数 q，通过不同的噪声管理策略——在乘法后执行”重线性化”(relinearization)和”缩放”(scaling)——来控制噪声增长。BFV 的编程模型更为直观：开发者只需在开始时选择一组参数（多项式次数 n、密文模数 q、明文模数 t），之后的所有运算都在同一模数下进行，不需要像 BGV 那样显式管理模数切换。

BFV 与 BGV 在性能上各有优劣。一般而言，BGV 的模数切换策略使其在深层电路的乘法链中更高效，因为每次切换都压缩了噪声增长；而 BFV 在浅层电路和混合运算模式下可能更具优势，且编程接口更为简洁。实际上，许多现代 FHE 库（如 Microsoft SEAL）同时支持 BGV 和 BFV，允许开发者根据具体应用场景选择最合适的方案。

BGV 和 BFV 共同构成了”第二代 FHE”的核心。它们将 FHE 的实用性提升了数个数量级：密钥大小从 GB 级降至 MB 级，单次乘法从分钟级降至毫秒级。更重要的是，对于许多实际应用，BGV/BFV 的”层级”(leveled)模式——即设定固定的电路深度而不使用自举——已经足够实用，完全避免了自举带来的巨大开销。

六、CKKS：近似计算的 FHE

精确计算与近似计算

BGV 和 BFV 方案在模运算的语境下工作：明文是整数环 Z_t 中的元素，所有运算都是精确的模运算。然而，现实世界中许多重要的计算任务——统计分析、机器学习推理、信号处理——涉及的是实数或浮点数的近似运算。在 BGV/BFV 中处理实数需要繁琐的定点数编码和精心的精度管理。

2017 年，Cheon、Kim、Kim 和 Song 提出了 CKKS 方案(也称为 HEAAN)，它做出了一个范式性的转变：将噪声本身视为近似计算的一部分，而非需要严格控制的敌人。 在 CKKS 中，密文的噪声被当作浮点运算中的舍入误差——只要噪声足够小，解密结果就是明文的一个足够精确的近似值。

编码与重缩放

CKKS 的编码方案将复数向量映射到多项式环的元素。具体而言，给定 n/2 个复数 (z₁, z₂, …, z_{n/2})，CKKS 先通过逆离散傅里叶变换(逆 DFT)的一个变体——作用在分圆多项式的根上——将其编码为一个实系数多项式，再乘以一个缩放因子 Δ 并四舍五入到整数多项式。缩放因子 Δ 的大小决定了编码精度：Δ 越大，近似精度越高。

CKKS 的核心技术创新是重缩放(rescaling) 操作。当两个缩放因子为 Δ 的密文相乘后，结果的缩放因子变为 Δ²。如果不加处理，缩放因子将随着乘法层数呈指数增长，很快耗尽密文模数的空间。重缩放操作将密文除以 Δ 并切换到更小的模数，使缩放因子回归到 Δ。这与 BGV 的模数切换在数学上有相似之处，但目标不同：BGV 的模数切换是为了压缩噪声，CKKS 的重缩放是为了管理缩放因子。

CKKS 在机器学习中的应用

CKKS 对实数运算的原生支持使其成为隐私保护机器学习的首选 FHE 方案。在典型的使用场景中，客户端将特征向量用 CKKS 加密后发送到服务器，服务器在密文上执行已训练好的模型的前向传播，将加密的预测结果返回给客户端解密。

然而，神经网络中的非线性激活函数（如 ReLU、Sigmoid）无法直接用加法和乘法表示。实践中有两种主要策略：一是用低次多项式近似替代非线性函数，例如用二次或四次多项式逼近 ReLU；二是设计专门适配 FHE 的网络架构，用加法和乘法友好的操作替代传统的非线性层。CKKS 的近似特性与多项式近似策略天然契合——少量的近似误差在 CKKS 的噪声模型中被自然吸收。

七、TFHE 与可编程自举

另一条路线：基于环面的 FHE

在 BGV/BFV/CKKS 家族关注深层算术电路的同时，另一条研究路线着眼于布尔电路和低延迟的逐门计算。TFHE(Torus Fully Homomorphic Encryption)由 Chillotti、Gama、Georgieva 和 Izabachène 在 2016 年提出，它基于环面(torus) T = R/Z（即实数模 1 的商群）上的 LWE 问题。

TFHE 的最大特点是逐门自举(gate-by-gate bootstrapping)：每执行一个布尔门（AND、OR、NAND 等）后立即进行一次自举操作来刷新噪声。虽然单次自举有一定开销，但 TFHE 的自举速度极快——在现代硬件上仅需约 10-20 毫秒——这使得它可以对任意深度的布尔电路进行实时计算，而不需要像 BGV/BFV 那样预先确定电路深度。

可编程自举

TFHE 的自举操作不仅仅是噪声刷新——它可以被”编程”以在刷新噪声的同时执行一个查找表(Look-Up Table, LUT)运算。这一特性被称为可编程自举(Programmable Bootstrapping, PBS)。在传统 FHE 方案中，自举纯粹是一个维护性操作——它只负责降低噪声。而 TFHE 的 PBS 将自举与实际计算融为一体：通过在自举过程中编码一个任意的单变量函数，PBS 可以在单次自举的代价内完成函数求值和噪声刷新两个任务。

PBS 的实用意义极为重大。首先，它使得非线性函数的计算变得高效——Sigmoid、ReLU 甚至任意的分段函数都可以通过一次 PBS 完成，而无需用高次多项式去逼近。其次，PBS 使得 TFHE 特别适合处理整数运算和比较操作——这些在 BGV/BFV/CKKS 中需要较深电路才能实现的操作，在 TFHE 中通过 PBS 可以直接完成。

主流 FHE 方案横向对比

至此，我们已经介绍了四种主流 FHE 方案。下表从核心维度对它们进行横向对比：

选择方案的经验法则：如果你的计算以线性运算为主且数据量大，选 BGV/BFV 的 SIMD 模式；如果涉及浮点近似计算（如 ML 推理），选 CKKS；如果需要通用计算且无法预知电路深度，选 TFHE。

八、FHE 编译器与开发框架

FHE 方案的数学复杂度极高，直接使用底层 API 进行开发对应用程序员而言几乎不可能。因此，FHE 编译器和高层开发框架成为推动 FHE 实用化的关键基础设施。

Microsoft SEAL 是最广泛使用的开源 FHE 库之一，使用 C++ 编写，支持 BGV 和 CKKS 方案。SEAL 提供了相对友好的 API：开发者指定加密参数（多项式模次数、系数模数链、明文模数），然后使用封装好的加法和乘法操作处理密文。SEAL 的设计哲学是在正确性和易用性之间取得平衡——它不会自动进行模数切换或重线性化，但提供了清晰的接口让开发者在需要时调用这些操作。

OpenFHE 是由 DARPA DPRIVE 项目资助开发的综合性 FHE 库，它整合了此前多个独立库（HElib、PALISADE 等）的功能，支持 BGV、BFV、CKKS 和 TFHE/FHEW 等几乎所有主流方案。OpenFHE 的一个重要特性是其模块化架构，使得研究者可以方便地替换和比较不同的底层实现。

Concrete 是 Zama 公司开发的基于 TFHE 的 FHE 编译器框架。Concrete 的设计目标是让开发者用几乎标准的 Python 代码编写程序，由编译器自动处理加密、参数选择、PBS 插入等所有密码学细节。开发者只需在普通 Python 函数上添加装饰器，Concrete 就会将其编译为 FHE 电路。这一”密码学透明”的编程模型极大地降低了 FHE 的使用门槛。

Google FHE 编译器 基于 MLIR(Multi-Level Intermediate Representation)框架构建，旨在将通用 C++ 程序自动转换为 FHE 电路。它利用 MLIR 的多层中间表示能力，在不同抽象层次上对 FHE 电路进行优化——从高层的循环变换到底层的 NTT 调度。

HElib 是 IBM 研发的开源 FHE 库，由 Shai Halevi 和 Victor Shoup 主导开发。HElib 对 BGV 方案的 SIMD 打包技术做了深入的工程优化，并率先实现了高效的自举算法。虽然 HElib 的 API 学习曲线较陡，但在需要极致性能的场景中仍是重要选择。

九、FHE 的性能现状与基准测试

FHE 距离”实用”还有多远？这是每一个关注隐私计算的人都在追问的核心问题。坦率地说，尽管近年来取得了巨大进展，FHE 的性能开销仍然是其大规模部署的主要障碍。

当前性能基准

下表汇总了主流 FHE 库在典型配置下的关键操作延迟（单线程 CPU，128-bit 安全级别）：

Microsoft SEAL 基准。 在 CKKS 模式下（n=2^15，乘法深度 5-8 层），SEAL 可以对打包了 2^14 个浮点数的密文执行一次 SIMD 乘法，耗时约 10 毫秒。这意味着等效吞吐量约为每秒 160 万次浮点乘法——虽然绝对延迟远高于明文，但考虑到一次操作同时处理了上万个数据点，吞吐量的差距远小于延迟的差距。在 BFV 模式下，单次密文乘法（含重线性化）约 5-10 毫秒，SIMD 打包同样可以将数千个整数编码到一个密文中并行计算。

Zama Concrete 基准。 Zama 的 Concrete ML 框架（基于 TFHE）可以在加密数据上执行逻辑回归和决策树推理。典型场景下，一个在 tabular 数据集上训练的逻辑回归模型，单次加密推理耗时约 50-200 毫秒；XGBoost 等树模型的推理耗时约 100 毫秒到数秒，取决于树的数量和深度。Zama 在近期的基准测试中展示了在加密数据上运行量化神经网络的能力，8-bit 量化的小型 CNN 推理耗时在秒级。

OpenFHE 基准。 OpenFHE 作为整合了 HElib 和 PALISADE 的综合库，在 BGV/BFV 模式下的 SIMD 批处理乘法性能与 SEAL 相当。其 CKKS bootstrapping 实现在 n=2^16 的配置下可以在约 200-500 毫秒内完成一次自举，支撑 CKKS 方案处理深层电路。TFHE/FHEW 模式下的门自举延迟约 10 毫秒，与 Concrete 的数据一致。

现实部署案例。 Apple 在 iOS 的 Live Caller ID 功能中使用了同态加密来在不暴露用户通讯录的前提下查询来电号码；Google 的 Private Join and Compute 协议使用同态加密进行隐私保护的集合交集计算。这些部署表明，对于特定的高价值场景，FHE 的性能已经进入可用区间。

硬件加速

软件层面的优化已经接近瓶颈，硬件加速被视为下一个数量级提升的关键。Intel HEXL(Homomorphic Encryption Acceleration Library)提供了针对 Intel CPU 的 AVX-512 优化指令集，在 NTT、大整数模运算等 FHE 核心操作上实现了显著加速。它已被集成到 Microsoft SEAL 和 OpenFHE 等主流库中。

GPU 加速是另一个活跃的研究方向。FHE 中的 NTT 运算和大规模多项式操作具有天然的并行性，非常适合 GPU 的 SIMD 架构。多个研究团队报告了在 GPU 上实现 10 倍到 100 倍加速的结果，使得 CKKS 的自举操作可以在百毫秒级完成。

更为前瞻性的方向是专用 ASIC 加速器的设计。DARPA 的 DPRIVE(Data Protection in Virtual Environments)项目资助了 Intel、Duality Technologies 等公司开发 FHE 专用芯片。这些设计目标是将 FHE 的性能提升到与明文计算相差不超过一个数量级的水平——如果实现，将彻底改变 FHE 的实用性前景。

一个值得深思的现象是：FHE 的「十万倍开销」这个数字已经成了一种流行的刻板印象，但它严重过时了。早期 Gentry 原始方案的十万倍开销是事实，但现代基于 CKKS 的机器学习推理系统已经将开销压缩到了 10-100 倍的量级——尤其是在利用 SIMD 打包技术批量处理同构数据时，吞吐量的实际差距远小于延迟的差距。对于特定的高价值场景——比如医疗影像的加密推理，其中一次推理的经济价值可能高达数百美元——即使是 100 倍的计算开销也完全在可接受范围内。笔者认为，真正阻碍 FHE 实用化的不是「绝对性能不够快」，而是「通用计算的期望不切实际」。我们不应该问「FHE 什么时候能替代明文计算」，而应该问「哪些应用场景的价值密度足够高，使得 FHE 的开销变得可接受」。这种思维转变——从追求通用性到聚焦高价值垂直场景——正是 FHE 从实验室走向产品的关键。

十、应用前景

隐私保护的机器学习推理

FHE 最引人注目的应用方向之一是隐私保护的机器学习推理(Private ML Inference)。在这一场景中，模型提供方（如医疗 AI 公司）拥有训练好的模型，用户拥有敏感数据（如医疗影像）。双方都不愿向对方暴露自己的资产：用户不想让公司看到自己的医疗数据，公司不想泄露模型参数。通过 FHE，用户将数据加密后发送给公司，公司在密文上运行模型推理，返回加密的预测结果——整个过程中，公司从未看到用户数据，用户也无法通过加密的中间结果逆向工程模型。

目前已有多个概念验证系统展示了 FHE 在机器学习推理中的可行性：基于 CKKS 的系统可以在密文上运行包含数十层的卷积神经网络，基于 TFHE 的系统可以执行决策树和随机森林分类。虽然性能开销仍然显著，但对于高价值、强隐私需求的场景（如医疗诊断、金融风控），额外的计算延迟是可接受的代价。

加密数据库查询

加密数据库查询(Encrypted Database Query)是另一个前景广阔的应用方向。设想一个场景：企业将数据库托管在云端，但不信任云服务商。使用 FHE，企业可以将整个数据库加密存储在云端，当需要查询时，将查询条件加密后发送给云端，云端在不解密数据库的情况下执行查询，返回加密的结果。

这一方向与隐私信息检索(Private Information Retrieval, PIR)密切相关。PIR 允许用户从数据库中检索一条记录而不让数据库管理员知道是哪条记录被检索了。基于 FHE 的 PIR 方案可以实现计算高效的单服务器 PIR，这在密码学中是一个具有里程碑意义的结果——早先的信息论安全 PIR 方案需要多个不合谋的服务器。

FHE 与安全多方计算的混合协议

FHE 并非银弹——对于某些计算模式，纯 FHE 的效率远不如其他隐私计算技术。近年来的一个重要趋势是将 FHE 与安全多方计算(MPC)相结合，发挥各自的优势。例如，在隐私机器学习中，线性层（矩阵乘法、卷积）适合用 FHE 处理——它利用了 CKKS 的 SIMD 特性实现高效的密文向量运算；而非线性层（ReLU、最大池化）则适合用 MPC 的秘密共享和混淆电路来处理——这些操作在 FHE 中代价极高，但在 MPC 中相对高效。

这种”混合协议”(hybrid protocol)的设计哲学是让每种技术做它最擅长的事情。CrypTFlow2、MOTION、ABY 等框架都支持在同一计算流程中动态切换 FHE 和 MPC 操作。

从工程实践来看，FHE 永远不会完全取代 MPC，反之亦然——两者的优势在本质上是互补的。FHE 的核心强项是非交互性：数据加密后可以被任意计算，不需要数据持有方在线参与，这使得它天然适合「一方拥有数据、另一方拥有算法」的客户端-服务器模型。但 FHE 处理多方输入的场景时非常笨拙——你需要所有人用同一把公钥加密，或者引入门限 FHE 等复杂机制。MPC 则恰恰相反：它天生适合多方各持私有输入的场景，但需要所有参与方在线交互。因此，笔者认为未来隐私计算的主流架构不会是纯 FHE 或纯 MPC，而是根据计算流图中每个子任务的特性动态选择最优原语的混合协议——线性运算用 FHE 的 SIMD 批处理、非线性运算用 MPC 的混淆电路、长期存储用 FHE 的加密态——这种「按需切换」的架构才是实用隐私计算的终局形态。

合规与数据主权

FHE 还为数据合规和数据主权提供了全新的解决思路。在 GDPR 等隐私法规日益严格的背景下，跨境数据流动面临越来越多的法律限制。FHE 提供了一种技术路径：数据以加密形式离开本国管辖范围，在外国的计算基础设施上进行处理，但由于计算全程在密文上进行，外国的服务商在技术上无法访问任何明文数据。这一特性使得 FHE 成为满足数据本地化要求的同时利用全球计算资源的潜在方案。

尽管如此，FHE 的法律地位尚未完全明确——加密后的数据是否仍构成”个人数据”、FHE 的安全保证是否满足特定法规的要求、密钥管理的责任如何界定——这些问题都需要技术界和法律界共同探讨。

展望

同态加密从 1978 年的概念萌芽到 2009 年的理论突破，再到今天日益成熟的工程实践，走过了近半个世纪的历程。虽然 FHE 的性能开销仍然是其大规模应用的主要瓶颈，但进步的速度是惊人的：过去十年间，FHE 的性能已经提升了约五到六个数量级。如果这一趋势持续——配合专用硬件加速器的到来——FHE 有望在未来五到十年内进入主流生产部署。

从更宏观的角度看，FHE 代表了一种深刻的理念转变：安全不应以牺牲功能为代价，加密不应成为计算的障碍。 在一个数据日益成为核心资产、隐私日益成为基本权利的世界中，能够在不暴露数据的前提下释放数据价值的技术，将具有不可估量的战略意义。全同态加密正是这样一项技术——它告诉我们，密码学不仅仅是关于”锁住”信息，更是关于在锁住的状态下让信息继续为人类服务。

密码学百科系列 · 第 42 篇

← 上一篇：安全多方计算 | 系列目录 | 下一篇：零知识证明系统 →