关于隐私:隐私计算技术解读-一文读懂SealPIR基于同态的隐私信息检索协议

“隐语”是开源的可信隐衷计算框架，内置 MPC、TEE、同态等多种密态计算虚构设施供灵便抉择，提供丰盛的联邦学习算法和差分隐衷机制。

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

隐衷信息检索 (Private information retrieval PIR) 也称为隐匿查问或匿踪查问，在医疗、股票、金融、社交等畛域中都有大量利用场景。近年来 PIR 技术钻研逐步丰盛，行业对利用 PIR 实现隐衷爱护的呼声也随之低落。

引 言

SealPIR 是微软开源的 PIR 实现，实现了 2018 年发表在 IEEE S&P 的论文 ACLS18 中的 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 中提出，用于爱护用户查问信息，避免数据持有方失去用户的检索条件。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 计划，也称为：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) 指标实际上是对计算量和通信量均衡失去的指标，更实用于理论业务需要。

2. 基础知识

目前 Single-PIR 最好的协定大多基于近似同态算法 (Somewhat homomorphic encryption SHE) 设计的，SealPIR 中用到的是 BFV12 算法。

2.1 BFV 计划
[BFV12] 将 Brakerski12 中的同态算法从 LWE 迁徙到 RLWE，RLWE 因为有非凡的构造比 LWE 性能更好，例如，RLWE 抉择特定参数时，乘法能够应用 NTT(Number Theoretic Transform)。BFV 算法的参数包含：

• 多项式次数: 𝑁
• 明文模: 𝑡，素数
• 密文模: 𝑞，若干素数的乘积

明文空间是𝑅𝑡=𝑍𝑡[𝑥]/(𝑋𝑁+1)，即：𝑎0+𝑎1𝑥+…+𝑎𝑁-2𝑥𝑁-2+𝑎𝑁-1𝑥𝑁-1，𝑎𝑖∈𝑍𝑡
密文由两个多项式 (𝑐0,𝑐1) 形成，𝑐0,𝑐1∈𝑅𝑞=𝑍𝑞[𝑥]/(𝑋𝑁+1)。
密文扩张因子 (Ciphertext expansion factor)，是指 SHE 加密后失去密文绝对明文的增大的比例，对于 BFV 算法，密文扩张因子𝐹=2𝑙𝑜𝑔(𝑞)/𝑙𝑜𝑔(𝑡)。
对于 128bit 平安，同态加密规范中给出了举荐参数。思考下面的密文扩大因子，明文模𝑡取绝对较大时，能取得较小的密文扩张；但进行密文同态计算时，明文模𝑡太大时，会导致噪声增长太快，明文模𝑡也不能获得太大。
SealPIR 中 BFV 参数中 N 和 q 抉择举例如下表：

SealPIR 中用到的同态运算：

密文加法：明文𝑝1(𝑥)，𝑝2(𝑥)对应的密文是𝑐1 和𝑐2，𝑐1+𝑐2 是𝑝1(𝑥)+𝑝2(𝑥)的密文。明文乘密文：明文𝑝1(𝑥)对应的密文是𝑐1，𝑝2(𝑥)·𝑐1 是𝑝1(𝑥)·𝑝2(𝑥)的密文。替换：明文𝑝(𝑥)对应的密文是𝑐，对于奇数𝑘，𝑆𝑢𝑏(𝑐,𝑘)是𝑝(𝑥𝑘)的密文。例如，𝑝(𝑥)=7+𝑥2+2𝑥3，𝑆𝑢𝑏(𝑐,3)失去𝑝(𝑥3)=7+{𝑥3}2+2{𝑥3}3=7+𝑥6+2𝑥9 的密文。SHE 的同态运算会引起噪声的增长，当噪声超过肯定限度时，无奈解密失去明文，所以要适当抉择 SHE 算法的参数，及管制同态运算的噪声增长。

2.2 HE-based PIR

HE-based PIR 基本原理如下图所示：

假如服务端数据量为𝑛，根本流程如下

