基于同态加密实现的隐匿查询方案

基于同态加密的隐匿查询方案总结

1. 单次查询的隐匿查询方案

• 隐匿查询 (Private Information Retrieval, PIR)：用于保护用户查询隐私的隐私计算方案，适用于对用户检索信息隐私性要求较高的场景。
• 解决方案：用户将所有数据库数据下载到本地，进行本地查询，无需其他参与方，不存在隐私泄漏风险。
• 多服务器PIR方案：
  • 多个服务器各自存储一份数据副本。
  • 查询方构造一个子集，服务器根据该子集返回相应的查询结果。
  • 安全假设：服务器之间不共谋。
• 双服务器PIR方案：
  • 数据复制存在两个服务器。
  • 查询方构造集合 {1, n} 的子集 Q，且 i ∉ Q。
  • 通过计算最终恢复查询结果。

2. 单服务器PIR方案

• 同态加密：
  • 公钥加密算法，允许对密文进行特定形式的代数运算。
  • 支持加法同态和乘法同态。
• 方案流程：
  • 生成公私钥对。
  • 构造查询向量并加密。
  • 数据服务方计算并返回结果。
  • 查询方解密获得最终结果。
• 优点：隐私性高，信任成本低，低交互次数。
• 缺点：通信量高，响应耗时较长。

3. XPIR 方案

• 数据库编码：将数据库表示成多维数组。
• 查询密文生成：用户生成多个查询向量，进行加密后发送给服务器。
• 服务端计算：服务器进行内积运算，返回查询结果。
• 客户端恢复：用户解密并重组查询结果。
• 特点：维度 d 越大，发送的密文越少，返回的密文越多。

4. SEAL PIR 方案

• BFV 替换操作：利用 BFV 密文的替换操作减少发送的密文数量。
• 密文扩展算法：通过替换操作和密文加法运算，将一个密文扩展成多个密文。
• 优点：减少通信开销，提高效率。

5. Onion PIR 方案

• 外积运算：结合 BFV 和 RGSW 加密算法的外积运算。
• 通信量优化：服务器返回一个密文，减少通信量。
• 噪声控制：外积运算的噪声增长是线性的。
• 计算开销：计算开销较低，适合大规模查询。

6. 批量查询的隐匿查询方案

• Cuckoo哈希：一种高效的散列方法，将 m 个元素映射到 b 个桶中，每个桶最多只包含一个元素。
• 工作原理：使用 k 个哈希函数，插入和替换元素。
• 应用场景：适用于需要高效查询和插入的场景。