全同态加密和隐私互联网的黎明

原创 Kurt Pan XPTY

2025年07月24日 12:34

原文：https://bozmen.io/fhe
作者：Barış,
译者：Kurt Pan

“在互联网上使用加密技术，就相当于安排一辆装甲车，把住在纸箱里的人的信用卡信息送到住在公园长椅上的人手里。”——Gene Spafford

想象一下，你向谷歌发送一个加密的问题，得到你想要的准确结果——而他们根本不知道你的问题是什么，也不知道他们返回了什么结果。实现这一目标的技术被称为全同态加密 (FHE) 。

我第一次听说 FHE 的作用时，并不相信这是可能的。但它确实是可能的——而且已经在今天的现实世界系统中工作了。

https://bozmen.io/fhe-current-apps

它允许对密文（加密数据）进行任意计算，而无需先解密。解密后，计算结果与对明文（未加密数据）执行的结果一致。

摘自 Craig Gentry 的幻灯片
https://eurocrypt.iacr.org/2021/slides/gentry.pdf

FHE 的摩尔定律

由于 FHE 允许加密计算，用户可以在互联网上始终保持数据加密（发送、服务器计算、接收）。这可以防止任何数据泄露的可能性。完全隐私性。

那么，为什么它不像 HTTPS 那样成为默认协议呢？为什么不是每个人都在使用它？为什么大多数人甚至都没听说过它呢？

因为它对于大多数应用程序来说仍然不实用，因为它非常慢。但这种情况正在迅速改变 ，我将在下面解释。

当前的 FHE 计算开销是明文操作的 1,000 倍到 10,000 倍。在存储方面，密文可能比明文大 40 到 1,000 倍。它就像 1990 年的互联网——技术上很棒，但实际用处有限。

https://youtu.be/PfSZL9LsMCg

有趣的是： FHE 算法的速度每年都会提升 8 倍。 2011年，每比特运算需要 30 分钟，而现在只需几毫秒。下图展示了其显著的速度提升。

图表显示，截至 2014 年，改进速度已达到 10^12 倍。过去十年，改进速度也在持续保持。我将在本文后面深入探讨这一点。

拐点

如果这种显著的进步持续下去，我们将接近计算的拐点。在不久的将来，FHE 的速度将足以实现以下目标：

加密云计算
加密 LLM 推理
保密区块链智能合约

这影响深远。建立在收集用户数据之上的整个商业模式可能会过时。既然有其他服务可以计算你的密文，那为什么还要发送你的明文呢？

互联网的“默认偷偷监视”可以变成“默认隐私”。

深入了解

以下章节将深入探讨本文主张的各个方面。如果你对某个部分特别感兴趣，可以跳到任何部分阅读。也可以按顺序阅读，因为它们是依逻辑排序的：

问题：安全的阿喀琉斯之踵
解决方案：定义全隐私计算
技术深度探究：FHE 的实际工作原理
更多关于性能改进：FHE 的摩尔定律：每年速度提高 8 倍
连接所有：计算的未来是加密的

安全的阿喀琉斯之踵

所有数据都存在于以下三种状态之一：

静态（存储在磁盘上）
传输中 （通过网络移动）
正在使用 （正在内存中处理）

对于前两个问题，我们都已经有健壮的解决方案：

静态： 磁盘加密、文件系统加密。
传输中： TLS/SSL、VPN、端到端加密。

但在使用过程中 ——当数据加载到 RAM 并由 CPU 处理时——它会被解密。这就是现代安全机制的阿喀琉斯之踵。云提供商、内部人员、攻击者或被入侵的 CPU 都可以读取你的明文数据。

想一想你听说过的每一次重大数据泄露事件：

2014 年名人照片泄露事件（苹果 iCloud）
23andMe 基因数据盗窃案
Capital One 黑客攻击事件

这些都是使用过程中或静态的加密失败造成的。数据一旦被加载到内存进行处理，就变得脆弱不堪。

FHE 解决了这个问题。数据在云端的整个生命周期内都可以保持加密，我们称之为“全隐私计算”。

定义全隐私计算

想象一下，在互联网上，你的数据总是被加密：

