高效且恶意安全的三方小集合隐私交集计算协议

张 蕾 贺崇德 魏立斐

1(上海海洋大学信息学院 上海 201306) 2(上海海事大学信息工程学院 上海 201306)

隐私集合交集(private set intersection, PSI)技术是安全多方计算技术的重要应用之一.经典的PSI协议允许2个参与方各自持有自己的私有集合，在协议结束时两方或其中一方作为接收者，获得两方集合的交集，且不会泄露除交集之外的任何元素信息[1-2].作为重要的密码学工具，PSI也被广泛应用于人工智能和数据挖掘的安全领域，如隐私保护数据挖掘[3-4]、私有通讯录查找[5]、新冠接触者追踪[6]以及衡量在线广告转化率[7]等.在数据共享的时代背景下，多方参与PSI的场景需求更加广泛，例如在社交软件的隐私联系人查找功能中，可查找多个用户的共同好友即属于多方参与PSI的应用场景.

目前大多数高效的PSI方案都是基于不经意传输(oblivious transfer, OT)协议[8]构建，得益于高效的OT扩展技术，各方可以通过少量的公钥操作生成大量的OT协议实例，使得基于OT的PSI协议所需要的公钥操作数量仅与安全参数有关，而与集合大小无关，计算成本较低，从而高效地构造PSI协议[9-15]，但其通常具有一定的固定成本，往往仅适合大集合(210～220个元素)场景，而在小集合(500个元素或者更少)场景下优势不够明显.此外，虽然基于OT的协议计算效率较高，但同时带来了巨大的通信成本，而在某些实际场景下通信成本比计算成本更重要[16].

基于密钥协商构造的PSI协议[17-20]一般通信量较低，在弱通信场景中具有较大优势.例如，采用目前最有效的1-out-of-2 OT[21]构建PSI，128个基本OT需要花费384个群元素进行通信以及640次指数运算，其开销比集合大小为200的基于Diffie-Hellman密钥协商的PSI还要昂贵[16].从实用成本的角度，在网络中添加CPU比扩大网络容量要便宜的多，因此，在谷歌内部部署PSI功能时选择了基于Diffie-Hellman密钥协商的PSI[16].此外，基于RSA和全同态加密的协议也具有很低的通信成本[22-26]，常被用于弱通信场景中，但其采用大量繁重的公钥操作，产生了巨大的计算成本，导致非常低的运算效率.

小集合交集计算是PSI协议的一个典型场景，具有广泛的应用.例如，为了增强了苹果手机的隔空投送功能，文献[27]通过对用户的整个地址薄(几千项)和另一个用户的个人标识符(电活号码或电子邮箱，可能是10项)进行PSI.又如，各方可能希望利用可用日历时间的PSI来安排在线会议时间，即各自可用时间集合(按小时划分，此时集合规模约为360小时[20])的交集.对于此类输入大小的集合，基于密钥协商的PSI是计算成本最低的.Rosulek等人[20]在CCS 2021上采用Diffie-Hellman密钥协商和多项式插值技术，在小集合情况下实现了迄今为止最快的PSI方案.然而，文献[20，27]所述的基于密钥协商的方案都仅适用于具有2个参与方的场景.PSI协议的隐私性要求除交集之外的任何信息都无法被泄露，而两方协议直接扩展到多方将不可避免地泄露交集之外的两两相交的部分，导致两方协议无法直接扩展到多方.

综上，本文提出了一个基于密钥协商的三方恶意安全PSI协议，能抵抗任意2个恶意参与方合谋，实现了现有多方PSI中最低的通信量；特别地，在小集合场景下，保持了较高的运算效率.该协议非常适合三方小集合场景，例如为了签订合同，投资方、劳务方和中介方希望利用1个月内的可用时间安排会议，需要3个参与方利用各自可用时间的集合，考虑存在合谋的情况下，不泄露各方集合信息时求出交集.本文的主要贡献有2个方面：

1)提出了一个基于密钥协商的三方PSI协议，实现了半诚实的安全性，允许任意2个参与方合谋，并在此基础上提出了恶意安全的三方PSI协议.利用模拟范式，证明了协议在半诚实和恶意安全模型下合谋时的安全性.

