加密数据库中的选择性文档检索方案解析

### 加密数据库中的选择性文档检索方案解析 #### 1. SDR 的安全属性 选择性文档检索（SDR）方案的主要目标是让服务器能在加密数据上进行搜索，并让客户端选择性地检索匹配的内容。在这种情况下，信息泄露可能来自三个源头：索引、陷门和查询结果，相应地存在三种隐私问题： - **索引隐私**：类似于明文隐私，意味着索引不应泄露有关编码关键字的任何信息。 - **陷门隐私**：类似于谓词隐私，意味着陷门不应泄露有关编码谓词的任何信息。 - **查询结果隐私**：如果客户端在两次执行检索算法时检索了 x 个文档，服务器不应知道这两次执行返回的是否是相同的文档。 现有可搜索对称加密（SSE）方案已经考虑了索引隐私和陷门隐私。然而，查询结果隐私在加密数据外包的场景中尚未被涉及，尽管它在许多应用场景中是一个实际的关注点。例如，若 Alice 将工作和个人文档存储在受 SSE 方案保护的远程服务器上，在办公室查询工作文档，在家查询个人文档。若服务器发现她晚上 10 点查询的文档与上午 11 点相同，就能猜测她在办公室加班。 #### 2. 游戏式安全定义 类似于 SSE 安全模型中的安全定义，将攻击者视为半诚实的服务器（以及其他外部攻击者）。半诚实指的是一个诚实但好奇的数据库服务器，它会遵守协议，但会尝试获取尽可能多的信息。 - **定义 1**：若在图 1 定义的攻击游戏中，没有概率多项式时间的攻击者具有不可忽略的优势（优势定义为 | Pr[b = b′] - 1/2|），则 SDR 方案是安全的。 - **攻击游戏流程**： 1. 挑战者运行密钥生成算法，获得秘密密钥 K 和谓词集 F，发布 F 并随机选择一个比特 b。 2. 攻击者 A 自适应地进行以下类型的查询： - **索引预言机查询**：在第 j 次索引查询时，A 输出两个文档 dj,0, dj,1 ∈D，挑战者用 BuildIndex(K, dj,b) 响应。 - **陷门预言机查询**：在第 i 次陷门查询时，A 输出两个谓词 fi,0, fi,1 ∈F，挑战者用 Trapdoor(K, fi,b) 响应。 - **检索预言机查询**：假设有 j 次索引查询和 i 次陷门查询，挑战者（模拟客户端）和服务器运行检索算法。服务器输入数据库 DB，包含 j 个（索引，文档）对，挑战者输入密钥 K 和一组文档标识符 IDb，ID0 和 ID1 是攻击者选择的相同大小的标识符集，IDb 指示挑战者应检索哪些文档。 3. A 输出对比特 b 的猜测 b′。 通过给予攻击者索引预言机查询，可保证攻击者无法区分不同文档的索引，从而覆盖索引隐私；给予陷门预言机查询，攻击者无法区分从客户端收到的陷门，覆盖陷门隐私；给予检索预言机查询，攻击者无法得知客户端检索的文档，覆盖查询结果隐私。若 SDR 方案在此定义下安全，攻击者只能知道挑战者检索的文档数量，而无法得知其他信息。 #### 3. 安全定义的放宽 查询结果隐私在许多 SDR 方案的应用场景中可能很重要，但在其他场景中可能并非如此。为满足定义 1 的安全要求，SDR 方案的检索算法会使用私有信息检索技术，这会带来显著的计算和通信复杂性，因此可能会为了效率牺牲该隐私属性。于是有了仅涵盖索引隐私和陷门隐私的定义。 - **定义 2**：若在图 1 定义的攻击游戏中，满足以下例外情况，且没有概率多项式时间的攻击者具有不可忽略的优势，则 SDR 方案实现了索引隐私和陷门隐私： 1. 游戏中不允许进行检索预言机挑战查询。 2. 对于任何索引预言机挑战查询 (dj,0, dj,1) 和任何陷门预言机挑战查询 (fi,0, fi,1)，u(dj,0) 满足 fi,0 当且仅当 u(dj,1) 满足 fi,1。 这种放宽的定义提供了与完全安全定义相同级别的安全保证。 #### 4. 提出的 SDR 方案 提出了一种新的 SDR 方案，并在上述安全模型中证明其安全性。该方案先从支持相等性测试谓词的情况进行描述，也支持其他类型的谓词。 - **预备知识**：若存在两个（可能相同）的操作 (⊗ 和 ⊕)，使得 E(a) ⊗ E(b) = E(a ⊕ b)，则加密函数 E(·) 称为同态的。在本文中，元素 x 的同态加密写为 [[x]]，即 [[a]]⊗[[b]] = [[a⊕b]]。使用的是语义安全的同态加密方案，允许对加密值进行一次乘法和多次加法，如基于格的 Gentry - Halevi - Vaikuntanathan（GHV）方案、Brakerski - Vaikuntanathan（BV）方案和基于配对的 Boneh - Goh - Nissim（BGN）方案。 - **提出的方案**：利用满足上述要求的对称同态加密方案和 Chang 与 Mitzenmacher 的索引构造方法，包含以下算法： - **Keygen(s)**：给定安全参数 s，为对称同态加密方案生成密钥 K，如对称版本的 BV 方案，并生成相等性测试谓词集 F = {fw|w ∈ W}。对于任何文档 d，u(d) 满足 fw 当且仅当 w ∈ u(d)。 - **BuildIndex(K, d)**： 1. 生成不同关键字的列表 u(d)。 2. 为文档 d 构造明文索引 Id = (Id[1], Id[2], ... , Id[b])，b 是可能关键字集的大小。若 w ∈ u(d) = si ∈ W，Id[i] 设为 1，否则设为 0。 3. 生成 [[Id]] = ([[Id[1]]], [[Id[2]]], ... , [[Id[b]]])，即明文索引逐位加密。 4. 输出索引 Id = [[Id]]。 - **Trapdoor(K, fw)**： 1. 构造 tfw = (tfw[1], tfw[2], ... , tfw[b])。对于 1 ≤ i ≤ b，若 w = si，tfw[i] 设为 1，否则设为 0。 2. 输出陷门 Tfw = ([[tfw[1]]], [[tfw[2]]], ... , [[tfw[b]]])。 - **SearchIn