静态加密
传输中加密
使用过程加密

这意味着：

你的设备绝不会向任何服务器发送纯文本
服务器仅处理加密数据
只有你可以解密结果

隐私版 ChatGPT 会话可能如下所示：

# 你的设备
pk, sk = keygen() # pk: 公钥, sk: 私钥
enc_prompt = encrypt("Why did the dev go to therapy?", pk)
server.send(enc_prompt, pk)

# OpenAI服务器（永远不能解密并看到你的prompt）
enc_prompt, pk = client.receive()
enc_llm = encrypt(LLM_MODEL, pk)
enc_answer = enc_llm.run(enc_prompt)
client.send(enc_answer)

# 你的设备
enc_answer = server.receive()
answer = decrypt(enc_answer, sk)
print(answer)
"""Because of too many unresolved dependencies!"""

OpenAI 计算出正确的答案，但永远无法以纯文本形式看到你的问题或他们的答案。

隐私成为计算不变量。

FHE 的工作原理

术语“ 同态 “”源自希腊语：“homo”（相同）+“morphe”（形式）。它表示两个代数结构之间存在结构保持映射。FHE 是同态的 ，因为对加密数据的操作可以映射（即镜像）到对原始数据的操作上。

https://en.wikipedia.org/wiki/Homomorphism

范畴论中的同态通常用交换图来表示，通过交换运算顺序，可以从一个点到达另一个点。在下面的 FHE 图中，你可以通过两种不同的方式从 (a, b) 到达 E(a*b)。

https://en.wikipedia.org/wiki/Category_theory

让我们看一个具有客户端/服务器视角和 f(x) 函数的等效图。

FHE 的一个有用的类比是傅里叶变换 ，它将信号从时域转换到频域。在频域上执行的计算等效于在时域中的计算，反之亦然。这意味着你可以在任一域中进行计算并获得相同的结果。类似地，FHE 在明文域和密文域之间运行。在明文域中进行的转换等效于在密文域中进行的转换，反之亦然。

https://en.wikipedia.org/wiki/Fourier_transform

	双向转换
傅里叶变换	时域 <--> 频域
FHE	明文域 <--> 密文域

基于格的密码学

为了实现上述转换，FHE 使用基于格的密码学 —想象一个多维点网格，向各个方向无限延伸。

https://www.esat.kuleuven.be/cosic/blog/introduction-to-lattices/

基于格的密码学的核心问题是一些被认为极难解决的问题——即使对于量子计算机来说也是如此。其中两个最著名的例子是[1] ::

最短向量问题（SVP）： 寻找格点之间的最短路径
最近向量问题（CVP）： 找到距离任何给定点最近的格点
在二维空间中，这些看起来微不足道。但增加一百万个维度呢？那就变得极其困难，以至于人们认为即使是量子计算机也无法有效破解它们。这使得 FHE 本质上具有抗量子性。这对于未来可能的量子计算来说，是一个非常重要的特性。
https://en.wikipedia.org/wiki/Post-quantum_cryptography#Lattice-based_cryptography

额外奖励：格操作高度可并行化，这意味着其可以受益于现代 GPU 和专门的硬件加速。

带错误学习（LWE）

基于格的 FHE 方案依赖于带错误学习 (LWE) 或 Ring-LWE 问题。高层次看，LWE 是这样的：

https://en.wikipedia.org/wiki/Learning_with_errors
https://en.wikipedia.org/wiki/Ring_learning_with_errors

A > 已知矩阵

s > 私钥

e -> 随机小噪声

计算 b = A*s + e （即 b 是一个带噪声的线性组合）

生成公钥= (A, b)

困难问题： 给定公钥 (A, b) ，找到私钥 s

注意， A*s 是线性的，因此在视觉上形成一个格。换句话说， A*s 位于一个格点上。噪声 e 的加入使得得到的 A*s + e = b 偏离格点（注意，噪声是从一个窄的随机分布中采样的，因此 b 不会偏离格点太多以至于更接近另一个格点）。

因此，问题就变成了：如果攻击者想要从公钥 (A, b) 中找到私钥 s ，他需要解决寻找最近格点的问题，也就是最近向量问题 (CVP)。最近向量问题被认为是 NP 难问题，甚至是量子抗性的。。

