PIR——第一周汇报

本周研究进展

上一周主要了解PIR的背景知识。熟悉了PIR的基本概念，了解了PIR的两种类型，即CPIR和ITPIR的概念、应用条件和优缺点，了解了一般PIR的基本模型和实现过程。

本周共完成了如下工作：

对Hodor那篇论文提出的BO-PIR进行了研究，并用自己能理解的方式重新写了一遍
了解了异构分布式HPIR那篇论文中的Shamir、Ramp秘密共享算法以及新提出的秘密共享算法
对Private Information Retrieval with Sublinear Online Time这篇论文的方法（即BO-PIR所基于的PIR方案）进行了研究，但尚未读完

研究内容细节

下面对上述三项工作进行详细汇报。

1.本周研究的重点是BO-PIR方案，虽然只有两页的内容，但一开始读感到很困难，很多地方无法理解，在读了其他几篇论文特别是Private Information Retrieval with Sublinear Online Time这篇之后，逐渐理解了BO-PIR的设计方案。对论文所做笔记如下：

BO-PIR——Batch PIR with off-line processing
含离线预处理的批处理PIR

1.1 背景：直觉上，隐藏用户访问痕迹可直接将源服务器上的数据库下载到客户端。但这样做有如下两个严重缺点：

（1）需要客户端实时地保存和更新服务器的数据库，开销过大，效率极低

（2）服务器失去对数据库敏感数据的控制，违反隐私条例

1.2 基本思想：客户端请求先作预处理，在encalve（可以理解为客户端）中为每个数据库存储hints，并通过hints对源数据库进行高效且安全的数据检索

1.3 过程：过程基本分为离线阶段和在现阶段。
离线阶段->客户端决定检索哪条数据前，从服务器得到一次性的hint
在线阶段->用户向source server发送请求，结合server返回的数据和hints恢复要查找的数据库（在线阶段的计算复杂度可降低为$\sqrt{n}$级别）

1.4 简化BO-PIR模型：

BO-PIR单次查询的简化模型可从另一篇论文的toy protocol中得到（下面是给自己看的简陋的描述）：

缺点：这个方案保护隐私的方法取决于请求集S’是均匀随机的。但hints无法用于后续的其他请求，因为后续请求的请求集S’将不再是均匀随机的

个人理解是例如第二个服务器接收了S’，在例子里接收到了S’={3,9}，如果之后用户再发送一个S’={4,9}，那第二个服务器知道根号n为3，即每个Sj的元素个数为3，就可以通过这两个S’凑出{3,4,9}这样的完整Sj，之后再查询i=3,4,9的时候根据客户端发送的S’即可得出查的是哪个i，因此会泄露i

1.5 优化的BO-PIR模型：

1.5.1 目标1：将处理单次请求扩展为处理批处理请求，可以直接多次预处理生成不同的hints集（例如提前生成10000个hints集以应对10000次查询），但这样做中继的enclave存储压力会变大。

1.5.2 解决方案：

可直观想到去除重复的hints集，将k个请求的hints集减到重复因子l个，意味着需要用一个或多个用过的hints集执行后续查询操作。为避免攻击者利用重用的hints集泄露，采用模糊化技术，将所有k个索引的查询集在发送到数据源之前随机化：

1.5.3 安全性论证：

1.假设查询集完全随机，且客户端在预处理阶段保持机密性，则BO-PIR可保证每个索引的隐私（被窃取的概率为1/n）

证明：

1.5.4 处理失败的请求：

2.关于HPIR的那篇论文，目前还没有看完，看到其设计的新的专门用于PIR的秘密共享方案那部分。该协议主要是针对多个server的场景（两个或两个以上），每个server的数据库资源和通信负载不同，以提高通信效率。

下面是对Shamir和Ramp秘密共享的流程笔记：

关于HPIR-tailored秘密共享方案基于Ramp秘密共享方案，主要处理的是在t增加的情况下服务器数量l也要增加的问题，无法满足其对于两个或固定服务器数量的应用场景，笔记还未整理好。

3.关于Private Information Retrieval with Sublinear Online Time这篇论文，组长听了报告会回来做了交流，对论文基本内容有了了解。

其简化模型，即论文提到的toy protocol就是BO-PIR的简化模型，步骤见1.4

在此基础上，该步骤存在一个问题，即client向第一个server发送的是整个数据库的索引以及可能的额外的分组所需的索引，通信开销较大，于是提出了一个简单的改进方案：

但文章后续对方案又进行了一些处理，进一步降低通信复杂度，并对应用场景作了迁移，由双服务器场景改为单服务器场景等，并引入了伪随机数等机制（笔记还未整理）。我们对方案做了讨论，也结合了之前学长提的一些自己的观点。方案中offline所做的预处理只能用作online的一次操作，预处理效率太低，真正的offline/online模式需要在offline阶段做一次预处理即可应对多次online操作，而BO-PIR即达到了这个目的，但是BO-PIR基于的是该论文的toy protocol所做的更改，意味着通信负载依然是超线性级别，虽然做了一定优化，但优化并未改变通信复杂度的级别，依然是超线性，且带来了准确率的再一次降低。

后续工作计划

我与组长做了分工，两人分别看一部分论文，然后通过传笔记、线上交流等方式了解全部的论文PIR方案。这周基本上看完了BO-PIR与Private Information Retrieval with Sublinear Online Time两篇（虽然还有一些地方没弄明白），下周将把之前还未结束的HPIR那一篇看完，然后将[CCS18]Private Stateful Information Retrieval这篇看完。和组长交流一下，把迄今为止前沿的PIR方案做一下梳理和总结，前两周的任务基本就结束了。

MYBLOG