• 客户端生成 BFV 算法的私钥和公钥（𝑠𝑘,𝑝𝑘）;
• 客户端生成查问𝑛维 0 - 1 向量(0,…,0,1,0,…,0)，其中查问 index 𝑖的地位位 1，其它地位为 0;
• 客户端应用公钥加密查问向量的每个重量，失去(𝐸(0),…,𝐸(0),𝐸(1),𝐸(0),…,𝐸(0))，发送给服务端;
• 服务端接管到密态查问向量后，和本地数据形成的𝑛维向量(𝐵1,𝐵2,…,𝐵𝑛)，进行点乘，失去𝐸(0·𝐵1+…+0·𝐵𝑖-1+𝐵𝑖+0·𝐵𝑖+1+…+0·𝐵𝑛)，发送给客户端;
• 客户端对查问响应密文解密，失去待查问的数据𝐵𝑖。

HE-based PIR 协定能够形象为四个子算法，即(Setup,Query,Answer,Extract)，如下图所示：

• SETUP: 服务端 将数据库中的数据转换为 HE 明文
• QUERY: 客户端依据查问 index，生成密态查问向量
• ANSWER: 服务端计算明文向量和密文向量的内积
• EXTRACT: 客户端应用私钥解密查问响应密文，失去查问数据

3.SealPIR 协定

HE-based PIR 基本原理中的协定，存在的问题是

查问申请的计算量和通信量都大，须要生成和发送𝑛个密文；服务端每个数据表示为一个 HE 明文，须要计算 n 为向量的内积，容易导致噪声太大，无奈解密

SealPIR 论文给出了解决下面的问题的方法：

3.1 将多个数据 pack 到一个 HE 明文

查问的 db_index 须要转换为 plaintext_index

假如数据库中数据长度为 288 字节(SealPIR 论文中给出的长度)，BFV 参数抉择：多项式次数 8192，明文模 16bit，举例说明一下 pack 的成果：

• 数据库中每条数据，须要 HE 明文多项式中个系数来示意𝐶𝑒𝑖𝑙(288*8/16)=144。
• HE 一个明文多项式能够蕴含𝐹𝑙𝑜𝑜𝑟(8192/144)=56 调数据库数据。
• 对数据库的查问 db_idx，须要转换为明文的查问 plain_index=𝑑𝑏𝑖𝑑𝑥/56。
• 用户失去查问相应密文，通过私钥进行解密，失去 HE 明文，将 HE 明文对应的系数进行组合，失去真正查问的数据。

3.2 将查问向量压缩到一个密文

显著缩小通信量，服务端减少一个额定的 Expand 操作失去查问密文向量。
查问向量 (0,…,0,1,0,…,0) 压缩到一个 HE 明文多项式为例，查问向量中的每个重量对应为 HE 明文多项式中的系数。
𝑎0+𝑎1𝑥+…+𝑎𝑁-2𝑥𝑁-2+𝑎𝑁-1𝑥𝑁-1=𝑥𝑞𝑢𝑒𝑟𝑦_𝑖𝑛𝑑𝑒𝑥, 其中：𝑎𝑖=0,𝑖≠𝑞𝑢𝑒𝑟𝑦_𝑖𝑛𝑑𝑒𝑥，𝑎𝑖=1,𝑖=𝑞𝑢𝑒𝑟𝑦_𝑖𝑛𝑑𝑒𝑥。
对查问明文进行加密，失去𝐸(𝑎0+𝑎1𝑥+…+𝑎𝑁-2𝑥𝑁-2+𝑎𝑁-1𝑥𝑁-1)=𝐸(𝑥𝑞𝑢𝑒𝑟𝑦_𝑖𝑛𝑑𝑒𝑥)。
服务端接管到查问密文后，执行 Expand 算法，失去查问密文向量：(𝐸(0),…,𝐸(0),𝐸(1),𝐸(0),…,𝐸(0))。还是以下面 packing 的参数举例，每个 HE 明文能够 pack 56 个数据库数据，客户端查问时，将 db_index 转换为 plain_index，即对 HE 明文数据库进行查问，最多能够查问 8192 个 HE 明文，转换成数据库数据，最多能够查问 8192*56=458752 条数据，不能满足理论业务中的需要。
为了满足理论将查问向量压缩到多个 HE 明文来示意查问向量，对于百万数据来讲，须要𝐶𝑒𝑖𝑙(1000000/8192)=123 个 HE 明文，对应 123 个 HE 密文，能力示意百万数据的查问向量。为了进一步压缩查问密文的数量，能够应用上面的多维示意办法。
Expand 算法的详细描述和证实能够参考 ACLS18 论文中的内容。

