隐私计算技术解读 | 一文读懂SealPIR-基于同态的隐私信息检索协议_labeled psi from fully homomorphic encryption with

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

开源项目：
https://github.com/secretflow
https://gitee.com/secretflow

隐私信息检索(Private information retrieval PIR)也称为隐匿查询或匿踪查询，在医疗、股票、金融、社交等领域中都有大量应用场景。近年来PIR技术研究逐渐丰富，行业对应用PIR实现隐私保护的呼声也随之高涨。

引 言

[SealPIR]^[1]是微软开源的PIR实现，实现了2018年发表在IEEE S&P的论文[ACLS18]^[2]中的PIR方案。论文题目《PIR with Compressed Queries and Amortized Query Processing》已经包含了两个主要的贡献点：

• 对查询进行了压缩，通信量降低了274倍；
• 通过概率批量编码(probabilistic batch codes PBCs)可以同时执行多个查询，分摊查询处理的开销。

在近年的PIR协议研究中，特别是基于HE的PIR协议有很多进展，且大多数都是和SealPIR进行对比，因此理解SealPIR的原理也就有助于理解和跟踪he-based PIR近年来的发展。

本文将为小伙伴们介绍基于同态的隐私信息检索协议-SealPIR，欢迎大家在本文留言讨论。

1.PIR定义及分类

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方案中计算量相对较小，但通信量一般很大，大体规模是