[博客翻译]iOS 18中的同态加密

由 发布于 同态加密隐私保护嵌入向量服务器安全数据加密
 收藏

原文地址：https://boehs.org/node/homomorphic-encryption


iOS 18中的同态加密

PenPen的笔记：本文旨在为非数学背景但具备一定计算机知识的读者提供易懂的解释。本文的写作背景是Jeff Johnson最近的文章“Apple Photos在iOS 18和macOS 15上向服务器发送数据”引发的争议。关于这项技术的工作原理，大家有很多困惑和好奇，同时也对苹果发布的密集研究报告提出了批评。本文的目标是将这些研究提炼成更易理解的内容，以便你能对自己的数据做出更明智的决定。正如“苹果从未明确说明发生了什么”所说，但也许我可以解释清楚。
假设你是苹果公司。你希望让照片应用中的搜索功能像魔法一样好用，用户能轻松找到所有“狗”的照片。你设计了一种方法，用数字来表示图像的概念，从而找到图像在语义上的相似度。然后，你创建了一个已知图像及其数字表示的数据库（“这个数字代表汽车”），并找到最接近的匹配项。为了保护隐私，你将这个数据库放在用户的设备上。
这一切听起来很酷，但其实是一个已经解决的问题。这种“数字表示”被称为嵌入向量。向量是一个高维空间中的一系列坐标。一个维度可能衡量某物有多“像狗”，另一个维度可能衡量某物有多“像野生动物”。既像狗又像野生动物？那可能是狼。我们可以使用余弦相似度等算法来比较距离。我们已经非常擅长将文本转化为向量，将图像转化为向量也做得不错。
但随着数据库的增长，用户不再想要所有狗的照片，而是想要金毛猎犬的照片。你无法再将这个数据库放在设备上。你可能会想把数据库存储在服务器上，并将设备上计算的数字表示发送到服务器。这应该没问题：向量化是一种有损操作。但这样一来，苹果就会知道Amy拍了很多金毛猎犬的照片，这可能会引发政治灾难。

同态加密的承诺

我们也很擅长加密。加密使我们能够对一系列比特进行混淆，使得没有密钥的观察者无法读取原始值。当应用正确的密钥时，原始值会被恢复。
为了使加密有效，输入的微小变化必须导致输出以不可预测的方式变化。如果不是这样，攻击者可以逐步调整输入，目标是生成越来越相似的加密输出。当输出匹配时，攻击者就知道原始值。
不幸的是，我们所知的加密对我们没什么用。如果我们在发送向量之前对其进行加密，苹果的服务器就无法读取向量的值。如果服务器无法读取向量的值，那么它们就不知道哪个数据库条目最接近我们的向量（如果它们确实知道，那么我们的加密就失败了）。服务器无法告诉我们它们不知道的事情。因此，这一切都是徒劳的。
这个猜想听起来很具体，但其中一个陈述是错误的。如果我告诉你，服务器可以告诉我们它们不知道的事情呢？这就是同态加密的用武之地。
前提如下：客户端向服务器发送一个加密值。服务器无法读取该值。服务器可以修改该值，但它无法知道修改后的新值。本质上，服务器是在“蒙着眼睛”操作。
一张戴着盲罩的女性使用旧电脑的库存图片
苹果服务器机房的真实照片
以加法为例。你有一个未知值P，并向其添加已知值Q。你可以推断出结果值等于P+Q，但你不知道P+Q是什么，也不知道P是什么。客户端使用其密钥解密该值，得到P+Q的结果。由于客户端也知道P的值，它可以反推出Q。
客户端服务器生成明文值P将P加密为密文E(P)发送E(P)盲目修改E(P)：E(P)+E(Q)=E(P+Q)发送修改后的密文E(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);
  // 客户端使用其私钥解密值。结果为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组成的向量，在你想要检索的值的索引处有一个11。然后，你与数据库进行点积，除了你想要检索的值外，所有其他值都会被清零：

