1-8 隐语小课｜私有信息检索(PIR)及其应用场景

“隐语”是开源的可信隐私计算框架，内置 MPC、TEE、同态等多种密态计算虚拟设备供灵活选择，提供丰富的联邦学习算法和差分隐私机制

开源项目

github.com/secretflow

gitee.com/secretflow

前言

欢迎来到小剧场全新系列节目「隐语小课」！本系列将围绕与隐私计算相关的技术概念陆续上新，旨在分享技术科普型内容，欢迎投稿，方式见文末。

首篇投稿来自隐私计算框架“隐语”团队的珊竹同学：

小剧场：“请问珊竹带来什么内容？”

珊竹：“那就浅谈下私有信息检索(PIR)及其应用呗！”

1. The Problem of Private Information Retrival

PIR 全称为 Private Information Retrival，直观的翻译名字为“私有信息检索”。已知的最早提出 PIR 的文章是 1995 年 Benny Chor, et. al. [1]。在文章最开始的时候，提到了在传统的 query 场景中，我们有一个 client 发送 query，有 server 回复结果。

从抽象角度来看，我们可以试图保护：

Server 数据的安全性
Client query 的安全性

在 [1] 之前，有许多工作在研究如何保护 server 端 DB 数据的安全性，在此不再赘述。Benny Chor, et. al. [1] 提出了一个问题：我们是否可以在 query 场景中保护 client query 的隐私性？由于当时分布式数据库存储的发展，因此他们提出了一个基于 replicated DB (and non-colluding) 的方案。

这就是 PIR 的场景性问题，根据现实中不同的 client 以及 server 的假设，我们可以把协议进行分类。

2. PIR 场景的分类

我们可以看到，PIR 场景中的实体有 client 以及 server，并且 client 向 server 发送了一个需要保护隐私的 query ，server 向 client 返回一个 query 的最终结果。

如果我们仅仅需要保护 query 的隐私、而又不在意性能 ，是有一个很简单的解决方案。我们可以让 server 将其持有的所有数据全量发送给 client，由 client 本地进行搜索查询并得到结果。显然，这种方案是十分低效的。我们寻求一种协议可以比这种简单的解决方案更加高效。

2.1 单server场景(单个数据库)&多server场景(分布式数据库)

如果我们假设 DB 只有一个，那么场景就是如下图所示：

这种情况下我们一般采取加密查询数据，之后交给 server 去作查询/匹配操作以得到正确的查询结果。例如基于任意加法同态算法的 [1]，全同态加密的 SealPIR [2]，以及返回一个 block 的查询结果的 [3]。

PIR 的研究者们同样证明了：在单 DB 的场景中，所有的 PIR 协议必须基于某个数学难题（这类 PIR 协议也叫做 computational PIR (cPIR) 协议），我们不可能构造出一个单 DB PIR 协议满足 unconditional security

如果我们假设有许多个 replicated DB，那么场景就是如下图所示：

这种情况下我们可以达到 unconditional security，例如基于 DPF 的 PIR [4] 等等。但是多 server 场景中有两条关键假设：

数据库是 replicated，因此每个数据库都持有相同的数据集
数据库中存在 non-colluding 的假设，server 之间存在不可共谋的假设（例如 honest majority or only one honest server）

2.2 +保护数据库隐私 (Symmetric PIR, sPIR)

如果我们试图保护：（1）DB 数据的安全性；（2）Client query 的安全性。那么我们叫这种协议为 symmetric PIR。我们之前提到的一些算法，例如基于任意加法同态算法的 [1] 以及全同态加密的 SealPIR [2] 都同时保护了数据库的隐私，因此也属于 sPIR。

2.3 基于索引查询/基于匹配查询

基于索引：index PIR

基于查询：keyword PIR

基于索引/匹配的 PIR 协议在单 DB 和多 DB 的情况下均成立，我们下面以单 DB 的方案为例。

【基于索引的 PIR】

基于索引的 PIR 要求 client 在查询数据库之前，已经预先得知想要查询的数据索引信息。如果我们有一个原本是 (key, value) 的 DB 的话，那么其实并不一定必须要使用基于匹配的 PIR。

如果 DB 中的 key 属于非隐私信息，那么我们可以使用一个 encoding 函数，将每个数据库元素的 key 映射到某个 index 上，然后对数据库进行重新排序，那么在 client 想要插叙某个 key 的时候，可以直接使用公开的 encoding 函数获取到 key 相对应的 index 值。
但是如果 DB 中的 key 属于隐私信息，那么也就意味着我们必须使用 sPIR 来保护数据库隐私，而 DB 使用的 encoding 函数本身可能会泄漏数据库 key 的分布情况，因此在这种情况下我们只能使用基于匹配的 PIR。