2)通过实验仿真，在大集合场景，相比现有基于OT的多方PSI协议，本文协议具有最优的通信轮数，通信量降低了89%～98%；在小集合场景，相比适用弱通信网络的同类PSI协议，具有最优的运行时间和通信负载，其中运算速度比依赖于同态加密的PSI协议快10～25倍.

1 相关工作

PSI作为安全多方计算的热点问题已经得到了快速的发展.经典的PSI协议包含2个参与方，已经达到非常高的效率.最早的PSI协议采用朴素哈希的方式，即先对集合元素求哈希，并通过对哈希值的对比得出交集，这种方案是十分高效的，但容易受到碰撞攻击.为了解决碰撞攻击的问题，需要采用安全对比的方法.对于持有m个元素的集合的双方，为了求出交集元素，最坏的情况需要进行O(m2)次比较.通过将元素映射到长为n的布隆过滤器，比较次数可减少到O(nlbn).随着PSI技术的成熟，通过布谷鸟哈希、不经意伪随机函数和高效的OT扩展等技术，一些PSI协议实现了O(n)的计算和通信复杂度.

最新对抗半诚实敌手的两方PSI协议来自文献[9].文献[9]设计了一种基于OT技术的安全字符串相等性测试协议，仅使用OT[8]、哈希函数、对称密钥加密操作和按位操作来构建协议，因此计算效率很高.文献[10]基于OT扩展和多项式编码技术实现，除基于昂贵的RSA和FHE的协议之外，该协议在已有的两方PSI中具有最低的通信.文献[11]提出了一种高效的多点不经意伪随机函数(oblivious pseudo-random function, OPRF)，实现了计算和通信之间更好的平衡，在具有中等带宽的网络中达到了所有已知协议中最高的运行效率.最新恶意安全两方PSI协议是文献[28]和文献[29]，它们分别基于高效的OT扩展和向量OLE[30].当集合比较大(例如n>220)时，文献[29]非常高效，但它具有较高的固定成本，这使得它在较小的集合场景中效率较低.

随着隐私集合交集技术的成熟及其在实际应用中的普及，2个参与方已经不能满足应用需求，多参与方的场景更加广泛，但目前仅有少数方案适用于此类场景.第1个高效的多方PSI协议由Kolesnikov等人[31]提出，该协议同样使用OT扩展实现，他们为协议设计了2个版本，分别实现了半诚实及增强半诚实(可能在执行开始前改变攻陷参与方的输入)的安全性.Efraim等人[32]巧妙地结合了来自半诚实安全的多方PSI[33]和恶意两方PSI[34]的结果，提出了第1个恶意安全的多方PSI，但该协议需要传输混乱布隆过滤器(garbled Bloom filter, GBF)进行通信，这带来了巨大的通信负担.Nevo等人[35]首先使用高效的不经意键值存储(oblivious key-value stores, OKVS)技术[36]和高效不可信云辅助两方PSI实现了迄今为止最快的恶意多方PSI协议，但该协议在恶意参与者合谋的情况下是不安全的，会泄露其他方的集合元素信息.利用不经意零共享技术和不经意可编程伪随机函数(oblivious programmable pseudorandom function, OPPRF)，Nevo等人[35]在第2个协议中实现了允许任意t个参与方进行合谋的恶意PSI协议，实现了已有恶意协议中最好的计算和通信效率.

基于密钥协商构建PSI协议是隐私集合交集计算的经典思路，也是本文工作的重点.最早的基于密钥协商的PSI协议可以追溯到1999年提出的文献[17]，并实现了半诚实的安全性，但由于该协议完全按照Diffie-Hellman协议设计，导致其在半诚实安全下变体的设计空间非常有限.之后的研究中，基于Diffie-Hellman的PSI协议在恶意敌手存在情况下的安全性得到增强.文献[18-19]提出了高效且恶意安全的PSI方案，实现了线性的通信复杂度和线性的计算复杂度.最新的文献[20]利用多项式插值将参与方集合元素映射到Diffie-Hellman密钥协商的密钥空间，通过对比输出密钥得出交集，分别实现了半诚实和恶意安全性，并极大地提高了基于密钥协商的PSI的效率，尤其是在小集合的情况下，该方案提出的恶意安全协议甚至比同类半诚实安全协议的运算速度快，同时通信成本降低了40%.但上述基于密钥协商的PSI协议都仅适用于两方，且无法直接扩展到多个参与方的场景.

