加入隐私计算vx群，和原作者交流讨论：SecretFlow01
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。
【基于匹配的 PIR】
基于匹配的 PIR 实际上和 PSI with Payload 很相似。场景如下图所示：
其实就是 one-element PSI with Payload。PSI with Payload 使用 client 的输入 ki 以及 DB 的输入 {k1,…, kn} 进行撞库，把匹配后数据（也就是 ki）的 value 返回给 client。其中保护了
client 不知道未匹配到的 key 是什么
client 不知道未匹配到的 key 的 value 是什么
DB 不知道具体匹配结果的 key 是什么（有些 PSI 算法可以额外保证这些）
DB 不知道具体匹配结果的 value 是什么（有些 PSI 算法可以额外保证这些）
相关资料
【课程】https://cyber.biu.ac.il/event/the-12th-biu-winter-school-on-cryptography/
【代码】/microsoft/SealPIR
【代码】/OpenMined/PIR
参考文献
[1] Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan. “Private Information Retrieval”. FOCS (1995).
[2] Angel, Sebastian G. et al. “PIR with Compressed Queries and Amortized Query Processing.” IEEE Symposium on Security and Privacy (SP) (): 962-979.
[3] Gentry, Craig and Zulfikar Ramzan. “Single-Database Private Information Retrieval with Constant Communication Rate.” ICALP ().
[4] Gilboa, Niv and Yuval Ishai. “Distributed Point Functions and Their Applications.” EUROCRYPT ().
