Scalable Multi-Party Private Set-Intersection-解读 - PamShao

本文记录阅读该paper的笔记。

摘要#

本文给出两种MPSI协议，采用的是星型拓扑结构，即有一个leader，需要和其他参与者交互。优点是并非所有各方都必须同时在线：

（1）能抗半诚实攻击

• 通信复杂度与输入数据集大小呈线性关系；
• 计算复杂度是leader方输入数据的二次关系，其他参与者的输入集大小呈线性关系，后面可以使用两种hash可以消除此消耗。

（2）能抗恶意攻击
通信复杂度降为O((n2+nmMAX+nmMINlogmMAX)k)bit，其中mMAX和mMIN分别为n个参与者的输入最大量和输入最小量

另外上面提到本文的半诚实方案是基于【FNP04】文章改进的，【FNP04】是最早提出MPSI的【Efficient private matching and set intersection-2013】，两方协议是：

画成图表示就是：

和下面介绍基于不经意多项式计算（OPE）的图是一样的。

介绍#

MPSI#

MPC的安全性通常是通过两种对抗模型来证明的：
（1）半诚实模型
敌手遵循协议执行，但会试图从协议中获取更多信息。
（2）恶意模型
敌手在多项式时间内进行攻击

协议的优劣最根本的衡量方法就是计算消耗和通信消耗，MPSI主要分为两个方向：
（1）改进协议，计算任意布尔/算术电路
（2）协议能计算特定的函数，例如：计算k个相同元素，模式匹配和搜索问题，集合求交等

2PC-PSI#

给出两种方法解决PSI问题：
（1）基于不经意多项式计算（OPE）

其中，需要用同态加密（乘法和加法），但是这是两方的PSI

（2）承诺不经意PRF计算

这里只使用PRF，来“隐藏”数据，安全性和性能有待确定。

（1）【Faster private set intersection based on OT extension】【Scalable private set intersection based on OT extension】给出了基于OT和布隆布过滤器的半诚实PSI协议
（2）【Improved private set intersection against malicious adversaries】给出基于OT和布隆布过滤器的抗恶意攻击PSI协议
（3）【Practical private set intersection protocols with linear com- plexity】【Linear-complexity private set intersection proto- cols secure in malicious model】【(if) size matters: Size-hiding private set intersection】使用了ROM（随机预言机）模型
（4）【When private set intersection meets big data: an efficient and scalable protocol】基于OT extension和混淆不隆过滤器设计的

上面方案很少设计多方，都是两方间的PSI

MPC-PSI#

上面的这三个方案，都是多方PSI，但通信复杂度高，对于大数据难以应用，效率低下。

其中【Multiparty computation from some- what homomorphic encryption】是在预处理阶段使用SWHE；【MASCOT: faster malicious arithmetic secure computation with oblivious transfer】在离线阶段计算，避免了不必要的在线计算量。

本文主要是设计了一个多方PSI协议，但是可以通过两方PSI实现多方PSI，能避免通信的二次开销。

半诚实#

采用具有加法同态性质的门限公钥密码方案，其中leader方输入的数据集可以很小，并将其数据进行hash，并提供两种hash方法：
（1）simple hashing
（2）balanced allocation hashing
使用这两个hash，通信量几乎相似，计算量（2）更优，且该动起来更复杂！

恶意#

预备知识#

基本符号#

困难问题#

DLIN问题#

即给出p,g,gx,gy,gxr,gys,难以区分gd和gr+s。

DDH问题#

即给出p,g,gx,gy,难以区分gz和gxy。

双线性对#

公钥加密（PKE）#

IND-CPA安全#

这里的history是什么意思？

加法同态性的公钥加密方案#

可以看到这里的“加法同态”是：c1∗c2=E(m1+m2)

门限密码#

具有加法同态性的ElGamal门限密码方案#

（1）原始ElGamal方案

（2）门限ElGamal

需有多个私钥联合解密，增加了一个FDecZero函数，是判断一个密文是否是0加密的。另外为了验证私钥的正确性，还需要ZKP.

hash函数#

方案的计算量主要是在P1计算上，至少需要m1∗mi比较，其中i∈[2,n]。为了减少计算量，使用hash函数，各方将自己的数据（item）映射/插入到B个不同的bin中。

只有映射在相同的bin才能比较，所以比较的次数减少为P1的输入数量*一个bin中能装的最大item数量。（这里也能看出，一个bin是可以存放多个item）

simple hash#

这里使用一个hash函数，即h，将m个item插入到B个bin中，其中每个bin的容量最大为M，即一个bin中最多能存放M个item。

balanced allocation hash#

这里使用了两个hash函数h0(),h1()，将m个item插入到B个bin中，其中每个bin的容量最大为M。

这里两个hash函数都使用了？还是选取一个使用？

半诚实模型协议#

（1）这是2PC协议：

• P2获得私钥SK。
• P2计算出多项式Q(.)：即Q(x)=(x−x21)...(x−x2m2)，并将系数加密发送给P1。
• P1对于每一个元素x1j∈X1，同态计算rj∗Q(x1j)+x1j，并将结果发送给P2。
  注意：这里涉及到（密文明文、密文+密文、密文+明文），密文明文可以转换为明文+明文的加密。
