土法炼钢兴趣小组的算法知识备份

全同态加密(FHE)技术详解

目录

引言

在数据为王的时代,数据隐私和安全变得至关重要。我们希望在利用数据带来价值的同时,保护其不被泄露。传统的数据加密技术(如 AES、RSA)可以有效地保护静态存储和传输中的数据,但一旦需要对数据进行计算或处理,就必须先解密。解密后的数据以明文形式暴露在内存中,极易受到攻击,这在云计算等第三方计算环境中构成了巨大的安全风险。

全同态加密(Fully Homomorphic Encryption, FHE)是一种革命性的加密技术,它允许直接在密文上进行任意计算,而无需事先解密。计算结果在解密后与在明文上进行相同计算的结果完全一致。这项技术被誉为密码学的“圣杯”,因为它解决了在不暴露数据内容的情况下进行数据处理的难题。

什么是同态加密?

同态加密(Homomorphic Encryption, HE)的核心思想是,存在一个加密函数 \(\text{Encrypt}\) 和一个解密函数 \(\text{Decrypt}\),对于某些操作(例如 \(+\)\(*\)),在密文上执行操作等同于在明文上执行操作。

形式上,一个同态加密方案包括以下几个算法: 1. \(\text{KeyGen}()\): 生成加密密钥(公钥 \(pk\))和解密密钥(私钥 \(sk\))。 2. \(\text{Encrypt}(pk, m)\): 使用公钥 \(pk\) 将明文 \(m\) 加密成密文 \(c\)。 3. \(\text{Decrypt}(sk, c)\): 使用私钥 \(sk\) 将密文 \(c\) 解密成明文 \(m\)。 4. \(\text{Evaluate}(pk, op, c_1, c_2, \dots)\): 在密文上执行 \(op\) 操作。

根据支持的运算类型和次数,同态加密可以分为以下几类:

全同态加密的演进

FHE 的概念早在 1978 年就由 Rivest、Adleman 和 Dertouzos 提出,但直到 2009 年才由 Craig Gentry 在其博士论文中给出了第一个可行的构造方案。

FHE 的核心原理:噪声的挑战

要理解 FHE,首先必须理解其核心挑战:噪声(Noise)

在几乎所有现代 FHE 方案中(主要基于格密码学),加密过程并不仅仅是将明文 \(m\) 变成一个数学上等价的密文。为了保证安全性,加密时会故意引入一个随机的、较小的“噪声” \(e\)。你可以把这个噪声想象成给原始信息披上的一层“伪装”。

一个简化的加密过程看起来像这样: \[ c = \text{Encrypt}(m) \approx A \cdot s + m + e \]

这里: - \(A\) 是一个公开的大数或多项式。 - \(s\) 是私钥,一个保密的、较小的数。 - \(m\) 是我们要加密的明文。 - \(e\) 就是那个随机的小噪声。

解密时,利用私钥 \(s\),我们可以消除 \(A \cdot s\) 这一项,得到 \(m + e\)。因为 \(m\) 通常被编码在一个比 \(e\) 大得多的空间里,只要噪声 \(e\) 足够小,我们就可以通过取模等操作把 \(m\)\(m + e\) 中恢复出来。

关键问题来了:当我们在密文上进行计算时,这个噪声会发生什么?

如果噪声增长得太大,超过了一个特定的阈值,它就会“淹没”原始的明文 m,导致 m + e 的结果变得混乱不堪,解密时就再也无法恢复出正确的 m

因此,噪声管理是所有 FHE 方案的中心问题。如何控制计算过程中噪声的增长,决定了 FHE 方案的成败。

噪声管理技术详解

目前主要有两种主流的噪声管理技术:层级式 FHE自举

1. 层级式 FHE (Leveled FHE) 与模切换

层级式 FHE 的思想非常直观:在计算开始前,就为噪声的增长预留出足够的空间

打个比方: 想象你的明文信息是一个小纸船,漂浮在一个水桶里。噪声就是桶里的水位。 - 加密:把小纸船(明文)放进一个只有少量水(初始噪声)的水桶里。 - 加法运算:往桶里加一瓢水(噪声线性增加)。 - 乘法运算:往桶里倒进一盆水(噪声急剧增加)。 如果水位(噪声)太高,淹没了纸船(明文),信息就丢失了。