总而言之，加密之所以有效是因为噪声的存在。而加密之所以安全，是因为解码带有噪声的格点非常困难。

噪声管理和引导

虽然噪声是这里的诀窍，但它在加法和乘法运算中也会导致以下问题。在同态加法中，每个密文的噪声也会相互相加，而在乘法中，它们会相乘。这会导致：

加法 --> 噪声线性增长（可控）
乘法——>噪声成倍增长（难以控制）

如果噪音太大，解密就会失败——你得到的是垃圾而不是结果。

由于乘法噪声增长难以控制， Craig Gentry 2009 之前的基于噪声的同态加密方案都只允许有限次数的乘法（因此不是图灵完备的）。因此，它们被称为 “Somewhat 同态加密”。。

https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf
https://digitalprivacy.ieee.org/publications/topics/types-of-homomorphic-encryption/

Craig Gentry 于 2009 年发明了第一个允许无限次加法和乘法相结合的同态加密方案。因此它是图灵完备的，因此被称为全同态加密。需要注意的是，任何类型的计算都可以表示为加法和乘法。实际上，所有计算在 CPU/GPU 层面上都简化为加法和乘法。

使 FHE 发挥作用的关键在于一种名为“引导（bootstrapping）”的方法。引导方法可以在噪声过大时降低噪声。这样，无论执行多少次乘法，它都能保证噪声不会干扰解密。

引导算法的工作方式非常巧妙。它之所以被称为“引导”，可能是因为它会在另一个公钥下“刷新”密文。它巧妙地将密文从一个公钥切换到另一个公钥，如下所示：

取原始公钥 pk_orig
取原来在 pk_orig 下加密的密文 ctx
生成一个全新的密钥对 pk_new , sk_new
用 pk_new 加密 pk_orig ，得到 pk_bootstrap （ 没错！用另一个密钥加密密钥。有创意！ ）
将密文 ctx 用pk_new 加密，得到 ctx_new
使用 sk_new 对 ctx_new 进行（同态）解密操作，得到 ctx_bootstrap

需要注意的是，FHE 的解密过程本身就是一个计算过程。因此它也可以用于同态计算！

新的 ctx_bootstrap 是另一个新的密文，其噪声被重置。需要注意的是，在解密计算过程中，由于进行了加法和乘法运算，它会产生一些固定的噪声。但这些噪声是有界的。

另外需要注意的是，引导是现代 FHE 方案的性能瓶颈。尽管新算法每年都在改进其计算开销。

关于这一点还有很多细节。我列出了一些 FHE Bootstrapping 正在使用的资源，尽管它们也没有涵盖所有内容。你需要阅读 FHE 参考库。其他关于引导的主题相当复杂，据我所知，它是 FHE 算法创新的焦点。至少从概念上理解它非常重要，因为它是 FHE 速度慢的根源，也是 FHE 有效的原因。

https://bozmen.io/dead
https://people.csail.mit.edu/vinodv/FHE/FHE-refs.html

关于 FHE，你需要了解的其他主题是重线性化和模数切换。 我在这里只通过直觉来解释它们。如果想更深入地了解数学，我推荐 Vitalik 的文章作为开胃菜。

https://vitalik.eth.limo/general/2020/07/20/homomorphic.html

重线性化

密文与密钥呈线性关系 -> a + b⋅s

乘法之后，结果变为密钥的二次关系。为说明这点：

我们将以下密文相乘：

ct1 = (a1, b1) ，其解密形式为 a1 + b1*s
ct2 = (a2, b2) ，其解密形式为 a2 + b2*s

相乘后：

ct_mul = (a₁a₂, a₁b₂ + a₂b₁, b₁b₂) ，其解密形式为 a₁a₂ + (a₁b₂ + a₂b₁)·s + b₁b₂·s²
注意 s² 项，它使密钥中的 ct_mul 成为二次。

重线性化使用称为“重线性化密钥”的附加公钥材料来消除高阶项。该过程如下：

