隐衷信息检索(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个元素的数据库={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][5]算法。

2.1 BFV计划

[BFV12]将[Brakerski12][6]中的同态算法从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抉择举例如下表：

多项式次数明文模密文模
2048 54bit
409638bit109bit 2*36+37
819217bit218bit 243+344

SealPIR中用到的同态运算：

  • 密文加法：

    明文1()，2()对应的密文是1和2，1+2是1()+2()的密文。

  • 明文乘密文：

    明文1()对应的密文是1，2()·1是1()·2()的密文。

  • 替换：

    明文()对应的密文是，对于奇数，(,)是()的密文。

    例如，()=7+2+23，(,3)失去(3)=7+{3}2+2{3}3=7+6+29的密文。

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. 服务端接管到密态查问向量后，和本地数据形成的维向量(1,2,...,)，进行点乘，失去(0·1+...+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明文多项式中的系数。

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][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字节，数据量220。

从下面能够看到，对于百万数据(220)单个查问的工夫是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.文中素材来自公开发表论文，如有不妥，将立刻删除

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