iOS 18 中的同态加密
原文：https://boehs.org/node/homomorphic-encryption
作者：Evan Boehs
译者：Kurt Pan
你是 Apple。你想要在「照片」App 中让搜寻变得像魔法一样，让使用者能够轻松找到所有「狗」的照片。为此，你想出了一种方法，能够用数值来表示一张图片所包含的概念，让你可以判断不同图片在意义上有多接近。接着，你建立了一个包含已知图像及其数值表示（「这个数字代表车」）的资料库，并找出最相近的匹配。为了保护隐私，你将这个资料库放在手机上。
这一切听起来虽然很酷，但其实已经是一个解决了的问题。这种「数值表示」称作嵌入向量（embedding vector）。向量是一组在高维空间中的座标；其中一个维度可能用来衡量「像狗」的程度，另一个维度可能衡量「野生」的程度。既像狗又像野生？那就变成狼了。我们可以使用像馀弦相似度这样的演算法来比较不同向量之间的距离。我们已经非常擅长将文字转换成向量，转换图片也只稍微差一些。
但接着，你的资料库变得越来越大。你的使用者不只想找所有的狗，还想找黄金猎犬。你再也无法把整个资料库都放在装置上。你可能想把这个资料库放到伺服器上，并把在装置上计算出来的数值表示传送过去。照理说，这样应该没问题：向量化是一种有损操作。但这样一来，你就会知道 Amy 拍了很多黄金猎犬的照片，而这会在政治层面上带来灾难。
同态加密的愿景
我们相当擅长的另一件事就是加密。加密能让我们将一串位元重新排列，使得观察者（没有密钥的人）无法读取原始值；一旦使用正确的密钥，原始值就能被还原。
为了让加密正常运作，对输入的细微改动必须以不可预测的方式影响输出。如果不是这样，攻击者就能逐步调整输入，以产生与目标加密输出越来越相似的结果。一旦输出完全相符，攻击者就能知道原始值。
不幸的是，以我们所熟知的方式进行加密，对我们的需求帮助不大。如果我们在传送前把向量加密，Apple 的伺服器就无法得知该向量的数值。如果伺服器不知道向量的数值，也就不知道哪一笔资料库内容与这个向量最相近（若它知道，表示加密失效）。伺服器无法告诉我们它不知道的事情。因此，这整套做法就失去了意义。
这个推论听起来很合理，但其中有个前提是错的。如果我告诉你：伺服器能告诉我们「它不知道」的事情呢？引入「同态加密」。
同态加密的前提如下：用户端将一个加密后的数值传送给伺服器。伺服器无法读取该数值，但它可以对这个数值进行运算，并且不知道经过运算后的新数值。在本质上，伺服器就像是「被蒙住眼睛」来做操作。
举例来说，对于加法：你拥有未知的数值 ，并把已知数值 加到 上。你可以推断结果是 ，但你不知道 是多少，也不知道 是多少。用户端再用自己的密钥将结果解密，得到 。由于用户端也知道 的值，它就能逆向计算出 。
同态方案中有两个主要操作：
同态加法 ： E(P) + E(Q) = E(P + Q)同态乘法 ： E(P) * E(Q) = E(P * Q)
通常针对明文的操作现在同样可以在密文上执行！
同态加密存在许多复杂性，例如噪声的累积。真正支持任意数量的操作非常困难，但如果能够支持任意深度的两个门，则实现了全同态加密。这背后的实际数学非常复杂，遗憾的是，这超出了本文的讨论范围。目前，人们对创建用于同态加密的编译器颇感兴趣，我们的代码示例将使用 Rust 编写，为简单起见，会大致基于 Sunscreen 的编译器。Concrete 可能是一个更健壮的选择，但学习曲线更高。
https://www.jeremykun.com/2024/05/04/fhe-overview/#basic-operations-and-dealing-with-noise https://docs.sunscreen.tech/fhe/intro/intro.html https://docs.zama.ai/concrete https://medium.com/optalysys/fully-homomorphic-encryption-and-the-game-of-life-d7c37d74bbaf
对密码学家的公开呼吁：
世界需要用简单的英语来解释同态加密（以及后量子加密！）背后的数学原理。
我理解一点最短向量问题和由此产生的不安全的 GGH 加密方案。
我认为我理解了 BFV 的基本原理是“环带误差学习 （RLWE）”，其中客户端生成多个多项式，选取
w的某个值，并计算每个方程的w值对应的答案。公钥是一个包含w私有值和公共解的系统。这些解存在一些随机误差。RLWE 的解可以用来解决格中的最短向量问题。但这一切都有点模糊。我正在寻找一些 3blue1brown 风格的、直观的 BFV 端到端工作原理的解释，但我还没找到。也许有？如果有，请告诉我。如果没有，也许你想写一个 ;)
同态程序是什么样的？
下面是一个简单的同态程序，它将两个加密值相乘：
#[fhe_program]
fn multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
a * b
}
fn main() {
let (public_key, private_key) = runtime.generate_keys()?;
// 客户端使用公钥加密数值。这个加密值只能用私钥解密。这被称为非对称加密。
let client_value = runtime.encrypt(Signed::from(8), &public_key)?;
// 私钥不会发送给伺服器，所以伺服器无法解密这个'8'
let res = server(public_key, client_value);
// 客户端使用私钥解密数值。结果 = 24
let result = runtime.decrypt(res, &private_key)?;
}
// 伺服器不会收到私钥，因此无法解密结果或客户端数值
fn server(public_key: PublicKey, client_value: Cipher<Signed>) -> Cipher<Signed> {
// 伺服器使用用户的公钥加密一个新数值
let server_value = runtime.encrypt(Signed::from(3), &public_key)?;
// 伺服器使用客户端数值和伺服器数值运行'multiply'函数，并返回响应
runtime.run(multiply, vec![client_value, server_value], &public_key)?
}
这个例子很简单。当你需要执行一系列操作时，情况会变得更加复杂，例如隐私信息检索可能需要的操作，因为你需要将查询组织为一些基本的数学运算。
更具体地说，同态加密程序本质上往往只支持 add 和 mul 指令。比较和模运算非常困难。因此，你需要以非常特殊的方式组织查询。
例如，要从数据库中检索一个值，查询可以组织一个长度为 n 的向量，其中 n 是数据库的大小。查询是一个由 0 组成的向量，其中 1 表示要检索的值的索引。然后，与数据库进行点积运算，除了要检索的值之外的所有值都将被清零：
// [0, 0, 1, 0, 0] * [10, 20, 30, 40, 50] = [0, 0, 30, 0, 0]
// => (0 + 0 + 30 + 0 + 0) = 30
#[fhe_program]
fn lookup(query: [Cipher<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
let mut sum = query[0] * database[0];
for i in 1..DATABASE_SIZE {
sum = sum + query[i] * database[i]
}
sum
}
你可能认为这听起来计算成本很高。你说得对。就带宽而言，可以减少输入的长度。例如，如果将数据库结构化为二维，查询可以分别对行和列进行编码，这样查询的大小就为 2sqrt(n) ，并且不会出现任何泄漏。但是可能需要付出执行成本的开销。
平方根查找
#[fhe_program]
fn lookup(
col_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
row_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher<Signed> {
let mut col = [col_query[0]; SQRT_DATABASE_SIZE];
// extract desired column
for i in 0..SQRT_DATABASE_SIZE {
for j in 0..SQRT_DATABASE_SIZE {
if j == 0 {
col[i] = database[i][j] * col_query[j];
} else {
col[i] = col[i] + database[i][j] * col_query[j];
}
}
}
let mut sum = col[0] * row_query[0];
for i in 1..SQRT_DATABASE_SIZE {
sum = sum + col[i] * row_query[i];
}
sum
}
注：使用 sunscreen，分支不能依赖于函数参数，并且不支持与这些参数的比较。甚至
==也不支持。这是因为在底层，你所做的一切都只是带有多项式的代数运算。但是，你可以手动实现布尔逻辑。Jeremy Kun 写道：“有了这种能力，你可以逐位加密你的数据，将你的程序表示为布尔电路 -XOR门是加法，AND门是乘法 - 然后模拟该电路。由于XOR和AND构成了布尔逻辑的通用基础，因此你始终可以通过这种方式分解电路”。此外，对于分支，你可能会想知道分支是否会泄露信息。 是的 ，它们可以。因此，每次都必须执行最坏的情况。必须执行所有if分支，并且所有循环都必须达到其上限（这也意味着上限必须是静态已知的）
余弦相似度更难，因为它的定义包含除法和范数运算，但你可以先对向量进行归一化，然后在同态程序中进行简单的标量积运算。预处理才是关键所在。
let norm = (vector1.iter().map(|x| x * x).sum::<f64>()).sqrt();
let normalized_vector: Vec<Signed> = vector1.iter().map(|x| Signed::from(x / norm1)).collect();
我们没有办法直接返回最佳匹配。最多只能返回数据库中每个条目的分数，然后客户端可以解密这些分数并找到最佳匹配：
对于每个查询，伺服器响应包含集群中的所有条目。[…] 在 Wally 中，我们利用基于格的部分同态加密 (SHE) 来减少响应开销。[…] 伺服器计算加密信息与 SHE 下的集群条目之间的距离函数，并返回加密分数。这减少了响应，因为加密分数的大小明显小于条目本身。
苹果的实现：Wally
本节对 Wally 论文中的可扩展隐私搜索进行了高级概述。 https://arxiv.org/pdf/2406.06761
不幸的是，苹果对同态加密的实现并不像我们上面讨论的那样纯粹。苹果必须在隐私和性能之间取得平衡，而这两者是相互矛盾的（同态加密程序的运行速度比同类程序慢很多个数量级）。
在了解苹果对同态加密的看法之前，我们先回顾一下。此搜索的非隐私实现如下所示：
在初始化时，伺服器将其文档分成类似文档的集群 。2 客户端选择与查询最匹配的集群。 客户端将其向量发送至伺服器。 伺服器返回集群中每个文档的相似度得分。 客户挑选最佳条目。 客户端请求最佳条目索引的元数据。
这存在以下安全漏洞：
伺服器可以读取向量。嵌入可以揭示很多信息。 客户端会显示最近的聚类。这个问题不太重要，但可以用来推断查询。例如，如果一个查询的嵌入匹配项是“狗”，那么它很可能位于“动物”聚类中。 为了获取相关的元数据，客户端会将最近条目的索引发送到伺服器。这也可能造成隐私泄露！
隐藏嵌入：回到同态加密
嵌入向量是目前泄露的最敏感的信息。
完全同态加密速度太慢，苹果公司无法使用，因此他们采用了部分同态加密。全同态加密 (FHE) 支持加法和乘法逻辑，但深度有限。每次数学运算都会增加深度，但这会增加噪声量。我们已选择了一些参数来平衡安全性和噪声预算。显然，最好不要在这些限制下工作。遗憾的是，全同态加密 (FHE) 的速度还不够快。
以下是已实现的操作，其中 ct 表示 E(v) ， v 是向量：
在上面的伪代码中，查询是一个包含多个单独加密值的向量。在 Apple 的实现中，整个向量似乎被归结为一个奇异值：
总体而言，在我们的实现中，客户端查询和伺服器响应分别是大小为 226kB 和 53kB 的单个 RLWE 密文（前者带有评估密钥）
他们对相似性数学所做的优化将在论文后面描述，但我没有理解。
隐藏最近的簇
在这三种泄露方式中，聚类泄露是最不重要的。如果嵌入信息泄露，照片的大量内容都会被泄露。狗的品种、草的颜色、氛围等等。如果最佳匹配信息泄露，伺服器就知道我们很可能有一张金毛猎犬的照片。如果聚类信息泄露……嗯，它可能是某种动物。苹果为了性能选择牺牲一些隐私，选择了一种名为“差分隐私”的技术。
Apple 使用由第三方运营的 ohttp 匿名网络代理向 Wally 发送请求。这意味着无法确定特定请求来自哪个设备——所有请求都会混杂在一起。此外，Apple 还采取了以下缓解措施：
https://www.rfc-editor.org/rfc/rfc9458
客户端发出许多虚假查询，然后丢弃结果。 查询按“epoch”分组。每个 epoch 内，固定数量的用户发起查询，并在 epoch 结束时进行处理。查询也会在随机时间以随机顺序发送，以期消除时序侧信道攻击。
Jeff Johnson 正确地指出，这个方案仍然存在一些缺陷：
这两个中继站、这两家公司已经在合作，那么从技术上讲，中继设置中有什么可以阻止这两家公司聚集在一起——无论是自愿的还是在某个政府的秘密命令下——来比较意见，并将点连接起来？
隐藏元数据
元数据是我们的第三个泄漏点。解决方案其实很简单。集群不再查询某个索引的元数据，而是返回该集群中存储的所有索引的元数据。
注：客户端获取的数据量看起来相当大。我不怪你质疑伺服器是否真的有必要。问题是，用于比较的存储向量是迄今为止最大的存储空间占用者。每个向量很容易就占用数 KB 的空间。本文讨论了一个包含 3500 万个条目的数据库，分布在 8500 个集群中。
如果元数据太大，本文详述的相同技术可用于私有信息检索，而不是私有最近邻搜索，这是我们到目前为止所关注的重点。
讨论
在继续之前，我想先声明一下，我只是个业余爱好者，并非这方面的专家。我第一次接触同态加密是在阅读 Jeff Johnson 最近发表的“ Apple Photos 在 iOS 18 和 macOS 15 上实现全面支持 ”以及之后的文章，之前的研究耗费了我大约 10 个小时。我对他写的任何内容都没有异议。
https://lapcatsoftware.com/articles/2024/12/3.html https://lapcatsoftware.com/articles/2025/1/1.html
一种自然的理解是将隐私与保密性联系起来。按照这种理解，如果我的数据是私有的，那么除了我之外没有人可以读取我的数据[…] 隐私权也可以指私有权。[…] 苹果在增强型视觉搜索方面似乎只关注隐私作为保密性的理解，而忽略了隐私作为所有权的理解。
我本人也花了不少时间整理了大量零散的信息，最终决定我喜欢这个功能，并会保留它。话虽如此，技术上的理解并不能取代用户同意，苹果应该征求用户同意，并提供合理的解释。
苹果曾经说过：“在你的 iPhone 上发生的事情，就留在你的 iPhone 上。”显然，事实并非完全如此，在苹果开始使用同态加密之前，情况并非如此。
关于私有云计算的简短讨论
毫无疑问，他们正在付出努力，远超其他任何科技公司。但他们也做出了牺牲，例如，他们决定将最复杂的人工智能工作负载转移到名为“私有云计算”的项目中，并将其迁移到自己的伺服器。这意味着计算将在隔离、无需许可、无状态的环境中运行，并允许安全研究人员读取源代码。
https://security.apple.com/blog/private-cloud-compute/
这一切听起来不错，但我如何才能确定伺服器正在运行它们声称正在运行的代码呢？使用同态加密，这种信任是不必要的，因为敌对伺服器不会有任何东西可以窃取，但 LLM 无法在这种环境下运行。如果我们要知道私有云计算确实是私有的，我们必须能够通过加密验证_知道_我们无法控制的伺服器正在运行我们信任的代码，但是当伺服器可以通过网络发送任何它们想要的数据时，我们怎么知道这一点呢？伺服器说它正在运行提交 f52fbd 并不意味着什么，它可以说任何它想说的话。这是一个感觉不可能的问题，苹果也意识到了这个问题：
没有通用机制可以让研究人员验证这些软件映像是否与生产环境中实际运行的软件映像相匹配。
他们似乎声称找到了解决方案。我计划将来调查一下这个说法。不过，还是回到手头的任务吧。同态加密是私密的吗？有些东西正在离开你的设备……
但是，哪些信息真正离开了你的设备？这根本就不存在。除非在数学计算或苹果的实现方式上出现问题，否则云服务首次能够成为你设备和数据的某种延伸，这是一个非常令人兴奋的提议。苹果在对照片内容一无所知的情况下就对其进行了分类。这太酷了。
如果这个项目先出现，在智能手机和社交媒体商品化之前，我肯定会写一些关于云计算使用越来越不谨慎的滑坡效应的文章。但我们已经生活在一个所有数据都存储在云端，而不是掌握在我们手中的世界。这个项目代表着我们朝着正确方向迈出了一小步，它真的很酷，我简直无法忘记。我只是希望苹果能更坦诚一些。
我们生活在一个令人惊叹的时代。
📝 参考文献和推荐阅读
使用同态加密构建应用程序 使用 Wally 进行可扩展的私有搜索 同态加密 全同态加密的高级技术概述 Katherine E. Stange：带错误和舍入的环学习 技术永远不能取代同意
👟 脚注
你可能会好奇，如果除了一个值之外所有值都相同，这如何保证隐私呢？加密函数不一定需要确定性。这就是噪声，它是随机的 。↩︎ 使用 K 均值聚类。聚类数量越多，性能越好，但聚类数量过多则可能选错聚类 。↩︎