取二次项 b₁b₂·s²
使用重线性化密钥将其“转换”回线性项
生成一个新的线性密文 (c₀', c₁') ，解密后为相同的值

模数切换

它用于控制噪声增长。这是一种通过降低密文模数来减少噪声的技巧。

我也与 ChatGPT 进行了几次对话，以便更好地了解 FHE 的一些数学细节，并在这里写下了我的所学。
https://bozmen.io/fhe-math-chats

同态加密方案的分类

同态加密方案是什么意思？

同态加密方案是一种密码构造，它定义如何执行加密、解密和同态运算（例如 BGV、CKKS、TFHE）。

同态加密方案根据其支持的操作类型和数量进行分类。

部分同态加密

仅支持一种运算（例如，Paillier 中的加法、RSA 中的乘法）。

（下面我将构建一个玩具 Pailler 示例，其代码简短且直观）

Somewhat同态加密

支持加法和乘法，但允许的乘法次数有限。

（我在上一节中解释了噪声增长如何限制可能的乘法次数）

全同态加密

支持无限次加法和乘法。图灵完备。通过引导定期降低噪声来控制噪声。

一个玩具示例

真正理解计算概念的最佳方法之一是以极简方式从头开始构建它。

https://bozmen.io/build-from-scratch
https://bozmen.io/minimal

就本文而言，构建一个全同态加密方案将会非常冗长。因此，我们将使用 Paillier 同态加密进行描述。它更简洁，更容易获得直观的理解。Paillier 是部分同态，这意味着它不支持所有操作（因此不是全同态）。它只支持加法（因此是加法同态）。我们将遵循一个典型的同态加密流程：

https://en.wikipedia.org/wiki/Paillier_cryptosystem

密钥生成 （公钥+私钥）
数据加密（使用公钥）
计算（同态运算）
结果解密（使用私钥）

import sympy, random

def generate_keypair(bit_length=512):
    p = sympy.nextprime(random.getrandbits(bit_length))
    q = sympy.nextprime(random.getrandbits(bit_length))
    n = p * q
    g = n + 1
    lambda_ = (p - 1) * (q - 1)
    mu = sympy.mod_inverse(lambda_, n)
    return (n, g), (lambda_, mu)

def encrypt(m, public_key):
    n, g = public_key
    r = random.randint(1, n - 1)
    return (pow(g, m, n**2) * pow(r, n, n**2)) % (n**2)

def decrypt(c, private_key, public_key):
    lambda_, mu = private_key
    n, _ = public_key
    l = (pow(c, lambda_, n**2) - 1) // n
    return (l * mu) % n

def homomorphic_sum(a, b, public_key):
    return (a * b) % (public_key[0]**2)


public_key, private_key = generate_keypair(128)

enc1 = encrypt(5, public_key)
print(enc1) # 75042696080311881003721105285833023546234037256871189406054603593273414107194675808782154359890875636008219678257354647151456750847402457204123856890

enc2 = encrypt(3, public_key)
print(enc2) # 269297253929306291153284608946414491483346738328838888044406160105950588673820650688249910373352597049965491330298818622410901670587359945691000319758

enc_sum = homomorphic_sum(enc1, enc2, public_key)
print(enc_sum) # 232817745404365921249916946617154013580946738803385878188677616867767489473531493655408124901849935882016399498283109322848069064027287561237823608127

dec_sum = decrypt(enc_sum, private_key, public_key)
print(dec_sum) # 8

这是 colab 笔记本链接供你自行运行和体验。 我强烈推荐。这将提供宝贵的直觉。 注意，由于加密过程是非确定性的（请注意 random 方法），每次运行时密文都会有所不同。以上注释的打印输出来自单次运行，用于展示在 Paillier 算法下密文的样子。

https://colab.research.google.com/drive/1dX62nYT4uXF-Yc72omV5oNZIGNpNGlft?usp=sharing

如果我们要构建一个全同态加密，可以使用类似的 API，包含 generate_keypair 、 encrypt 、 decrypt 和 homomorphic_sum ，并添加 homomorphic_multiply 。但代码会更长。有关此类代码，请参阅 Vitalik 的 homomorphic_encryption.py。和 matrix_fhe.py 。还可以阅读他的精彩深度探讨。

