分区可搜索加密技术解析

### 分区可搜索加密技术解析 在当今的数据处理和安全领域，可搜索加密技术扮演着至关重要的角色。本文将深入探讨分区对称可搜索加密（PSSE）的相关技术，包括布隆过滤器（Bloom Filters）的应用、PSSE的基本概念、不同的实现方案以及其安全性分析。 #### 布隆过滤器（Bloom Filters） 布隆过滤器是一种概率性抽象数据结构，它允许在常数时间内进行搜索、插入和删除操作。与使用哈希表或不同类型的基于树的结构的现有方法相比，布隆过滤器在运行时间和内存空间上都有显著的改进。 其核心思想是存储关键字的表示，而不是关键字本身。具体操作如下： 1. 假设有一个由B位组成的位向量 ⃗b 作为底层数据结构。 2. 对于插入的字符串 w，计算 i ← Hash(w)，其中 Hash 是一个哈希函数，其输出范围为 {0, ..., B - 1}。 3. 对于每个哈希函数输出的索引 i，将 ⃗bi 设置为 1。 由于 bi 可能被多个字符串设置为 1，因此布隆过滤器可能会出现误报（false positives）。不过，通过控制使用的哈希函数数量，可以限制插入 n 个元素时误报的概率： \[Pr\left[\exists w \notin W \land |W| \geq 1 \land BF.Search(\vec{b}, w) = 1\right] \approx \left(1 - \left(1 - \frac{1}{B}\right)^{\gamma \cdot n}\right)^{\gamma}\] 其中，γ 是哈希函数的数量。最优的哈希函数数量约为：γ ≈ ln(2) · B / n。 在数据表示方面，假设有 d 个数据文件 D(1), ..., D(d)，以二进制形式表示。对于每个 D(i)，我们将其关键字向量 w(i) = (w(i)1, ..., w(i)ni) 实例化，其中 w(i)t 表示第 i 个文档 D(i) 的第 t 个关键字。对于每个 D(i)，我们实例化一个布隆过滤器 BF(i)，其位向量 ⃗b(i) 可以分割成 l(i) 个大小相等的桶，每个桶的大小为 Bi / l(i)，其中 Bi 是 ⃗b(i) 的长度。 #### 分区对称可搜索加密（PSSE） 分区对称可搜索加密（PSSE）是对标准可搜索加密（SSE）定义的自然扩展。在 PSSE 中，搜索算法需要由 N 个用户联合进行后处理，而不是由单个用户完成，以确定包含相应关键字的文档。该协议通过预先在用户之间共享公共参数，然后以类似于分布式伪随机函数（PRF）的方式组合他们的结果来工作。 ##### 诚实用户模型下的 PSSE 在最简单的设置中，分区协议要求所有用户在声明其结果时保持诚实，以共同验证关键字是否属于某个文档。一个 N 方的 PSSE 由以下一组算法组成： - **PSSE.Setup(1λ, DB, N)**: 这是一个概率多项式时间（PPT）算法，它接受关键字数据库 DB 和用户数量 N 作为输入。该算法提取关键字，生成 N 个单独的数据库 DBj，并将 DBj 发送给用户 j。此外，还可能计算并添加一些辅助信息到公共参数 pp 中。 - **PSSE.ClientSetup(DBj, j)**: 每个用户 j 独立地采样一个公私钥对 (skj, pkj)。在这个阶段，用户 j 使用 pkj 对 DBj 进行加密，得到 EDBj，并将其发送给服务器。 - **PSSE.Search(EDB, skj, w, I)**: 这是客户端 j 和服务器之间的一个协议。客户端 j 使用其私钥 skj 查询索引在 I 中的数据文件中是否包含关键字 w。服务器返回一个位 bj，表示部分搜索是否在索引为 I 的数据文件中找到了 w。 - **Comb(b1, ..., bN)**: 在搜索过程完成后，各方在不与服务器交互的情况下本地组合他们的个人结果，生成搜索查询的最终结果。 如果存在第五个算法 (EDB′j, σ′) ← Update(EDBj, σ, skj, I, w, op)，则称该分区对称可搜索加密方案是动态的。其中，客户端 j 对关键字 w 进行加密，并发送一个更新查询，操作 op 可以是删除或插入。 我们要求任何 PSSE 方案都满足正确性，即对于任何 w ∈ {w(1), ..., w(d)}，以下概率值接近 1： \[Pr\left[b \leftarrow Comb(\{b_j\}) \mid pp \leftarrow PSSE.Setup(1^{\lambda}, DB, N) \land \{(sk_j, p_kj) \leftarrow PSSE.ClientSetup(DB_j, j)\}_{j \in [N]} \land \{b_j \leftarrow PSSE.Search(EDB, sk_j, w, I)\}_{j \in [N]}\right]\] 如果任何概率多项式时间（PPT）对手在某个游戏中获胜的优势接近 1/2，则称该 PSSE 方案是自适应安全的。 ##### 处理恶意用户 在实际场景中，可能存在恶意用户，他们可能会故意改变搜索结果。为了处理这种情况，我们修改了诚实用户模型下的定义，给服务器提供一些验证方法，如 VerCT 和 VerKey。在这种设置下，要求 ClientSetup 为每个用户返回一个公钥 pkj。正确性可以通过要求以下概率值接近 1 来描述： \[Pr\left[1 \leftarrow Comb(\{b_j\}) \mid pp \left