隐私计算技术详解 | 一篇关于 SealPIR 的文章 - 基于同态的隐私信息检索协议 - 1. 隐私信息检索协议的定义和分类

1.1 PIR定义

隐私信息检索(Private information retrieval PIR)是对信息检索(information retrieval IR)的一种扩展，最早在[CKGS95][3]中提出，用于保护用户查询信息，防止数据持有方得到用户的检索条件。

PIR协议目标可以定义为：Alice有共N行的数据库D，每一行的数据大小为L。Bob希望查询获得其中指定位置的某一行，但是不想告诉Alice自己查询的是哪一行。

隐私信息检索协议(PIR)需要满足正确性和安全性两方面的要求：

• 正确性：用户得到要查询的数据
• 安全性：服务端 无法知道 用户查询的是哪条数据
  

1.2 PIR分类

1.2.1 服务器数量分类

按照服务器数量分类可分为多服务器PIR和单服务器PIR。

• 多服务器PIR(MultiServer-PIR)

多服务器PIR一般基于信息论安全(Information-theoretic security)的密码技术，例如：基于函数密码分享(Function Secret Sharing)[BGI16][4]方案，也称为：IT-PIR。

多服务器PIR协议大体流程如下：

1. 客户端生成查询条件的分量，发送给不同的服务器；
2. 服务器收到查询条件的分量后进行相应的计算，返回给客户端；
3. 客户端接收到所有服务器的响应后，将服务器查询响应看做秘密共享的分量进行合成，得到查询结果。

为了保护查询信息的安全，多服务器PIR方案中要求服务器之间是不能合谋的，增加了系统实现和部署的难度。多服务器PIR方案中计算量相对较小，但通信量一般很大，大体规模是????????(1)。

• 单服务器PIR(SingleServer-PIR)

单服务器PIR一般基于公钥密码方案，特别是同态性质的公钥密码方案，安全性基于计算复杂理论，也称为CPIR。

基于同态的单服务器PIR方案，大体流程如下：

1. 客户端生成加密的查询向量，发送给服务端;
2. 服务端接收到查询向量后，在本地执行同态运算，将结果返回给客户端；
3. 客户端收到响应后，解密得到查询结果。

单服务器PIR方案一般通信量较少，但计算量较大，且容易部署。

1.2.2 按照检索条件分类

• Index PIR/Dense PIR

服务端有n个元素的数据库????={????1,????2,…,????????}，用户查询第????个元素，通过执行PIR协议，用户得到????????，服务端不知道用户查询????的信息。由于用户的查询条件在一个连续的集合[1…????]，Index PIR也称为Dense-PIR。

• Keyword PIR/Sparse PIR

服务端的数据是(key,value)对构成的n个元素的数据库，用户选择自己要查询的key，通过执行PIR协议，用户得到key对应的value。这里查询条件key不能覆盖一个连续集合，例如：手机号或身份证，也称为Sparse PIR。

1.3 PIR性能指标

PIR的性能指标主要包括计算量和通信量。

• 计算量：计算量一般指的是服务端的计算量。
• 通信量：通信量可细分为查询请求的通信量和响应的通信量。

Trivial PIR中服务端没有计算量，将数据全部发给客户端，客户端在本地查询，通信量跟数据库中数据量n相关。因此PIR的通信量要求小于数据库的容量。对比IT-PIR和CPIR的计算量和通信量可以看到，IT-PIR在计算量较少，但通信量较大；CPIR计算量较大，但通信量较小。

除了计算量和通信量两个指标外，有些论文里还引入了成本(monetary)作为指标，成本(monetary)指标实际上是对计算量和通信量平衡得到的指标，更适用于实际业务需求。