https://github.com/vbuterin/research/blob/master/tensor_fhe/homomorphic_encryption.py
https://github.com/vbuterin/research/blob/master/matrix_fhe/matrix_fhe.py
https://vitalik.eth.limo/general/2020/07/20/homomorphic.htm

FHE 的摩尔定律：每年速度提高 8 倍

四代：

1978 年（史前史）： Rivest、Adleman、Dertouzos 设想了 FHE，并将其命名为“隐私同态”
2009 年（第一代）： Gentry 于 2009 年发表的博士论文构建了第一个 FHE 方案
2011 年（第一代）： 首次实现 FHE——引导每位耗时 30 分钟 [2]
2011-2012（第二代）： BGV/BFV 方案，基于格，仍然很慢。
2013+（第 3 代）： 以毫秒为单位实现更快的引导。
2017 年（第四代）： CKKS 用于近似浮点数，支持 ML/AI。

更多信息，请参阅 FHE 历史。

https://bozmen.io/fhe-history

Since 2011, FHE performance has improved 8× every year—from 10¹⁰× overhead down to ~10³× ~10^4× today.
自 2011 年以来，FHE 性能每年提高 8 倍——从 10¹⁰× 开销降低到今天的 ~10³× ~10^4×。

最近的突破正在加速这一进程：

2025 年 6 月的论文中，Dan Boneh 和 Jaehyung Kim 声称乘法吞吐量提高了 1,000 倍，延迟降低了 10 倍（对于大整数运算）

https://eprint.iacr.org/2025/346.pdf

硬件加速可以再增加 10³ 倍的加速

https://www.youtube.com/watch?v=V3FcM1B4mcg&list=PLnbmMskCVh1cCnWbmgxI0BM0UD2JHH9fz&index=14

除了算法改进之外，硬件也在不断改进，从而进一步增强了效果。更多信息请参阅 FHE 硬件。

https://bozmen.io/fhe-hardware

以下是 Vitalik 对进展速度的看法：

我们很快就能实现同态加密在隐私保护计算中的诸多应用，并使其实际可用。 此外，基于格的密码学在同态加密中的更高级应用研究也正在快速推进。因此，在这个领域，目前已经有一些成果可以实现，但我们满怀希望地期待未来十年会有更多成果成为现实。

计算的未来是加密的

让我们把这些点连接起来。

数据泄露几乎是不可避免的。

保护数据的唯一方法是始终在服务器上对数据进行加密，而服务器不具备解密的能力。

这意味着即使对数据进行计算也应该加密。

FHE 支持对加密数据进行计算。

由于计算开销较大，FHE 对于许多应用来说尚不实用。但对于某些应用来说，它还是可行的。

FHE 算法每年都在改进，每年提升 8 倍。其结果是，现实世界中可行的应用正在不断增加。FHE 正在消耗计算资源，但规模仍然很小。

如果这种趋势继续下去，FHE 将征服更多的现实世界用例，以至于大多数云计算都可以用 FHE 完成。

用户的隐私意识不断增强，隐私法规也日益严格。

如果 FHE 是一个可行的选择，那么人们和机构就会要求它。

如果人们对此有要求，并且趋势使得 FHE 对于大多数计算而言都是实用的，那么大多数互联网计算都将在 FHE 上进行。

互联网计算的未来必将是加密的。这不是“是否”的问题，而是“何时”的问题。

HTTPS by default --> 2010s
FHE by default --> ?

[1] 密码系统依赖于困难问题 ——那些没有已知多项式时间解（NP-hard）的问题。为了发挥作用，这些问题必须易于单向计算，但难以逆向计算。这类问题被称为单向函数，所有密码学都依赖于它们。一个典型的例子是大素数的乘法 —前进很容易，后退却很难。

[2] 引导开销导致效率低下，这是加密数据计算的一部分。引导每位需要 30 分钟。https://x.com/i/grok/share/jhND3efXK7or24rdkFgcxpbZz

【Eurocrypt 2025】一種對高精度運算的全同態加密（FHE）新方案

iOS 18 中的同态加密

备战后量子：格密码学初学者指南

阅读原文