2 预备知识

2.1 安全模型

安全多方计算的安全模型可以分为半诚实模型和恶意模型2种.在半诚实模型下，敌手完全遵循协议的执行过程，但可能会记录协议执行过程中的所有数据，并试图从协议执行过程数据中获取额外信息；在恶意模型中敌手不仅可以通过协议过程的数据推测敏感信息，还可以不遵循协议规范，拒绝参与协议、修改隐私的输入集合信息或者提前终止协议的执行等.本文提出的协议分别在半诚实模型和恶意模型下可证安全而不泄露任何信息，且允许任意2个参与方的合谋.

针对安全多方计算的协议普遍采用模拟范例进行证明，将理想状态下引入可信第三方的安全多方计算协议的理想协议与真实协议进行对比，如真实协议的视图与理想协议的视图是不可区分，则真实协议未泄露更多信息，进而证明协议是安全的.在半诚实模型中，模拟器仅需根据协议规则模拟敌手视图，并证明与真实协议的视图是不可区分.在恶意模型中，需要进一步考虑敌手的恶意行为，对恶意参与方进行输入提取，并考虑其对诚实参与方输出的影响严格进行模拟，最终证明模拟器与真实协议的视图不可区分.

本文协议包含3个参与方，可以抵抗任意两方的合谋攻击.在三方协议中，需要对任意两方合谋进行模拟，证明模拟器视图与真实协议视图计算不可区分.

定义2.恶意模型安全性.设f是理想状态下的三方协议，π为真实协议.如果对于现实模型中所有使用概率多项式时间算法的敌手A都存在一个理想模型中使用概率多项式时间算法的模拟器S，使得

即敌手A在真实协议中得到的信息与理想模型得到的信息是不可区分，则称协议π在恶意敌手存在的情况下安全地计算了f，其中x,y,z为参与方的输入，n为安全参数.

2.2 三方PSI的理想功能

3个参与方各自拥有自己的私有集合，通过联合执行三方PSI协议，接收方获得3个参与方集合交集元素的信息，除此之外各参与方无法获取任何额外信息.另外，敌手会设置状态abort，若abort=1，则协议会中止.特别地，在半诚实模型中，敌手总是设置abort=0.图1描述了三方PSI的理想功能，其中[n]表示整数集合{1,2,…,n}.

2.3 理想置换

在理想置换模型中，各方可以访问{0,1}n上的随机置换Π及其逆置换Π-1，在安全性证明中，模拟器可以观察理想置换Π,Π-1上所有查询并编码响应，为模拟敌手的视图提供帮助.目前，理想置换已被用于实现混乱电路和OT协议中哈希函数[37-38].理想置换也可以用于设计安全的PSI协议，文献[20]利用理想置换分别实现了半诚实和恶意敌手的安全性.

2.4 双线性配对

双线性配对广泛应用于密码方案的设计[39].设G是素数q阶加法循环群，GT是q阶乘法循环群.映射e:G×G→GT满足下列性质，则被称为一个双线性配对映射：

1)双线性.对于任意的P,Q∈G，a,b∈*p，则有e(aP,bQ)=e(P,Q)ab.

2)非退化性.存在P,Q∈G，使得e(P,Q)≠1GT，其中1GT是GT中的单位元.

3)可计算性.对于任意的P,Q∈G，存在有效的多项式时间算法可以计算e(P,Q).

本文方案的安全性主要基于判定性双线性(decision bilinear Diffie-Hellman, DBDH)假设:对于P∈G，给定(P,aP,bP,cP)和元素h∈GT，判断e(P,P)abc和h是计算不可区分的，即对于任意的多项式时间算法F及任意的n，均有:

Pr[F(P,aP,bP,cP,e(P,P)abc)=1]-

Pr[F(P,aP,bP,cP,h)=1]≤ε(n),

其中ε(n)是参数为n的可忽略函数.

2.5 三方密钥协商协议

本文设计的三方PSI协议是基于文献[40]提出的三方Diffie-Hellman密钥协商协议.文献[40]的协议仅需要一轮通信即可构建一个共享的密钥.三方密钥协商协议过程如图2所示.该协议包含3个参与方A,B,C，给定双线性配对e:G×G→GT，其中G是素数q阶加法循环群，GT是q阶乘法循环群.P是G的一个生成元，A,B,C各随机选择a,b,c∈*p，分别广播aP,bP,cP.根据双线性配对性质，三方均可以计算共享密钥K=e(bP,cP)a=e(aP,cP)b=e(aP,bP)c=e(P,P)abc.

