PenPen的注释：本文旨在为非数学背景但具备一定计算机知识的读者提供易于理解的解释。文章是在Jeff Johnson最近发表的“Apple Photos在iOS 18和macOS 15上向服务器发送数据”引发的争议之后撰写的。关于这项技术的工作原理，存在很多困惑和好奇，同时也有对苹果发布的密集研究论文的批评。本文的目标是将这些研究提炼成更易于理解的内容，以便您能对自己的数据做出更明智的决定。“苹果从未明确说明发生了什么”，但也许我可以。
假设你是苹果公司。你希望让照片应用中的搜索功能像魔法一样好用，用户能轻松找到所有“狗”的照片。你设计了一种方法，将图像的概念用数字表示，这样你就能找到图像在意义上的相似度。然后，你创建一个已知图像及其数字表示的数据库（“这个数字代表汽车”），并找到最接近的匹配项。为了保护隐私，你将这个数据库放在用户的设备上。
这一切听起来很酷，但其实是一个已经解决的问题。这种“数字表示”被称为嵌入向量。向量是一个高维空间中的一系列坐标。一个维度可能衡量某物有多“像狗”，另一个维度可能衡量某物有多“像野生动物”。既像狗又像野生动物？那可能是狼。我们可以使用余弦相似度等算法来比较距离。我们非常擅长将文本转化为向量，将图像转化为向量也差不多。
但后来，你的数据库变大了。用户不再想要所有狗的照片，他们想要金毛猎犬的照片。你无法再将这个数据库放在设备上。你开始考虑将这个数据库存储在服务器上，并将设备上计算的数字表示发送到服务器。这应该没问题：向量化是一个有损操作。但这样一来，你就会知道Amy拍了很多金毛猎犬的照片，这可能会引发政治灾难。
同态加密的承诺
我们在加密方面也做得不错。加密使我们能够对一系列比特进行混淆，使得没有密钥的观察者无法读取原始值。当应用正确的密钥时，原始值会被恢复。
为了使加密有效，输入的微小变化必须导致输出以不可预测的方式变化。如果不是这样，攻击者可以逐渐调整输入，目标是创建越来越相似的加密输出。当输出匹配时，攻击者就知道原始值。
不幸的是，我们所知的加密对我们没什么用。如果我们在发送向量之前对其进行加密，苹果的服务器将无法读取向量的值。如果服务器无法读取向量的值，那么它们就不知道哪个数据库条目最接近我们的向量（如果它们知道，那我们的加密就失败了）。服务器无法告诉我们它们不知道的事情。因此，这一切都是徒劳的。
这个猜想听起来很具体，但其中一个陈述是错误的。如果我告诉你，服务器可以告诉我们它们不知道的事情呢？这就是同态加密的用武之地。
其前提如下：客户端向服务器发送一个加密值。服务器无法读取该值。服务器可以修改该值，但它无法知道修改后的新值是什么。本质上，服务器是在“蒙眼”操作。
以加法为例。你有一个未知值P，你给它加上已知值Q。你可以推断出结果值等于P+Q，但你不知道P+Q是什么，也不知道P是什么。客户端使用其密钥解密该值，得到P+Q的结果。由于客户端也知道P的值，它可以反推出Q。
在同态加密方案中，有两个主要操作：
- 同态加法：
E(P) + E(Q) = E(P + Q) - 同态乘法：
E(P) * E(Q) = E(P * Q)
通常只能在明文上执行的操作，现在可以在密文上执行了！
同态加密涉及许多复杂性，例如噪声的积累。支持真正任意数量的操作非常困难，但如果你能支持任意深度的加法和乘法，你就拥有了完全同态加密。背后的数学非常复杂，本文无法详细讨论。目前有一些关于创建同态加密编译器的兴趣，我们的代码示例将使用Rust，基于Sunscreen编译器进行简化。Concrete可能是一个更强大的选择，但学习曲线更高。
同态程序长什么样？
下面是一个简单的同态程序，用于将两个加密值相乘：
#[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);
// 客户端使用其私钥解密值。result = 24
let result = runtime.decrypt(res, &private_key)?;
}
// 服务器不会接收私钥，因此无法解密结果或client_value
fn server(public_key: PublicKey, client_value: Cipher<Signed>) -> Cipher<Signed> {
// 服务器使用用户的公钥加密一个新值
let server_value = runtime.encrypt(Signed::from(3), &public_key)?;
// 服务器使用client_value和server_value运行'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]
#[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)，而不会泄露任何信息。然而，你可能需要在执行成本上付出代价。
余弦相似度更难，因为它涉及除法和范数操作，但你可以在同态程序中对向量进行归一化，然后执行简单的标量积。预处理确实是关键。
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
PenPen的注释：本节提供了使用Wally进行可扩展的私有搜索论文的高级概述。
不幸的是，苹果的同态加密实现并不像我们上面讨论的那样纯粹。苹果必须在隐私和性能之间取得平衡，而这两者是相互矛盾的（同态加密程序的运行速度比其等效程序慢很多个数量级）。
在讨论苹果的同态加密之前，我们先退一步。这种搜索的非私有实现可能如下所示：
- 在初始化时，服务器将其文档分成相似的文档簇。
- 客户端选择与查询最匹配的簇。
- 客户端将其向量发送到服务器。
- 服务器返回簇中每个文档的相似度分数。
- 客户端选择最佳条目。
- 客户端请求最佳条目的元数据。
这种实现存在以下安全漏洞：
- 服务器可以读取向量。嵌入向量可能非常具有揭示性。
- 客户端揭示了最近的簇。这是一个较小的问题，但它可以用来推断查询。例如，嵌入匹配“狗”的查询可能位于“动物”簇中。
- 为了获取相关元数据，客户端将最近条目的索引发送到服务器。这也会导致隐私泄露！
隐藏嵌入向量：回到同态加密
嵌入向量是目前泄露的最敏感信息。
完全同态加密对苹果来说太慢了，因此他们使用了部分同态加密。部分同态加密支持加法和乘法逻辑，但只能到一定深度。每个数学操作都会增加深度，因为它会增加噪声量。选择的参数在安全性和噪声预算之间取得了平衡。显然，理想情况下不应在这些约束下工作。不幸的是，完全同态加密目前还不够快。
以下是实现的操作，其中ct表示E(v)，v是一个向量：
| SHE操作 | 结果 | 时间（毫秒） | 噪声（比特） |
|---|---|---|---|
| PtCtAdd(ct, v’) | E(v + v’) | 0.004 | 0.5 |
| CtCtAdd(ct, ct’) | E(v + v’) | 0.004 | 0.5 |
| PtCtMult(ct, v’) | E(v ⊙ v’) | 0.02 | 20 |
| CtCtMult(ct, ct’) | E(v ⊙ v’) | 2.5 | 26 |
| CtRotate(ct, r) for r ∈[0, n/2) | 0.5 | 0.5 |
在上述伪代码中，查询是一个由许多单独加密值组成的向量。在苹果的实现中，似乎整个向量被压缩成一个单一值：
总体而言，在我们的实现中，客户端查询和服务器响应分别是大小为226kB和53kB的单个RLWE密文（前者带有评估密钥）。
他们对相似性数学的优化在论文的后半部分有所描述，但老实说，我并没有完全理解。
隐藏最近的簇
在这三个泄露中，簇是最不重要的。如果嵌入向量泄露了，照片内容的很多信息都会被揭示。狗的品种、草的颜色、氛围。如果最佳匹配泄露了，服务器知道我们可能有一张金毛猎犬的照片。如果簇泄露了……好吧，它是某种动物。苹果选择为了性能牺牲一些隐私，采用了一种称为差分隐私的技术。
苹果使用由第三方运营的ohttp匿名网络来代理对Wally的请求。这意味着无法知道特定请求来自哪个设备——所有请求都混合在一起。此外，还采取了以下缓解措施：
- 客户端发出一些虚假查询，然后丢弃结果。
- 查询按“epoch”分组。在每个epoch内，固定数量的用户发出查询，他们的查询在epoch结束时处理。查询也会在随机时间以随机顺序发送，希望能消除时间侧信道。
Jeff Johnson正确地指出，这个方案仍然存在一些缺陷：
两个跳转，两家公司已经在合作，那么从技术上讲，中继设置中有什么可以阻止这两家公司——无论是自愿还是某个政府的秘密命令——来比较笔记，连接点呢？
隐藏元数据
元数据是我们的第三个泄露。解决方案其实很简单。与其查询一个簇的元数据以获取一个索引，不如让簇返回该簇中存储的所有索引的元数据。
PenPen的注释：这似乎意味着客户端会获取大量数据。我不怪你质疑服务器是否真的需要。问题是，用于比较的存储向量是最大的存储用户。每个向量可能很容易达到几千字节。论文讨论了一个包含3500万个条目的数据库，分布在8500个簇中。
如果元数据太大，可以使用本文中详细描述的技术进行私有信息检索，而不是我们迄今为止关注的私有最近邻搜索。
讨论
在继续之前，我想明确一点，我只是一个业余爱好者，而不是这方面的专家。我第一次听说同态加密是在阅读Jeff Johnson最近的“Apple Photos在iOS 18和macOS 15上向服务器发送数据”以及后续 文章时，前面的内容是我大约10个小时的研究成果。我不质疑他写的任何内容。
理解隐私的一种自然方式是与保密同义。根据这种解释，如果我的数据是私有的，那么除了我之外，没有人可以读取我的数据[…]隐私权也可以意味着私有所有权的权利。[…]在增强视觉搜索中，苹果似乎只关注隐私作为保密的理解，而忽略了隐私作为所有权的理解。
我自己在花时间整理了一大堆零散信息后，决定我喜欢这个功能，并将保持启用状态。话虽如此，技术理解并不能替代同意，苹果本应在启用功能时请求同意并提供适当的解释。
苹果曾经说过：“发生在你iPhone上的事情，就留在你的iPhone上。”显然，这并不完全正确，而且在苹果开始使用同态加密之前，情况就已经不是这样了。
关于私有云计算的简短讨论
毫无疑问，他们正在付出努力。比其他任何科技公司都要多。但他们仍然做出了一些牺牲，比如当他们决定将最复杂的AI工作负载卸载到服务器上时，这个项目被称为私有云计算。这包括在一个隔离的、无权限和无状态的环境中运行计算，并允许安全研究人员阅读源代码。
这一切听起来不错，但我怎么确定服务器运行的是他们所说的代码？在同态加密中，这种信任是不需要的，因为敌对服务器没有什么可窃取的，但LLM无法在这种上下文中运行。如果我们期望知道私有云计算确实是私有的，我们必须能够通过密码学验证来知道我们不控制的服务器正在运行我们信任的代码，但当服务器可以通过网络发送任何数据时，我们怎么知道这一点？服务器说它正在运行提交f52fbd并不意味着什么，它可以说任何它想说的话。这是一个感觉不可能解决的问题，苹果也认识到了这个问题：
没有通用的机制允许研究人员验证这些软件映像是否与生产环境中实际运行的软件映像匹配。
他们似乎声称已经找到了解决方案。未来，我计划调查这一说法。但无论如何，回到手头的任务。同态加密是私有的吗？某些东西正在离开你的设备……
但是，真正离开你设备的信息是什么？没有“相信我”的元素。除非在数学或苹果的实现中发现一些问题，否则云首次能够充当设备和数据的某种扩展，这是一个非常令人兴奋的前景。苹果已经能够在不知道照片内容的情况下对照片进行分类。这有多酷。
如果这个项目在智能手机和社交媒体商品化之前出现，我可能会写一些关于云使用越来越不谨慎的滑坡效应。但我们已经生活在一个所有数据都在云端而不是我们手中的世界。这个项目代表了朝着正确方向迈出的一小步，我无法忽视它的酷炫之处。我只是希望苹果能更坦率一些。
我们生活在一个令人惊叹的时代。
