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
组成的向量,在你想要检索的值的索引处有一个1
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)
,而不会泄露任何信息。然而,你可能需要在执行成本上付出代价。
sqrt查找```
#[fhe_program]
fn lookup(
col_query: [Cipher
row_query: [Cipher
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::
let normalized_vector: Vec
我们没有办法简单地返回最佳匹配。最多,我们可以返回数据库中每个条目的分数,然后客户端可以解密这些分数并找到最佳匹配:
> 对于每个查询,服务器响应包含集群中的所有条目。[…] 在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/n