3.3 将数据库一维向量转换为多维向量

二维查问时将数据库数据表示为√𝑛*√𝑛的矩阵，缩小查问向量

以下面 packing 的参数举例，将数据库示意为 2 维数据时，通过两个查问密文能够查问的数据量是 8192819256≈37 亿，曾经能满足绝大多数的数据库查问工作。数据库数据量为𝑛，通过 packing 后失去 HE 明文数量为𝑛′，𝐹是密文扩张因子，二维查问流程如下：
服务端：

• 将 HE 明文示意为√𝑛′*√𝑛′的矩阵𝑀，其中√𝑛′<8192。
• 𝑉𝑐是密文查问列向量，𝐴𝑐=𝑀·𝑉𝑐，其中𝐴𝑐是√𝑛′ * 1 的密文列向量。
• 将𝐴𝑐中每个密文拆分为𝐹份明文多项式，失去√𝑛′ * 𝐹矩阵𝐴𝑆𝑐。
• 𝑉𝑟是密文查问行向量，𝐴𝑆𝑇𝑐·𝑉𝑟，𝐹 * 1 失去的密文向量。

客户端：

• 客户端收到𝐹个密文向量，应用私钥𝑠𝑘解密，将其组合成密文𝐸𝑛𝑐(𝑀[𝑟,𝑐])，对应用私钥𝑠𝑘解密𝐸𝑛𝑐(𝑀[𝑟,𝑐])失去真正的查问 HE 明文𝑀[𝑟,𝑐]，对 HE 明文𝑀[𝑟,𝑐]中对应的系数进行组合，失去真正查问的数据。

服务端为了防止进行密文乘以密文的同态运算，第 3 步中将密文拆解成𝐹个明文进行操作，最初服务端发给客户端的查问响应是𝐹个密文，在多项式次数 8096 时，𝐹≈26，因而，服务端发给客户端的查问响应音讯太大，这也是 SealPIR 次要的问题，后续的文章，次要指标是缩小查问响应音讯，在前面的性能比照中能够看到。

3.4 通过一次进行多个查问升高整体性能开销

SealPIR 论文中还给出了通过 PBC(probabilistic batch code)将数据库中的内容分成若干 batch，同时执行 k 个查问时，别离对不同的 batch 进行查问，升高整体的性能开销。论文给出了基于 CuckooHash 的 PBC 结构计划。

CuckooHash 的 hash 数为 3，bin 数量为 1.5𝑘，k 为同时查问的数量。
服务端 预处理：

• 对 DB 中 n 个 index，别离计算 cuckooHash 的 3 个 Hash，失去 3 个 bin_index, 将 (db_index, data) 插入到 3 个 bin_index 中。

客户端 预处理：

• 对 DB 中 n 个 index，别离计算 cuckooHash 的 3 个 Hash，失去 3 个 bin_index, 将 (db_index) 插入到 3 个 bin_index 中。
• 将 k 个查问，通过 cuckooHash，插入到𝑏=1.5𝑘个 bin 中，对空的 bin 进行随机填充。
• 对每个 bin 执行 PIR，共计 b 个 PIR，每个 PIR 的 index，是客户端理论查问的 data_idx，在 bin 中的索引。

