隐语小课|私有信息检索 (PIR) 及其应用场景

原创
2023/08/25 15:22
阅读数 84

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

代码开源:

https://github.com/secretflow

https://gitee.com/secretflow

 

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/

【代码】https://github.com/microsoft/SealPIR

【代码】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).

 

隐语社区:

https://github.com/secretflow

https://gitee.com/secretflow

隐语官网:https://www.secretflow.org.cn

👇欢迎关注:

公众号:隐语的小剧场

B 站:隐语 secretflow

邮箱:secretflow-contact@service.alipay.com

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部