3 三方隐私集合交集计算协议

本节首先介绍了第一个半诚实版本的协议1(PSI-s)，主要思想来源于三方密钥协商[40]，仅需两轮通信.协议要求各参与方是半诚实的，同时允许任意两方合谋.通过改进半诚实版本的协议，在协议2(PSI-m)中达到了恶意攻击安全.在协议描述中，用K表示密钥协商中输出密钥空间，κ表示计算安全参数，λ表示统计安全参数.

3.1 半诚实三方隐私集合交集协议(PSI-s)

3.1.1 基本协议

基于密钥协商的三方PSI协议的主要想法是将参与方的元素与输出密钥用插值多项式联系起来：若元素在集合的交集中，则输出相同的密钥，否则将输出不同的密钥，这个过程不会泄露任何信息.

协议模型结构如图3所示.3个参与方A,B,C，其中参与方C作为接收者，在协议执行结束之后获得三方集合交集的元素信息.协议将集合元素映射到密钥协商后的公共密钥空间上，若三方获得的公共密钥相同，则可判断对应的元素在交集中，否则该元素不在交集中.事实上，将元素映射到3个参与方的密钥空间是不必要的，本节中提出的协议仅仅将元素映射到参与方B,C的密钥空间，这大大降低了协议所需的计算量和通信量.

半诚实三方PSI的完整协议在协议1中给出.参与方A通过插值多项式，将所有xi∈X与用于生成共享密钥的参数aiP进行关联，并通过理想置换Π-1(aiP)使得生成的多项式与随机选取的同阶多项式不可区分，从而保证了集合X中元素的隐私性.参与方B和C通过对来自A的多项式求响应，并最终求出共享密钥，分别隐含了X∩Y和X∩Z的信息.最终C通过对比共享密钥，即可得出三方集合交集，不会泄露除交集外的任何元素信息.

协议1.基于密钥协商的半诚实三方PSI(PSI-s).

参数：3个参与方A,B,C；有限域F，循环群G和GT，P是G的生成元；理想置换Π,Π-1：F→F;双线性配对e:G×G→GT；随机密钥空间|K|≥2λ+2 lb n.

输入：参与方A,B,C分别输入集合X,Y,Z；

输出：接收方C输出集合X∩Y∩Z.

协议过程如下：

1)B随机选择b∈*p计算bP发送给C，同时C

随机选择c∈*p计算cP发送给B.

2)A随机选择n个随机值{a1,a2,…,an}∈*p，插值多项式Q(xi,Π-1(aiP))并发送给B,C.

3.1.2 正确性分析

因此，对于交集中的元素xi=yi=zi，有：

e(P,P)aibc=e(aiP,cP)b=

3.1.3 安全性证明

定理1.假设Π,Π-1是理想置换，协议1在半诚实模型下安全地实现了三方隐私集合交集计算，其安全性归约于判定性双线性问题的困难性假设.

证明.在本文的协议中，任意2个参与方合谋即为最大的合谋攻击，因此只需要证明协议对任意2个参与者合谋时是安全的，则对于任意单个半诚实参与方也是安全的.分3种情况分别讨论.

1)半诚实的参与方A与B合谋情况

在参与方A,B合谋的情况下，敌手从诚实参与方C接收到的唯一消息是cP，由于c是在*p中随机选取的，cP和G中随机值是不可区分的.因此，在A,B合谋的情况下，A,B未获得任何有用信息.

2)半诚实的参与方B与C合谋情况

在参与方B,C合谋的情况下，敌手获得的消息是来自诚实参与方A的多项式Q(·)，因Π是理想置换，每一个Π-1(aiP)值与随机值是不可区分的，因此Q(·)是一个输出随机均匀的多项式而与输入x无关，Q(·)与随机选取的同阶多项式是无法区分的，B,C未获得任何有用信息.

3)半诚实的参与方A与C合谋情况