从上图中能够看到，客户端生成的是 CuckooHashTable 和 SimpleHashTable 两张表，服务端生成的 SimpleHashTable。客户端和服务端 SimpleHashTable 的差异在于，服务端 SimpleHashTable 有理论待查问的数据，服务端 SimpleHashTable 只是模仿了服务端插入过程，bin 中有 db_index。

3.5 SealPIR 的性能

SealPIR 论文 Figure 里给出 single_query 和 multi-query 的性能数据，多项式次数是 2048，明文模式 20bit，密文模式 60bit，数据长度 288 字节，数据量 220。

从下面能够看到，对于百万数据 (220) 单个查问的工夫是 3.3 秒左右，多个查问 (256) 性能能够降到 0.1 秒左右。

4. 其它改良协定

这里介绍一下 21 年的两篇 PIR 方面的文章：

• 发表在 USENIX21 年的[ALP+21]2[7]
• 发表在 CCS21 年的 OnionPIR:MCR21

[ALP+21]题目是《Communication–Computation Trade-offs in PIR》是计算量和通信量均衡的 PIR 计划，该计划显著升高了查问响应的通信量，从老本 (monetary) 的角度看比 SealPIR 升高了 35%。

OnionPIR 利用了 somewhat homomorphic encryption(SHE)最新的停顿，将两种 lattice-based SHE 计划 (BFV 和 RGSW) 组合在一起，升高了查问响应的大小和计算量。还设计了基于状态 (stateful) 的 PIR。

从下面的数据看到，尽管相应的改良协定对查问响应大小都有较大改良，但整体运行工夫方面和 SealPIR 差异不大，因为引入了更简单的算法，实现老本也会变得更高，综合来看 SealPIR 在理论利用中还是绝对较好的抉择。

参考文献
[1] [SealPIR] SealPIR: A computational PIR library that achieves low communicationcosts and high performance, 2020. https://github.com/microsoft/SealPIR.
[2] [ACLS18] S. Angel, H. Chen, K. Laine and S. Setty,”PIR with Compressed Queries and Amortized Query Processing,”2018 IEEE Symposium on Security and Privacy (SP), 2018, pp. 962-979, doi: 10.1109/SP.2018.00062.
[3] [CKGS95] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan”Private information retrieval”, in Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 41-50, Oct 1995.
[4] [BGI16] Elette Boyle, Niv Gilboa, and Yuval Ishai.Function secret sharing: Improvements and extensions. In CCS, 2016.
[5] [BFV12] Junfeng Fan and Frederik Vercauteren. 2012.Somewhat Practical Fully Homomorphic Encryption.IACR Cryptol. ePrint Arch. 2012 (2012), 144.
[6] [Brakerski12] Zvika Brakerski.Fully Homomorphic Encryption without Modulus Switching from Clas-sical GapSVP. IACR Cryptology ePrint Archive, 2012:78, 2012.
[7] [ALP+21] Asra Ali, Tancrède Lepoint, Sarvar Patel, Mariana Raykova, Phillipp Schoppmann, Karn Seth, and Kevin Yeo.Communication-computation trade-o s in PIR. In USENIX Security, 2021.
[8] [MCR21] M. Mughees, Hao Chen, Ling RenOnionPIR: Response Efficient Single-Server PIR, CCS’21.
[9] [CGN98] Benny Chor, Niv Gilboa, and Moni Naor.Private information retrieval by keywords.IACR Cryptology ePrint Archive, 1998:3, 1998.[10] [CHLR18] Hao Chen, Zhicong Huang, Kim Laine, and Peter Rindal.Labeled PSI from fully homomorphic encryption with malicious security.In ACM Conference on Computer and Communications Security, pages 1223–1237. ACM, 2018.
P.S. 文中素材来自公开发表论文，如有不妥，将立刻删除

🏠 隐语社区：
https://github.com/secretflow
https://gitee.com/secretflow
https://www.secretflow.org.cn（官网）

👇欢送关注：
公众号：隐语的小剧场
B 站：隐语 secretflow
邮箱：secretflow-contact@service.alipay.com