// [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)，而不会泄露任何信息。然而，你可能需要在执行成本上付出代价。
sqrt查找```
#[fhe_program]
fn lookup(
col_query: [Cipher; SQRT_DATABASE_SIZE],
row_query: [Cipher; SQRT_DATABASE_SIZE],
database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher {
let mut col = [col_query[0]; SQRT_DATABASE_SIZE];
// 提取所需的列
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
}

> [PenPen](https://boehs.org/node/<./penpen>)的笔记：在使用Sunscreen时，分支不能依赖于函数参数，也不支持与这些参数的比较。甚至连`==`都不支持。这是因为在底层，你所做的一切都只是多项式的代数运算。手动操作时，你**可以**实现布尔逻辑。Jeremy Kun写道：“有了这种能力，你可以逐位加密数据，将程序表示为布尔电路——`XOR`门是加法，`AND`门是乘法——并模拟电路。由于`XOR`和`AND`构成了布尔逻辑的通用基础，你总是可以以这种方式分解电路。”此外，关于分支，你可能会想知道分支是否会泄露信息。[是的](https://boehs.org/node/<https:/www.jeremykun.com/2024/05/04/fhe-overview/#the-highest-level-view>)。它们可以。因此，每次都必须执行最坏的情况。所有`if`分支都必须执行，所有循环都必须达到其上限（这也意味着上限必须是静态已知的）。
余弦相似度更难，因为它涉及到除法和范数运算，但你可以在同态加密程序中对向量进行归一化，然后进行简单的标量积。预处理确实是关键。

let norm = (vector1.iter().map(|x| x * x).sum::()).sqrt();
let normalized_vector: Vec = vector1.iter().map(|x| Signed::from(x / norm1)).collect();

我们没有办法简单地返回最佳匹配。最多，我们可以返回数据库中每个条目的分数，然后客户端可以解密这些分数并找到最佳匹配：
> 对于每个查询，服务器响应包含集群中的所有条目。[…] 在Wally中，我们利用基于格的部分同态加密（SHE）来减少响应开销。[…] 服务器在SHE下计算加密信息与集群条目之间的距离函数，并返回加密分数。这减少了响应，因为加密分数的大小显著小于条目。
## 苹果的实现：Wally
> [PenPen](https://boehs.org/node/<./penpen>)的笔记：本节提供了[可扩展的私有搜索与Wally](https://boehs.org/node/<https:/arxiv.org/pdf/2406.06761>)论文的高级概述。
不幸的是，苹果的同态加密实现并不像我们上面讨论的那样纯粹。苹果必须在隐私和性能之间取得平衡，而这两者是相互矛盾的（同态加密程序的运行速度比其等效程序慢许多数量级）。
在讨论苹果的同态加密之前，我们先退一步。一个非私有的搜索实现可能如下所示：
  1. 在初始化时，服务器将其文档分成相似的文档集群。[2](https://boehs.org/node/<#fn2>)
  2. 客户端选择与查询最匹配的集群。
  3. 客户端将其向量发送到服务器。
  4. 服务器返回集群中每个文档的相似度分数。
  5. 客户端选择最佳条目。
  6. 客户端请求最佳条目的元数据。


这种实现存在以下安全漏洞：
  1. 服务器可以读取向量。嵌入向量可以[非常具有揭示性](https://boehs.org/node/<https:/arxiv.org/abs/2310.06816>)。
  2. 客户端会泄露最近的集群。这是一个较小的问题，但它可以用来推断查询。例如，嵌入向量匹配“狗”的查询很可能位于“动物”集群中。
  3. 为了获取相关的元数据，客户端会向服务器发送最近条目的索引。这也会导致隐私泄露！


### 隐藏嵌入向量：回到同态加密
嵌入向量是目前泄露的最敏感信息。
完全同态加密对苹果来说太慢了，因此他们使用了部分同态加密。SHE支持加法和乘法逻辑，但只能到一定深度。每个数学运算都会增加深度，因为它会增加噪声量。选择的参数在安全性和噪声预算之间取得了平衡。显然，理想情况下不应该在这些约束下工作。不幸的是，FHE目前还不够快。
以下是实现的操作，其中`ct`表示`E(v)`，`v`是一个向量：
SHE操作| 结果| 时间（毫秒）| 噪声（比特）  
---|---|---|---  
PtCtAdd(ct, v’)| E(v + v’)  
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](https://boehs.org/node/<https:/www.rfc-editor.org/rfc/rfc9458>)匿名网络来代理对Wally的请求。这意味着无法知道特定请求来自哪个设备——所有请求都混合在一起。此外，还采取了以下缓解措施：
  1. 客户端发出一些虚假查询，然后丢弃结果。
  2. 查询按“时期”分组。在每个时期内，固定数量的用户发出查询，他们的查询在时期结束时处理。查询也会在随机时间以随机顺序发送，希望消除时间侧信道。


[Jeff Johnson](https://boehs.org/node/<https:/lapcatsoftware.com/articles/2025/1/1.html>)正确地指出，这个方案仍然存在一些缺陷：
> 这两个跳转，这两家公司，已经在合作了，那么在技术上有什么可以阻止这两家公司——无论是自愿还是在某个政府的秘密命令下——联合起来，连接这些点呢？
### 隐藏元数据
元数据是我们的第三个泄露。解决方案其实很简单。与其查询集群中某个索引的元数据，不如让集群返回该集群中存储的所有索引的元数据。
> [PenPen](https://boehs.org/node/<./penpen>)的笔记：这似乎意味着客户端无论如何都会获取大量数据。我不怪你质疑服务器是否真的需要。问题是，存储的向量是最大的存储用户。每个向量可能很容易达到几千字节。论文讨论了一个包含3500万个条目的数据库，分布在8500个集群中。
如果元数据太大，可以使用本文中详细描述的技术进行私有信息检索，而不是我们一直关注的私有最近邻搜索。
## 讨论
在我继续之前，我想明确一点，我只是一个爱好者，而不是这个主题的专家。我第一次听说同态加密是在阅读Jeff Johnson最近的文章“[Apple Photos在iOS 18和macOS 15上向服务器发送数据](https://boehs.org/node/<https:/lapcatsoftware.com/articles/2024/12/3.html>)”以及[后续](https://boehs.org/node/<https:/lapcatsoftware.com/articles/2024/12/4.html>) [文章](https://boehs.org/node/<https:/lapcatsoftware.com/articles/2025/1/1.html>)时，前面的内容是我花了大约10个小时的研究成果。我不质疑他写的任何内容。
> 理解隐私的一种自然方式是将其等同于保密。根据这种解释，如果我的数据是私有的，那么除了我之外没有人可以读取我的数据[…] 隐私权也可以意味着私有**所有权**。[…] 在增强视觉搜索中，苹果似乎只关注隐私作为保密的理解，而忽略了隐私作为所有权的理解。
我自己在花时间整理了一大堆零散信息后，决定我喜欢这个功能，并将保持启用状态。话虽如此，技术理解并不能代替同意，苹果本应请求用户的同意并提供适当的解释。
!["发生在你iPhone上的事，就留在你的iPhone上。"](https://boehs.org/assets/Pasted%20image%2020250109113847.png)
苹果曾经说过“发生在你iPhone上的事，就留在你的iPhone上。”显然，这并不完全正确，而且在苹果开始使用同态加密之前很久就已经不是这样了。
关于私有云计算的简短题外话
毫无疑问，他们正在付出努力。比其他任何科技公司都要多。但他们仍然做出了牺牲，比如当他们决定将最复杂的AI工作负载卸载到服务器上时，这个项目被称为[私有云计算](https://boehs.org/node/<https:/security.apple.com/blog/private-cloud-compute/>)。这包括在一个隔离的、无权限和无状态的环境中运行计算，并允许安全研究人员阅读源代码。
这一切听起来不错，但我怎么确定服务器运行的是它们所说的代码呢？对于同态加密，这种信任是不必要的，因为敌对服务器没有什么可窃取的，但LLM无法在这种环境下运行。如果我们期望知道私有云计算确实是私有的，我们必须能够通过加密验证来**知道**我们不控制的服务器正在运行我们信任的代码，但当服务器可以通过网络发送任何数据时，我们怎么知道这一点呢？服务器**说**它正在运行提交`f52fbd`并不意味着什么，它可以说任何它想说的话。这是一个感觉不可能解决的问题，苹果也认识到了这个问题：
> 没有通用的机制可以让研究人员验证这些软件映像是否与生产环境中实际运行的代码匹配。
他们似乎声称已经找到了解决方案。未来，我计划调查这一说法。但无论如何，回到手头的任务。同态加密是私有的吗？**某些东西**正在离开你的设备……
但是，**真正**离开你设备的信息是什么？这里没有“相信我”的元素。除非在数学或苹果的实现中发现了一些问题，否则这是第一次云能够作为一种设备和你数据的扩展，这是一个非常令人兴奋的前景。苹果已经能够在不知道照片内容的情况下对照片进行分类。这有多酷。
如果这个项目在智能手机和社交媒体商品化之前出现，我可能会写一些关于滑向越来越不谨慎使用云的滑坡的文章。但我们已经生活在一个所有数据都在云端而不是我们手中的世界。这个项目代表了向正确方向迈出的一小步，我无法不感叹它的酷炫。我只是希望苹果能更坦诚一些。
我们生活在一个令人惊叹的时代。
## 📝 参考资料与推荐阅读
  * [使用同态加密构建应用程序](https://boehs.org/node/<https:/homomorphicencryption.org/wp-content/uploads/2018/10/CCS-HE-Tutorial-Slides.pdf>)
  * [可扩展的私有搜索与Wally](https://boehs.org/node/<https:/arxiv.org/pdf/2406.06761>)
  * [同态加密](https://boehs.org/node/<https:/en.wikipedia.org/wiki/Homomorphic_encryption>)
  * [完全同态加密的高级技术概述](https://boehs.org/node/<https:/www.jeremykun.com/2024/05/04/fhe-overview/>)
  * [技术永远不能代替同意](https://boehs.org/node/<https:/lapcatsoftware.com/articles/2025/1/1.html>)


## 👟 脚注
  1. 你可能会想知道，如果除了一个值外所有值都相同，这如何保持私有。加密函数不一定是确定性的。这就是噪声。它是随机的。[↩︎](https://boehs.org/node/<#fnref1>)
  2. 使用K-means聚类。更多的集群意味着更高的性能，但太多的集群可能会导致选择错误的集群。[↩︎](https://boehs.org/node/<#fnref2>)


[Evan Boehs](https://boehs.org/node/<https:/boehs.org>) [/node/homomorphic-encryption](https://boehs.org/node/</node/homomorphic-encryption>)

_         /`\      (     /`\
  (_)     /`\  // \\     ))    // \\
       // \\ // \\ /`\_____||    // \\
       // \\ // \\ // /    \ /`\ // \\
       // \\ // \\ ///_________\// \\// \\ 
       // \\ // \\ // |-[+]---| // \\// \\
       // \\ // \\ // |-------| // \\// \\
 _____,....-----'------'-----''-------'---'----'--

**主要**
    
  * [首页](https://boehs.org/node/</>)
  * [联系](https://boehs.org/node/</contact>)
  * [博客](https://boehs.org/node/</in/blog>)


**链接**
    
  * [GitHub](https://boehs.org/node/<https:/github.com/boehs>)
  * [Mastodon](https://boehs.org/node/<https:/social.coop/@eb>) ([Bsky](https://boehs.org/node/<https:/bsky.app/profile/did:plc:7u5tor5fp3ai4jwvea6t6mjd>))
  * [捐赠](https://boehs.org/node/<https:/liberapay.com/e>) ([Ko-fi](https://boehs.org/node/<https:/ko-fi.com/evan>))


**元数据**
    
  * [⤺](https://boehs.org/node/<https:/xn--sr8hvo.ws/%F0%9F%86%8E%F0%9F%88%B6%E2%8F%B0/previous>) 🕸💍 [⤻](https://boehs.org/node/<https:/xn--sr8hvo.ws/%F0%9F%86%8E%F0%9F%88%B6%E2%8F%B0/next>)
  * [博客列表](https://boehs.org/node/</blogroll>)
  * [分析](https://boehs.org/node/<https:/beanbag.boehs.org/share/JGBYO4bVg3kZVQUb>)
阅读全文（20积分）