设计以下模拟器S来证明它和真实协议是不可区分的.定义混合序列hybridh：步骤①S按照协议规则诚实地发送bP给参与方C；步骤②对于zi∈(X∩Y∩Z)∪{zi|i≥h}，模拟器计算ki=e(Π(Q(zi)),bP)c，其中Π由参与方A决定；步骤③对于所有其他的zi∈Z，选择随机值作为ki的输出；步骤④S生成集合K.

此时，hybrid0即为真实协议，而hybridn即为设计的模拟器.在hybridn中只利用了交集X∩Y∩Z中的元素生成信息，所以不会泄露不在交集中元素的任何信息.

为了证明hybridh和hybridh+1是不可区分的，修改上述混合序列步骤③为：若zh∉X∩Y∩Z,模拟器计算kh=k*；对于所有其他的zi∈Z，选择随机值作为ki的输出.

此时，上述混合序列在k*被赋予不同的值时分别对应于hybridh和hybridh+1.在hybridh中，k*被计算为k*=e(Π(Q(zi)),bP)c，而在hybridh+1中k*被赋予随机值.根据参数选取的随机性和双线性配对的性质易知，hybridh和hybridh+1是不可区分的，从而证明了模拟器和真实协议也是不可区分的.

综合1)～3)知，协议1在半诚实模型下安全地实现了基于密钥协商的三方隐私集合交集计算且能够抵抗合谋攻击.

证毕.

3.2 恶意安全三方隐私集合交集协议(PSI-m)

3.2.1 基本协议

协议2.基于密钥协商的恶意三方PSI(PSI-m).

参数：3个参与方A，B，C；有限域F，循环群G和GT，P是G的生成元；理想置换Π,Π-1：F→F;双线性配对e:G×G→GT；抗碰撞的哈希函数H1：{0,1}*→F,H2：{0,1}*×GT→{0,1}2κ；随机密钥空间|K|≥2κ.

输入：参与方A，B，C分别输入集合X，Y，Z；

输出：接收方C输出集合X∩Y∩Z.

协议过程如下：

1)B随机选择b∈*p计算bP发送给C，同时C

随机选择c∈*p计算cP发送给B.

2)A随机选择n个随机值{a1,a2,…,an}∈*p，并对每一个xi∈X求哈希值H1(xi).随后插值多项式Q(H1(xi),Π-1(aiP))发送给B,C.

3)B,C接收多项式，若多项式阶数小于1，则协议终止.

4)B计算输出密钥.B对每一个yi∈Y求哈希值H1(yi)，然后用H1(yi)对来自参与方A的多项式Q(·)求值，并计算对应的共享密钥值ki=e(Π(Q(H1(yi))),cP)b.

3.2.2 正确性分析

与3.1.2节类似，对于交集中元素xi=yi=zi有：

H2(zi,ki)=H2(zi,e(Π(Q(H1(zi))),bP)c)=

H2(zi,e(aiP,bP)c)=H2(zi,e(P,P)aibc)=

H2(yi,e(aiP,cP)b)=H2(yi,

e(Π(Q(H1(yi))),cP)b)=H2(yi,ki).

因此，满足H2(yi,ki)∈K的元素即是交集X∩Y∩Z的元素.

3.2.3 安全性证明

考虑到参与方的合谋情况，安全性证明分为3种情况，在定理2～4中分别讨论.

定理2.假设Π,Π-1是理想置换，协议2在恶意参与方B,C合谋的情况下是安全的.

证明.由于诚实参与方并未收到任何来自恶意参与方B,C的输入，所以在B,C合谋的情况下，不需要考虑敌手对诚实参与方输出的影响，也即不需要进行输入提取.因Π是理想置换，每一个Π-1(aiP)的输出值都是一个均匀随机的，因此多项式Q(·)与输入x无关，Q(·)与随机选取的同阶多项式是无法区分的.B,C未获得任何有用信息，从而证明了在恶意参与方B,C合谋的情况下，协议2安全地实现了隐私交集计算的功能.

证毕.

定理3.假设H1,H2是随机预言机，Π,Π-1是理想置换，则协议2在恶意参与方A,C合谋的情况下安全性归约于判定性双线性问题的困难性假设.

证明.首先刻画模拟器S的能力：

1)S诚实地扮演随机预言机H1,H2和理想置换Π±的角色.

① 对于所有敌手发出的查询H1(y)，若未查询过y，则S随机选取元素h1作为返回，并将(y,h1)记录在列表O1中；否则直接返回O1中的对应值.