层级式 FHE 的做法是,在计算开始前,根据你计划要执行的运算(比如 3 次乘法和 10 次加法),预先估算出总共需要“倒入多少水”。然后,选择一个足够深的大水桶(即一个非常大的模数 q),确保即使在所有计算完成后,水位也永远不会淹没纸船。

这种方案的优点是效率高,因为不需要进行额外的噪声控制操作。缺点是计算的复杂度(电路深度)必须在开始前就确定,无法进行无限次运算。

技术深化:模切换 (Modulus Switching)

为了进一步优化,第二代 FHE 方案(如 BGV, BFV)引入了模切换技术。这相当于在不改变“水位”和“纸船”相对高度的情况下,给整个水桶“瘦身”。

举例说明: 假设一个密文 \(c\) 在一个大模数 \(Q\) 下,其简化表示为 \(c \equiv m + e \pmod{Q}\)\(Q\) 非常大,比如 \(1,000,000\)。明文 \(m=5\),噪声 \(e=1000\)。所以 \(c \equiv 1005 \pmod{1000000}\)。 此时,噪声 \(e\) 相对于模数 \(Q\) 很小。

现在,我们想在乘法后减小噪声。假设乘法后,噪声增长到了 \(e' = 200,000\)。 模切换技术会选择一个新的、更小的模数 \(q\)(比如 \(50,000\)),然后将密文 \(c\) 转换到这个新模数下。这个过程大致是计算 \(c' = \text{round}(c \cdot \frac{q}{Q})\)\[ c' = \text{round}((m+e') \cdot \frac{q}{Q}) = \text{round}(m \cdot \frac{q}{Q} + e' \cdot \frac{q}{Q}) \] \[ c' \approx m \cdot \frac{q}{Q} + e' \cdot \frac{q}{Q} = 5 \cdot 0.05 + 200000 \cdot 0.05 = 0.25 + 10000 \] 在新的标度下,新的噪声 \(e''\) 大约为 \(10,000\),相对于新的模数 \(q=50,000\),比例仍然很小。但噪声的绝对值被有效地“压缩”了。

通过在一系列计算步骤中不断地切换到更小的模数,BGV/BFV 等方案可以在有限的电路深度内非常高效地控制噪声。

2. 自举 (Bootstrapping):实现完全同态的关键

自举是 Craig Gentry 的天才构想,是实现真正 FHE(无限次运算)的钥匙。它的核心思想是:当密文的噪声快要满时,用同态的方式给它“洗个澡”,得到一个噪声很低的新密文

这个“洗澡”的过程,就是同态地执行解密电路

打个比方: 你有一个装有“脏数据”(高噪声密文 \(c\))的加密盒子。你想清理它,但你不能打开盒子(解密)。 幸运的是,你还有另一个神奇的“清洁机器人”,这个机器人可以隔着盒子操作。 要启动机器人,你需要给它一把“万能钥匙”,但这把钥匙本身也必须放在一个加密的盒子里(加密的私钥 \(\text{Enc}(sk)\))。

自举的过程就是: 1. 你把装有“脏数据”的盒子 \(c\) 和装有“加密钥匙”的盒子 \(\text{Enc}(sk)\) 一起交给清洁机器人。 2. 机器人在你看不见的情况下,用加密的钥匙在加密的盒子上模拟了一遍“开锁-清理-上锁”的过程。 3. 最后,机器人返回给你一个崭新的加密盒子 \(c'\)。这个新盒子里装的数据和原来完全一样(相同的明文 \(m\)),但它变得非常“干净”(噪声极低)。

技术深化:自举如何工作

假设我们有一个密文 \(c\),它加密着明文 \(m\),但噪声 \(e\) 很大。 解密函数是 \(\text{Decrypt}(sk, c) = m\)。 自举过程就是计算 \(c' = \text{Evaluate}(\text{Decrypt_Circuit}, \text{Enc}(pk, sk), c)\)

这里: - \(\text{Decrypt_Circuit}\) 是解密过程的电路表示。例如,解密可能包含一些模乘和模加操作。我们可以把这些操作本身也用同态加密的方式来执行。 - \(\text{Enc}(pk, sk)\) 是用公钥 \(pk\) 加密的私钥 \(sk\)。这是自举过程最巧妙也最昂贵的部分,被称为“密钥切换”。 - \(c\) 是我们想要刷新的高噪声密文。

\(\text{Evaluate}\) 函数会同态地执行 \(\text{Decrypt_Circuit}\)。它的输入是加密的 \(sk\) 和加密的 \(m\)(即 \(c\)),输出的将是一个新的密文 \(c'\)。这个 \(c'\) 加密的内容是什么呢?正是 \(\text{Decrypt}(sk, c)\) 的结果,也就是 \(m\)

由于 \(c'\) 是一个全新的加密结果,它的噪声回到了初始的、非常低的水平。通过这个过程,我们成功地“刷新”了密文,打破了计算深度的限制。只要在噪声溢出前周期性地执行自举,我们就可以进行无限次的运算。

举例说明: - 假设一个 TFHE 方案,明文是 0 或 1。 - 一个密文 \(c\) 加密着 \(m=1\),经过多次运算后,它的内部表示(一个多项式)变得非常“嘈杂”。 - 此时我们调用 \(\text{Bootstrap}(c)\)。 - 该函数会取一个加密后的私钥 \(\text{Enc}(sk)\),然后同态地计算一系列布尔门操作,例如 \(\text{NAND}(\dots, \text{NAND}(c, \text{Enc}(sk))\dots)\),这个过程等价于在密文上运行解密电路。 - 其输出是一个全新的密文 \(c'\),它内部的多项式非常“干净”,但解密后,\(\text{Decrypt}(sk, c')\) 的结果仍然是 \(1\)

通过自举,FHE 从“有限级”走向了“完全”,实现了理论上的任意计算。当然,代价是自举本身是一个非常消耗计算资源的操作。

主流 FHE 方案技术详解

目前,最流行的 FHE 方案主要有三类,它们基于不同的数学原理,适用于不同的应用场景。

方案 主要特点 运算类型 典型应用
BFV/BGV 支持精确整数运算 \(t\) 整数的加法和乘法 精确计数、数据库查询、基因数据分析
CKKS 支持近似浮点数运算 实数/复数的加法和乘法 机器学习、信号处理、统计分析
TFHE/FHEW 极快的自举速度 逐比特的布尔运算 布尔电路求值、密码查找表、安全计算

1. BFV 和 BGV 方案:精确整数计算

BFV 和 BGV 是非常相似的方案,它们都是为模整数环上的精确计算而设计的。如果你需要进行的运算是像 (a + b) mod t(a * b) mod t 这样的,那么 BFV/BGV 是最佳选择。

技术核心:基于 Ring-LWE 的多项式密码学

运算原理:

举例说明:加密整数向量

假设我们的明文模数 \(t=100\),我们想加密一个向量 v = [10, 25]。 1. 编码: 将 v 编码为明文多项式 \(m(x) = 10 + 25x\)。 2. 加密: 使用 BFV 方案的 \(\text{Encrypt}\) 函数,得到密文 \(c_v = (c_0, c_1)\),这是一对非常大的、看起来完全随机的多项式。 3. 同态计算: 假设我们想计算 v' = v + [5, 5]。我们先将 [5, 5] 编码为 \(m'(x) = 5 + 5x\),然后同态地计算: \[ c_{res} = \text{Add}(c_v, \text{Encrypt}(m'(x))) \] 或者,如果 [5, 5] 是公开的,可以直接计算: \[ c_{res} = \text{AddPlain}(c_v, m'(x)) \] 4. 解密: 将 \(c_{res}\) 发回给持有私钥的用户,解密后得到多项式 \(m_{res}(x) = 15 + 30x\),解码后即可得到结果向量 [15, 30]


2. CKKS 方案:近似浮点数计算

CKKS 是 FHE 的一个重大突破,因为它允许在加密的浮点数(或更准确地说是复数)上进行近似计算。这使其成为隐私保护机器学习的理想工具。

技术核心:将噪声视为精度的一部分

CKKS 的天才之处在于它对待噪声的方式。在 BFV/BGV 中,噪声是必须被精确移除的“敌人”。而在 CKKS 中,噪声被视为计算过程中自然产生的、可以容忍的“精度误差”。

图解 CKKS 编码与噪声

这个图展示了 CKKS 如何巧妙地利用缩放因子来处理数据和噪声。

CKKS 编码与噪声

举例说明:隐私保护的平均值计算

假设两个医院想计算其患者的平均年龄,但不想透露各自的数据。 - 医院 A 的患者年龄: v_A = [45.5, 60.2] - 医院 B 的患者年龄: v_B = [38.8, 55.5]

  1. 编码与加密:
    • 医院 A 使用 CKKS 加密 v_A 得到密文 \(c_A\)
    • 医院 B 使用 CKKS 加密 v_B 得到密文 \(c_B\)
  2. 同态计算: 一个云服务器接收 \(c_A\)\(c_B\),并执行同态加法和标量乘法。
    • 计算总和: \(c_{sum} = \text{Add}(c_A, c_B)\)
    • 计算平均值: \(c_{avg} = \text{MulByPlain}(c_{sum}, 0.25)\) (乘以 1/4)。
  3. 解密: 将 \(c_{avg}\) 返回给任意一方(或一个指定方)进行解密。
    • 解密后得到的结果向量 \(v_{res}\) 将会是 [21.074..., 28.924...],非常接近真实平均值 [21.075, 28.925]。这个微小的误差就是由同态计算中累积的噪声引起的。

3. TFHE 和 FHEW 方案:可编程自举

TFHE 和 FHEW 这类方案的专长是处理布尔电路,并且它们拥有目前最快的自举(Bootstrapping)能力

技术核心:逐比特运算与可编程自举

举例说明:构建一个加密的比较器

假设我们想安全地比较两个加密的 4 比特数字 \(A = a_3a_2a_1a_0\)\(B = b_3b_2b_1b_0\)\(A\)\(B\) 的每一位都被 TFHE 单独加密,我们有 8 个密文:\(c_{a3}, \dots, c_{a0}\)\(c_{b3}, \dots, c_{b0}\)

  1. 分解为布尔电路: 比较操作 A > B 可以被分解为一个复杂的布尔电路,其中充满了 XOR、AND 和 NOT 门。
  2. 同态门运算:
    • 计算 \(x_i = \text{XOR}(c_{ai}, c_{bi})\)
    • 计算 \(g_i = \text{AND}(x_i, c_{ai})\)
    • … (更多复杂的门组合)
  3. 自举: 每经过一次或几次门运算,密文的噪声就会增加。TFHE 会在关键路径上频繁地调用自举来“刷新”密文,确保计算可以继续进行。例如,在计算一个 AND 门时,就可以利用可编程自举,将 AND 的真值表 {(0,0)->0, (0,1)->0, (1,0)->0, (1,1)->1} 作为查找表来实现。
  4. 最终结果: 电路的最终输出是一个加密的比特 \(c_{res}\),解密后,如果结果是 1,则 \(A > B\);如果是 0,则 \(A \le B\)

TFHE 的这种逐比特操作方式虽然看起来繁琐,但其极快的自举速度(毫秒级)使其在需要深度计算电路或执行非标准运算(如激活函数 ReLU)的场景中具有无与伦比的优势。

图解 FHE 工作流程

为了更直观地理解 FHE,我们可以用一个简单的图来描述其工作流程。

FHE 工作流程

上图清晰地展示了 FHE 的基本范式: 1. 客户端使用公钥 pk 加密其敏感数据 xy,得到密文 c_xc_y。私钥 sk 始终由客户端自己保管。 2. 客户端将密文 c_xc_y 以及要执行的计算函数 f(的同态版本)发送给云服务器。 3. 云服务器在完全不知道明文内容的情况下,使用公钥 pk 在密文上执行计算 f,得到结果密文 c_res。 4. 服务器将 c_res 返回给客户端。 5. 客户端使用自己的私钥 sk 解密 c_res,得到最终结果 res,该结果与直接在明文上计算 f(x, y) 的结果一致。

在整个过程中,原始数据和中间计算结果始终处于加密状态,从而保证了数据的机密性。

FHE 的应用场景

FHE 的“密文计算”特性为其在多个领域开辟了广阔的应用前景。

  1. 隐私保护的云存储和计算: 用户可以将加密数据存储在云端,并让云服务商在加密数据上执行各种计算任务(如数据检索、分析),而云服务商无法窥探任何用户数据。这是 FHE 最直接和最经典的应用场景。

  2. 安全多方计算 (Secure MPC): 多个参与方可以共同计算一个函数,而无需透露各自的输入。例如,多家公司可以在不共享各自客户数据的情况下,共同计算客户重合度。

  3. 隐私保护的机器学习 (Private AI):

    • 模型即服务 (Model-as-a-Service): 用户可以将自己的数据加密后发送给一个机器学习模型服务商,在加密状态下进行预测,然后取回加密的预测结果。服务商无法得知用户的输入数据。
    • 联合学习 (Federated Learning): 在联合学习中,FHE 可以用来加密和聚合来自不同用户的模型更新,从而保护每个用户的本地数据隐私。
  4. 金融和医疗领域: 在金融领域,可以使用 FHE 对交易数据进行加密分析,以检测欺诈行为,同时保护客户隐私。在医疗领域,多家医院可以在不泄露患者隐私的前提下,对加密的医疗数据进行联合统计分析,加速医学研究。

挑战与展望

尽管 FHE 前景广阔,但其走向大规模实际应用仍面临一些挑战:

  1. 性能开销: 这是 FHE 最大的障碍。与明文计算相比,FHE 的计算速度要慢上几个数量级(通常是 1000 倍到 1,000,000 倍)。密文的体积也比明文大得多。
  2. 编程复杂性: 开发 FHE 应用需要密码学专业知识,程序员需要理解噪声管理、参数选择等底层细节,开发门槛很高。
  3. 标准化: 目前存在多种 FHE 方案和库,彼此之间不兼容,缺乏统一的行业标准。
  4. 参数安全性: 具体实现时需要根据目标安全级别(如 128-bit 安全)选择合适的多项式维度、模数大小和噪声分布等参数,否则可能在性能和安全之间失衡。

为了应对这些挑战,学术界和工业界正在共同努力: - 硬件加速: 许多研究团队和公司正在开发专用于 FHE 计算的硬件加速器(ASIC/FPGA),有望将性能提升几个数量级。 - 编译器和软件框架: 发展更高级的编译器,可以将普通的高级语言代码(如 C++ 或 Python)自动转换为高效的 FHE 计算电路,从而降低开发难度。 - 方案优化: 不断改进 FHE 算法本身,降低噪声增长速度,提高计算效率。

总结

全同态加密是一项颠覆性的技术,它为在不信任环境中安全地处理数据提供了可能。从 Gentry 的理论突破到如今支持近似计算的 CKKS 方案,FHE 在过去十年中取得了长足的进步。虽然性能和易用性仍然是其广泛应用的瓶颈,但随着算法的不断优化、硬件加速的发展以及软件生态的成熟,我们有理由相信,FHE 将在不远的未来成为保护数据隐私的核心技术之一,深刻地改变云计算、人工智能和数据分析等领域。

值得一提的是,基于格密码学的 FHE 方案天然具有抗量子攻击的特性。在量子计算威胁日益临近的今天,FHE 不仅能保护数据在计算过程中的隐私,还能在后量子时代继续提供可靠的安全保障,这使其战略价值更加凸显。

扩展阅读

如果你对 FHE 感兴趣并希望深入学习或实际应用,以下资源会很有帮助:

开源库: - Microsoft SEAL: 支持 BFV 和 CKKS,文档完善,适合入门。 - PALISADE: 功能全面的 C++ 库,支持多种 FHE 方案。 - HElib: IBM 开发的库,最早的开源 FHE 实现之一。 - Lattigo: Go 语言实现,性能优秀,适合工程化部署。 - TFHE-rs: Rust 实现的 TFHE,专注于布尔电路计算。

学习资源: - Craig Gentry 的博士论文《A Fully Homomorphic Encryption Scheme》是理解 FHE 理论基础的必读文献。 - 各大 FHE 库的官方教程和示例代码是实践的最佳起点。 - FHE.org 社区提供了标准化工作的最新进展和资源汇总。


By .