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进行可扩展的私有搜索论文的高级概述。
不幸的是，苹果的同态加密实现并不像我们上面讨论的那样纯粹。苹果必须在隐私和性能之间取得平衡，而这两者是相互矛盾的（同态加密程序的运行速度比其等效程序慢很多个数量级）。
在讨论苹果的同态加密之前，我们先退一步。这种搜索的非私有实现可能如下所示：
- 在初始化时，服务器将其文档分成相似的文档簇。
- 客户端选择与查询最匹配的簇。
- 客户端将其向量发送到服务器。
- 服务器返回簇中每个文档的相似度分数。
- 客户端选择最佳条目。
- 客户端请求最佳条目的元数据。
这种实现存在以下安全漏洞：
- 服务器可以读取向量。嵌入向量可能非常具有揭示性。
- 客户端揭示了最近的簇。这是一个较小的问题，但它可以用来推断查询。例如，嵌入匹配“狗”的查询可能位于“动物”簇中。
- 为了获取相关元数据，客户端将最近条目的索引发送到服务器。这也会导致隐私泄露！
隐藏嵌入向量：回到同态加密
嵌入向量是目前泄露的最敏感信息。