② 对于每一个敌手发出的查询H2(y,k)，若未查询过(y,k)，则S随机选取元素h2作为返回，并将(y,k,h2)记录在列表O2中；否则直接返回O2中的对应值.

③ 对于每个查询Π-1(m)，若未查询过Π(f)，则S随机选取元素f作为返回，并将(f,m)记录在列表OΠ中；否则直接返回OΠ中的对应值.

4)S最终将K发送给敌手.

以下通过混合序列hybridh，证明了这个模拟协议与真实协议是无法区分的.

1)hybrid0.这是真实的交互，与参与方B按照协议规则诚实地运行，其中K定义为

K={H2(y,e(Π(Q(H1(y))),cP)b)|y∈Y}，

同时，列表O1，O2和OΠ也被生成.

2)hybrid1.与hybrid0唯一的不同是：在计算ki时，若存在y∈Y满足y∉O1但Q(H1(y))∈OΠ，则交互终止.这意味着敌手从未查询H1(y)，但Q(H1(y))却是它从Π-1输出的值.这种概率是可忽略的：对于任意f∈OΠ，多项式等式Q(·)=f至多有n个解且在F中均匀分布，因此至少有n/|F|概率满足Q(H1(y)=f).假设敌手对H1做了共q次查询，通过n个y∈Y和q个f∈OΠ，总概率为n2q/|F|，这是可忽略的.

3)hybrid2,i.对于每一个i∈[q]，对于形式为Π(f)=m的前i次查询中，若从未查询过Π-1(m)，则将f添加到集合Si.记Si是前i次查询中敌手没有的元素对应的Π的输出.显然Si和OΠ是不相交的，所以计算K为

K={H2(y,e(Π(Q(H1(y))),cP)b)|

y∈YandQ(H1(y))∉Si}.

最后在K中加入随机元素，直到|K|=n.

此后，hybrid2,i+1将hybrid2,i中的e(Π(Q(H1(y))),cP)b替换为随机值.根据DBDH假设可知，hybrid2,i+1和hybrid2,i是无法区分的.

4)hybrid3.重写了hybrid2,q，所有Π(f)=m都用Sq和OΠ表示，对于所有满足Π(f)=m的值必然属于这2个集合的其中之一，即Q(H1(y))∉Si等价于Q(H1(y))∈OΠ，因此K可以表示为

K={H2(y,e(Π(Q(H1(y))),cP)b)|

y∈YandQ(H1(y))∈OΠ}.

由hybrid1已知，若存在任何y∉O1但Q(H1(y))∈OΠ，则交互将终止.这意味着Q(H1(y))∈OΠ隐含着y∈O1.因此，K可以进一步改写为

K={H2(y,e(Π(Q(H1(y))),cP)b)|

y∈Y∩O1andQ(H1(y))∈OΠ}.

5)hybrid4.hybrid3基础上，诚实的参与方B查询H2以获得K.若一个H2查询是第1次查询，但结果在O2中，则协议终止.此类事件的概率是|O2|/|F|=n/|F|，是可以忽略的，则hybrid4与hybrid3是无法区分.

假设hybrid4维护了前面描述的列表O2，即(y,e(Π(Q(H1(y))),cP)b,k′)∈O2意味着敌手查询H2(y,e(Π(Q(H1(y))),cP)b)并得到输出密钥的随机预言机查询结果.由于参与者B只识别敌手已经向H2查询过的值，因此hybrid4可以写作：

K={k′|(y,e(Π(Q(H1(y))),cP)b,k′)∈O2|

y∈Y∩O1andQ(H1(y))∈OΠ}.

K={H2(y,e(Π(Q(H1(y))),cP)b)|

此时，hybrid4与模拟器的行为是相同的.

综上，模拟协议和真实协议是不可区分的，从而证明了在恶意参与方A,C合谋的情况下，协议2安全地实现了隐私交集计算功能.

证毕.

定理4.假设H1,H2是随机预言机，Π,Π-1是理想置换，则协议2在恶意参与方A,B合谋的情况下安全性归约于判定性双线性问题的困难性假设.

证明.首先刻画模拟器S的能力：

1)S扮演随机预言机H1,H2和理想置换Π±的角色同定理3.

2)在收到多项式Q(·)之后，S定义集合

3)在接收到来自敌手的K后，S定义集合