• P2收到后，解密每个结果，如果结果在X2中，则说明是在交集中，否则不在。

另外，上面是P2拥有私钥，P2加密的系数，P1只进行密文计算，P2解密结果，并判断。
（2）首先对2PC协议改进：

这里说，P2的功能不变，即产生多项式，加密系数；各方的密钥(PK,SKi)；对于P1中的元素x1j∈X1，同态的计算rj∗Q(x1j)；P1的功能就是聚合多项式计算和得出交集；这里把改造后的协议，各方的消息的发送表示为πjFNP,j∈(1,2)。

上面是改造后的两方协议，其中P2生成多项式，加密系数，P1同态的计算多项式，并联合P2一起解密。下面完整协议中需要使用这个两方协议构造多方协议，即P1还是同态的计算多项式，而其它方则扮演P2的角色，生成多项式，加密系数，并最后和P1一起解密！
（3）完整的多方PSI协议

完整的协议，分为三部分：
第一，各方运行πSHGEN，协商出一个公钥，且不会泄露出各方的私钥。(意思就是各方都有一个私钥，这满足前面提到的门限加密)
第二，P1使用改进后的2PC协议和各方交互得到系数密文。（也就是加密的Q(xi_j)系数）第三，各方执行\pi _{DecZsro}^{SH}，P_1$得到所有的交集。

下面详细看：
输入：各方Pi的输入集合Xi=(x11,...,x1m1)，集合大小为m1，其中i∈[1,n]
第一：各方一起运行πSHGEN，得到一个公钥PK和每人一个私钥(SK1,...,SKn)
第二：P1和各方（即P2,...,Pn）逐一执行协议（π1FNP,π2FNP），得到结果密文(ci1,...,cimi)，其中i∈[2,n]（这里如果是系数的话，不是应该有mi+1个么？）
意思就是，各方Pi生成多项式Q(.)，然后加密系数，将其发给P1，P1再将所有的加密系数“整合”为一个加密的Q1()，并对于每一个元素同态的计算rj∗Q1(x1j)。
第三，就是计算交集。
从各方收到结果密文后，P1计算:

其中mMAX=max(m2,...,mn)，画个图理解一下：

这里相当于P1计算Q1=Q2()+...+Qn()（别忘记了，这里使用的加法同态是：c1∗c2=E(m1+m2)）

这里的意思是，各方计算出Qi()，然后加密系数，发送给P1，P1再将这些密文系数对应相加得到Q1()，再将P1的集合元素代入，计算出m1个结果，再将其解密，根据是否为0判断是交集！（和之前的协议相反，这里的加密是在各方进行，解密是在P1执行，且需要联合各方（多个私钥））。

分析一下同态计算：
将多个加密的系数“整合”在一起，其实是想Q2()+Q3+...+Qn()，根据加法同态性，需要将密文系数相乘达到“相加”的效果。那么现在得到了Q1()的密文系数，代入P1的集合元素（明文），计算ri∗Q1(x1j)，这里面涉及到密文明文(系数乘元素)，密文+密文（计算后的各项相加），明文密文（随机数乘最终结果）。

灵魂疑问：仅“加法”同态能实现么？

通信和计算复杂度#

协议消耗主要是在门限加/解密（同态计算）和2PC协议。
（1）对于改进的2PC协议，通信消耗是在要传输m2+1个密文；对于P1的计算量又是巨大的，需要为每个元素都要执行O(m2)的指数运算，对于全部的元素m1，则总共需要O(m1.m2)的指数元素。
（2）为了减少计算量，会使用hash函数，给出两种：simple hashing和balanced allocation hash

使用simple hash#

在该方案中，各方使用hhash函数，以P2为例，每个bin中最多存储M个数，可以看成一个M次的多项式的根存储在一个bin中，如果不够M个，则可以填充0，结果就是有B个bin，即B个次数为M的多项式，m2个非零根。

对于P1来说，将每一个元素x1j插入到一个bin中，然后计算对应的bin，就相当于计算多项式。

对于通信复杂度，需要发送B.Mi=O(mi)个密文，其中Mi是用于分配P1输入的bin大小在与Pi方交互时。
对于计算复杂度，P1对于每一方需要O(Mi)的指数运算，总共需要执行O(m1∗∑iMi)的指数元素。

这里存在一个疑问：Mi和mi有什么区别？mi是Pi方的集合大小，Mi是P1与Pi交互时，P1的输入对应的一个bin的容量。

使用balanced allocation hash#

这里使用两个hash函数，bin的个数B和最大容量M和simple hash不一样。
以P2为例，将其m2个元素插入到B个bin中的一个，其中每一个bin的最大容量为M，这里是将每一个bin看作是一个M次的多项式。形成多项式Q1(),...,QB()，Qi()的根在第i个bin中存储。

当P1收到所有的加密多项式，同态计算出r0j∗Qh1(x1j)和r1j∗Qh1(x1j)，将其相乘，解密后为0，则表明x1j为交集元素。

恶意模型协议#