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…
【代码】https://github.com/microsoft/…
【代码】https://github.com/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.”2018 IEEE Symposium on Security and Privacy (SP) (2018): 962-979.
[3] Gentry, Craig and Zulfikar Ramzan.“Single-Database Private Information Retrieval with Constant Communication Rate.”ICALP (2005).
[4] Gilboa, Niv and Yuval Ishai.“Distributed Point Functions and Their Applications.”EUROCRYPT (2014).