k′)∈O2andk′∈K}.

以下通过混合序列hybridh，证明了这个模拟协议与真实协议是无法区分的.

1)hybrid0.这是真实的交互，合谋方A,B与参与方C按照协议规则运行，交集可以表示为

{z∈Z|H2(z,e(Π(Q(H1(z))),bP)c)∈K},

同时，列表O1,O2和OΠ也被生成.

2)hybrid1.与hybrid0唯一的不同是：Π±的模拟.所有对Π和Π-1的新查询都以随机值进行响应.若Π或Π-1获得重复的输出，则交互将终止.因此hybrid1与hybrid0是无法区分的.

3)hybrid2.与hybrid1不同是：若存在z∈Z满足z∉O1但Q(H1(z))∈OΠ，则交互终止，即敌手从未查询H1(z)，但Q(H1(z))却是它从Π-1输出的值.这种概率是可忽略的.对于任意f∈OΠ，多项式等式Q(·)=f至多有n个解且在F中均匀分布，因此至少有n/|F|概率满足Q(H1(z))=f.假设敌手对它的预言机做了总共q次查询，通过n个z∈Z和q个f∈OΠ，总概率为n2q/|F|，这个概率也是可忽略的.若不终止，则意味着Q(H1(z))∈OΠ且z∈O1.因此输出形式改写为

{z∈Z|H2(z,e(Π(Q(H1(z))),bP)c)∈K

andQ(H1(z))∈OΠandz∈O1}.

4)hybrid3.诚实的接收者查询H2以获得输出，与hybrid2唯一的不同是H2如何模拟.若H2查询是第1次被查询但结果却在K中，则协议终止.此类事件的概率是|K|/|F|=n/|F|，这是可忽略的，因此hybrid3与hybrid2无法区分.

假设hybrid3维护了列表O2，即(z,e(Π(Q(H1(z))),bP)c,k′)∈O2意味着敌手查询H2(z,e(Π(Q(H1(z))),bP)c)并得到结果k′.由于C识别敌手已经向H2查询过的值，可记作：

{z∈Z|∃k′:(z,e(Π(Q(H1(z))),bP)c,k′)∈

O2andk′∈KandQ(H1(z))∈OΠandz∈O1},

等价于：

Z∩{x|∃k′:(x,e(Π(Q(H1(x))),bP)c,k′)∈

O2andk′∈KandQ(H1(x))∈OΠandx∈O1}.

Z∩{x|x∈O1andQ(H1(x))∈OΠ}∩

{y|∃k′:(y,e(Π(Q(H1(y))),bP)c,k′)∈

O2andk′∈K}.

综上，模拟器的行为和真实协议是不可区分的，从而证明了在恶意参与方A,B合谋的情况下，协议2依然安全地实现了隐私交集计算功能.

证毕.

4 协议性能与比较

4.1 实验环境与参数

本文使用C++实现了基于密钥协商的三方恶意隐私集合交集计算协议，并与同类方案进行了对比.实验环境为:Ubuntu 18.04.4 LTS, Intel®CoreTMi7-8750H CPU @2.20 GHz, 16 GB RAM.实验中采用带有固定密钥且分组长度为128 b的AES算法作为理想置换，并使用SHA2实例化必要的哈希函数.具体实现中采用了libOTe库以及libsodium库，最后利用PBC库提供的A类曲线(y2=x3+x)实现了双线性配对.所有计算均采用PSI元素长度为128 b，计算安全参数κ=128，统计安全参数λ=40.

4.2 性能评估与分析

小集合场景下的性能：本文分别对各参与方集合元素数量为24,25,26,27,28,29这6种情况对恶意隐私集合交集协议进行了仿真实验测试.

在实施过程中，协议的计算成本包括：参与方B和参与方C计算bP和cP，以及n个经过双线性运算的密钥输出；参与方A计算n个aiP.3个参与方对H1和Π±各进行n次查询；参与方B和C分别对H2进行n次查询；最后参与方A必须插值一个多项式，参与方B，C在n个点上对多项式求值，这都需要O(nlb2n)个域操作[41].由参与方C进行对比得出交集，各个参与方负载均衡.该协议的总通信成本包括：参与方B，C发送的bP和cP；用于描述多项式Q(·)的n个域元素；n个H2输出，每个2κ位.

