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

隐衷信息检索 (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 计划中计算量绝对较小，但通信量个别很大，大体规模是𝑛^𝑜(1)。

• 单服务器 PIR(SingleServer-PIR)

单服务器 PIR 个别基于公钥明码计划，特地是同态性质的公钥明码计划，安全性基于计算简单实践，也称为 CPIR。

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

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

单服务器 PIR 计划个别通信量较少，但计算量较大，且容易部署。

1.2.2 依照检索条件分类

• Index PIR/Dense PIR

服务端有 n 个元素的数据库𝐷={𝐷₁,𝐷₂,…,𝐷_𝑛}，用户查问第𝑖个元素，通过执行 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]^[5] 算法。

2.1 BFV 计划

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

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

明文空间是𝑅_𝑡=𝑍_𝑡[𝑥]/(𝑋^𝑁+1)，即：𝑎₀+𝑎₁𝑥+…+𝑎_𝑁-2𝑥^𝑁-2+𝑎_𝑁-1𝑥^𝑁-1，𝑎_𝑖∈𝑍_𝑡

密文由两个多项式 (𝑐₀,𝑐₁) 形成，𝑐₀,𝑐₁∈𝑅_𝑞=𝑍_𝑞[𝑥]/(𝑋^𝑁+1)。

密文扩张因子(Ciphertext expansion factor)，是指 SHE 加密后失去密文绝对明文的增大的比例，对于 BFV 算法，密文扩张因子𝐹=2𝑙𝑜𝑔(𝑞)/𝑙𝑜𝑔(𝑡)。

对于 128bit 平安，同态加密规范中给出了举荐参数。思考下面的密文扩大因子，明文模𝑡取绝对较大时，能取得较小的密文扩张；但进行密文同态计算时，明文模𝑡太大时，会导致噪声增长太快，明文模𝑡也不能获得太大。

SealPIR 中 BFV 参数中 N 和 q 抉择举例如下表：

SealPIR 中用到的同态运算：

• 密文加法：

    明文𝑝₁(𝑥)，𝑝₂(𝑥)对应的密文是𝑐₁和𝑐₂，𝑐₁+𝑐₂是𝑝₁(𝑥)+𝑝₂(𝑥)的密文。

• 明文乘密文：

    明文𝑝₁(𝑥)对应的密文是𝑐₁，𝑝₂(𝑥)·𝑐₁是𝑝₁(𝑥)·𝑝₂(𝑥)的密文。

• 替换：

    明文𝑝(𝑥)对应的密文是𝑐，对于奇数𝑘，𝑆𝑢𝑏(𝑐,𝑘)是𝑝(𝑥^𝑘)的密文。

    例如，𝑝(𝑥)=7+𝑥²+2𝑥³，𝑆𝑢𝑏(𝑐,3)失去𝑝(𝑥³)=7+{𝑥³}²+2{𝑥³}³=7+𝑥⁶+2𝑥⁹的密文。

SHE 的同态运算会引起噪声的增长，当噪声超过肯定限度时，无奈解密失去明文，所以要适当抉择 SHE 算法的参数，及管制同态运算的噪声增长。

2.2 HE-based PIR

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

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

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

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 明文多项式中的系数。

𝑎₀+𝑎₁𝑥+…+𝑎_𝑁-2𝑥^𝑁-2+𝑎_𝑁-1𝑥^𝑁-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]^[2] 论文中的内容。

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 字节，数据量 2 ²⁰。

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

4. 其它改良协定

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

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

[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: A computational PIR library that achieves low communication
costs and high performance, 2020. https://github.com/microsoft/…

2 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 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 Elette Boyle, Niv Gilboa, and Yuval Ishai.Function secret sharing: Improvements and extensions. In CCS, 2016.

5 Junfeng Fan and Frederik Vercauteren. 2012.Somewhat Practical Fully Homomorphic Encryption.IACR Cryptol. ePrint Arch. 2012 (2012), 144.

6 Zvika Brakerski.Fully Homomorphic Encryption without Modulus Switching from Clas-sical GapSVP. IACR Cryptology ePrint Archive, 2012:78, 2012.

7 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 M. Mughees, Hao Chen, Ling RenOnionPIR: Response Efficient Single-Server PIR, CCS’21.

9 Benny Chor, Niv Gilboa, and Moni Naor.
Private information retrieval by keywords.
IACR Cryptology ePrint Archive, 1998:3, 1998.

10 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. 文中素材来自公开发表论文，如有不妥，将立刻删除

欢送关注微信公众号：隐语的小剧场，获取更多隐衷计算常识分享！