表1展示了本文提出的恶意三方PSI协议的通信量和各阶段运行时间.本文的协议适合预计算，可将部分计算放在离线阶段进行.在实验测试性能时，本文将协议分为离线阶段和在线阶段：离线阶段主要是参数的生成以及参与方A的多项式插值的计算；在线阶段各方交互并得出交集.耗时为在线阶段和离线阶段的运行时间，通信量为所有参与方发送/接收数据的总和.从实验数据可以看出，本文提出的协议十分适用于参与方所具有的集合元素较少的情况.在集合元素较少的情况下，该协议具有较高的运算效率和极低的通信量；在集合元素较多的情况下，由于本文协议涉及双线性配对计算，所以效率有所下降。对比已有三方PSI协议，本文协议仍具有最高的通信效率。因此，本文协议适用于网络带宽和通信量均受限的场景.

Table 1 Communication and Running Time of Our Protocol in Small Set Scenarios

4.3 性能对比

表2展示了本文方案与相关工作的综合对比.其中n是集合中元素的个数.表2中的文献都可以实现三方PSI的计算.本文提出的方案分别提供了半诚实和恶意安全性，并且在任意两方合谋时都是安全的.此外，本文在2种安全模型下都实现了线性的通性复杂度和计算复杂度并且仅需要两轮通信交互.文献[31]、文献[43]以及文献[42]可提供半诚实的安全性.相比之下，本文协议的半诚实版本具有更低的通信轮数以及通信复杂度和计算复杂度，并允许任意两方合谋.

Table 2 Comparison of Related Semi-Honest and Malicious Three-Party PSI Protocols

文献[32,35,42,44-45]都可以在恶意敌手存在的情况下完成工作.文献[45]表明必须有指定的2个服务器是不合谋的，所以文献[45]在三方交集中存在两方合谋时是不安全的.文献[42]基于加法同态加密框架构建，且在恶意版本的协议中需要O(n2)计算复杂度，其未提供任何实验数据和代码，但预计其效率要比本文低的多.文献[44]基于不经意线性函数评估(oblivious linear function evaluation, OLE)构建，同样需要大量公钥操作，其优势在于通信量较低，当集合包含216个元素时，有固定通信量为80 MB，这是本文通信量的8倍.文献[32]和文献[35]均基于高效的OT扩展，具有较高的运算效率，主要瓶颈均在于通信.

大集合场景下相关方案的通信量对比：文献[32]和文献[35]与本文在3个参与方，各参与方集合大小为28,212,216,220，且存在合谋情况下的通信量对比如表3所示.可以看出，拥有相同的集合大小时，相比于文献[32]和文献[35]，本文方案的通信量降低了89%～98%.因此，本文的协议也将适用于此类具有较大集合(210～220个元素)且需要降低通信量的场景中.例如在集合大小是220时，文献[32]和文献[35]通信开销分别约为20 GB和1.6 GB，这在通信带宽受限的场景中是不可接受的.

Table 3 Communication Comparison of Malicious Secure Three-Party PSI Protocol in Large Set Scenarios

小集合场景下相关方案的对比：基于同态加密的方案同样适应于弱通信场景，具有较低通信量，但由于需要大量公钥加密操作，计算速度比本文方案慢几个数量级.文献[25]与文献[26]均基于同态加密实现了多方PSI，这2个文献与本文方案的通信量和运行时间对比如图4所示.由图4可知，文献[26]的通信量和运行时间都很高，这与其采用同态加密的布隆过滤器有关；文献[25]通信量较低，与本文基本相同，但其总运行时间是本文的10～25倍.

5 结 论

PSI协议是安全多方计算的重点研究问题之一.本文提出了2个基于密钥协商的三方隐私集合交集计算协议，分别可以抵抗半诚实和恶意敌手且允许任意两方合谋，通过模拟范式证明了方案的安全性.与现有方案相比，本文的方案具有较低的通信代价和更高的安全性，尤其适用于带有小集合的三方隐私集合交集计算场景.在未来的工作中，我们将考虑进一步提高计算效率并扩展到普适多方的场景，一种可能的优化是通过寻找不同的编码方式以降低多项式插值过程的计算成本.

作者贡献声明：张蕾负责论文思路构建和框架设计；贺崇德负责撰写论文和实验；魏立斐提出指导意见并负责论文校对与修订.