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

张 蕾1 贺崇德1 魏立斐2

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

摘 要 隐私集合交集(private set intersection, PSI)允许持有私有集合的参与方安全地获得集合的交集,而不会泄露除交集之外任何元素的信息.现有的两方/多方PSI协议大多基于不经意传输(oblivious transfer, OT)协议,具有很高计算效率的同时,也带来了巨大通信开销.在很多场景中,扩展网络带宽是非常昂贵甚至不可行的,而目前不依赖于OT设计且计算高效的多方PSI协议仍然较少.基于一轮密钥协商构造了三方参与的PSI计算协议,分别在半诚实模型和恶意安全性模型下,证明了协议的安全性且允许任意两方的合谋攻击.通过实验仿真,在大集合场景,相比现有基于OT的多方PSI协议,所构造的协议具有最优的通信轮数且通信量降低了89%~98%;在小集合场景(500个元素或更少),相比适用弱通信网络的同类PSI协议,具有最优运行时间和通信负载,比依赖于同态加密的PSI协议快10~25倍.

关键词 隐私集合交集;密钥协商;恶意敌手;抗合谋攻击;小集合场景

隐私集合交集(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(n lb n).随着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个参与方,可以抵抗任意两方的合谋攻击.在三方协议中,需要对任意两方合谋进行模拟,证明模拟器视图与真实协议视图计算不可区分.

定义1.半诚实模型安全性.设f是理想三方协议,用I表示任意参与方子集.I中参与方在执行输入为(x,y,z)三元组的协议π时,其视图表示为其中n为安全参数,表示I中各参与方的输入值列表,表示参与方集合I在执行过程中产生的第j个随机数,表示I收到的第j个消息.如果存在使用概率多项式时间算法的模拟器S,使得对于任意的I均有下式成立:

则称协议π安全地计算了f,其中表示计算不可区分.

定义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}.

Fig.1 Ideal functionality of three-party PSI

图1 三方PSI的理想功能

2.3 理想置换

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

2.4 双线性配对

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

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

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

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

本文方案的安全性主要基于判定性双线性(decision bilinear Diffie-Hellman, DBDH)假设:对于PG,给定(P,aP,bP,cP)和元素hGT,判断e(P,P)abch是计算不可区分的,即对于任意的多项式时间算法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×GGT,其中G是素数q阶加法循环群,GTq阶乘法循环群.PG的一个生成元,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.

Fig.2 Three-party key agreement protocol

图2 三方密钥协商协议

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通过插值多项式,将所有xiX与用于生成共享密钥的参数aiP进行关联,并通过理想置换Π-1(aiP)使得生成的多项式与随机选取的同阶多项式不可区分,从而保证了集合X中元素的隐私性.参与方BC通过对来自A的多项式求响应,并最终求出共享密钥,分别隐含了XYXZ的信息.最终C通过对比共享密钥,即可得出三方集合交集,不会泄露除交集外的任何元素信息.

Fig.3 Semi-honest three-party private set intersection computation protocol

图3 半诚实三方隐私集合交集计算协议

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

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

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

输出:接收方C输出集合XYZ.

协议过程如下:

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)B计算输出密钥.B对每一个yiY,对来自参与方A的多项式求值Q(yi),并计算每个响应对应的共享密钥值将其乱序发送给C.

4)C计算输出密钥.CB做同样的操作,即对每一个ziZ,对多项式求值Q(zi),并计算每个响应对应的共享密钥值

5)计算交集.参与方C判断是否在KB中,若则输出

3.1.2 正确性分析

参与方A插值多项式Q使得Q(xi)=Π-1(aiP),参与方B用自己的集合元素在多项式上求响应并进行理想映射得到Π(Q(yi)).若参与方AB拥有相同的集合元素xi=yi,则Π(Q(yi))=aiP,然后利用双线性配对计算输出密钥集合此时否则将是一个随机值.同理,参与方C用自己的集合元素在多项式上计算并进行理想置换得到Π(Q(zi)),若参与方AC拥有相同的集合元素xi=zi,则Π(Q(zi))=aiP,当参与方C利用双线性配对计算输出密钥此时否则将是一个随机值.

因此,对于交集中的元素xi=yi=zi,有:

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

因此,满足的元素,即交集XYZ的元素.

假设xiXYZ,只有当xi对应的随机密钥时,接收方才会产生不正确的输出.对于这个特殊的xi,当随机密钥的随机空间足够大时,这个事件发生的概率是可忽略的.设随机密钥空间为K,则该事件发生的概率为n/|K|,在最多n个这样的值时,发生的总概率为n2/|K|,由于协议的随机密钥空间|K|≥2λ+2 lb n,故发生错误的概率是2-λ,即可忽略的.

3.1.3 安全性证明

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

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

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

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

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

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

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

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

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

为了证明hybridhhybridh+1是不可区分的,修改上述混合序列步骤③为:若zhXYZ,模拟器计算kh=k*;对于所有其他的ziZ,选择随机值作为ki的输出.

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

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

证毕.

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

3.2.1 基本协议

本节将展示恶意安全的基于密钥协商的三方PSI协议.恶意安全三方PSI的完整协议在协议2中给出.为了对抗恶意敌手,让参与方A插值多项式Q,使得Q(H(xi))=Π-1(aiP),其中Π是理想置换,H是抗碰撞哈希函数,将参与方B的输出K替换为

在半诚实版本的基础协议中存在以下安全威胁:若恶意参与方A插值多项式使得Q1(b)=Π-1(abP),其中,b是参与方B的元素,ab是与b对应的随机数.参与方A将此多项式发送给B.接下来A插值多项式使得Q2(c)=Π-1(abP),其中c是参与方C的元素.根据协议过程,该行为将导致协议输出错误的结果(元素c并不在交集,但它将会被输出).本文在恶意版本的协议2中将参与方B的输出K替换为避免了这种攻击.在安全性证明中,H1H2作为随机预言机来帮助模拟器进行输入提取.

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

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

输入:参与方ABC分别输入集合XYZ

输出:接收方C输出集合XYZ.

协议过程如下:

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

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

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

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

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

5)B对每个yiY和相应的ki联合求哈希值得到将其乱序发送给C.

6)C计算输出密钥.C对每一个ziZ求哈希值H1(zi),然后用H1(zi)对来自参与方A的多项式Q(·)求值,并计算对应的共享密钥值ki=e(Π(Q(H1(zi))),bP)c.最后对ziki联合求哈希值得到

7)计算交集.参与方C判断是否在K中,若则输出zi.

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的元素即是交集XYZ的元素.

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合谋的情况下安全性归约于判定性双线性问题的困难性假设.

证明思路如下:模拟器的主要任务是提取2个输入集合发送给理想PSI函数,获得然后适当地模拟了消息K.想要区分合谋参与方作为参与者输出的消息和作为窃听者输出的消息,前者与的元素对应,后者可用随机值代替.诚实的参与方B对每个yY计算Π(Q(H1(y)))作为一个标准消息,而敌手只有以下情况同时发生时才拥有这个值:它查询了H1(y)且对随机置换做了反向查询Π-1得到 Q(H1(y)).若敌手直接选择Q(H1(y))或只对理想置换做正向查询Π,则敌手没有对应的值,在模拟器中它将对该结果值没有控制.同理,模拟器观察H2的所有查询,可以识别哪些K的实例会给出敌手可以识别的输出,其他输出都可以安全地用随机输出来替换.

证明.首先刻画模拟器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Π中的对应值.

2)在收到多项式Q(·)之后,S定义集合并将发送到理想PSI函数.

3)从理想PSI函数接收到后,S对所有wW计算kw=e(Π(Q(H1(w))),cP)b,定义K={H2(w,kw)|wW},然后不断向K中添加随机值,直到|K|=|Y|.

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

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

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

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

同时,列表O1O2OΠ也被生成.

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

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

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

yY and Q(H1(y))∉Si}.

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

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

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

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

yY and Q(H1(y))∈OΠ}.

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

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

yYO1and Q(H1(y))∈OΠ}.

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

假设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|

yYO1and Q(H1(y))∈OΠ}.

假设记K等价为

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

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

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

证毕.

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

证明思路如下:模拟器S的主要任务是提取集合发送给理想函数.在接收到多项式Q(·)之后,诚实的参与方C对每个zZ计算Π(Q(H1(z))),而敌手只有以下情况发生时才拥有这个值:查询了H1(z)并且它查询反向随机置换Π-1得到 Q(H1(z)).若敌手直接选择Q(H1(z))或直接对理想置换做正向查询Π,则敌手没有对应的值,S将对该结果值没有控制.同理,在接收到敌手给出的K后,S观察所有H2查询,可以知道哪些值通过H2放入了K中.同时,ΠS控制,因此S可以获得随机置换的输入输出值,进而得知哪些值是z对应的正确输出密钥,从而完成输入提取.

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

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

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

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

k′)∈O2and k′∈K}.

4)S发送到理想PSI函数获得

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

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

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

同时,列表O1,O2OΠ也被生成.

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

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

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

and Q(H1(z))∈OΠand zO1}.

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

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

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

O2and k′∈K and Q(H1(z))∈OΠand zO1},

等价于:

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

O2and k′∈K and Q(H1(x))∈OΠand xO1}.

假设记则交集等价于:

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

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

O2and k′∈K}.

至此,hybrid3输出为这和理想输出是相同的.

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

证毕.

4 协议性能与比较

4.1 实验环境与参数

本文使用C++实现了基于密钥协商的三方恶意隐私集合交集计算协议,并与同类方案进行了对比.实验环境为:Ubuntu 18.04.4 LTS, Intel® CoreTM i7-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计算bPcP,以及n个经过双线性运算的密钥输出;参与方A计算naiP.3个参与方对H1Π±各进行n次查询;参与方BC分别对H2进行n次查询;最后参与方A必须插值一个多项式,参与方BCn个点上对多项式求值,这都需要O(n lb2n)个域操作[41].由参与方C进行对比得出交集,各个参与方负载均衡.该协议的总通信成本包括:参与方BC发送的bPcP;用于描述多项式Q(·)的n个域元素;nH2输出,每个2κ位.

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

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

表1 小集合场景下本文方案通信量和运行时间

集合大小通信量∕KB在线时间∕s离线时间∕s242.680.0290.044255.250.0410.0732610.370.0830.1192720.620.1430.2462841.080.3060.4792982.120.5920.936

4.3 性能对比

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

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

表2 相关半诚实、恶意三方PSI协议对比

协议安全模型是否合谋通信轮数通信复杂度计算复杂度文献[42] 半诚实是4O(n)O(nlbn)文献[31]-协议1半诚实是4O(n)O(n)文献[31]-协议2增强半诚实是3O(n)O(n)文献[43]半诚实否8O(nlbn)O(n)本文(PSI-s)半诚实是2O(n)O(n)文献[42]恶意是7O(nlbn)O(n2)文献[44]恶意是12O(n)O(nlb2n)文献[32]恶意是8O(nlbn)O(n)文献[45]恶意否5O(nlbn)O(n)文献[35]-协议1恶意否5O(n)O(n)文献[35]-协议2恶意是4O(n)O(n)本文(PSI-m)恶意是2O(n)O(n)

文献[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

表3 大集合场景下恶意安全的三方PSI协议通信量对比 MB

协议集合大小28212216220文献[32]14.45214.151623.2820876.96文献[35]0.345.5295.071669.17本文(PSI-m)0.040.6410.25164.01

Fig.4 Comparison with HE-based PSI in small setscenarios

图4 小集合场景下与基于同态加密的PSI方案对比

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

5 结 论

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

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

参考文献

[1]Shen Liyan, Chen Xiaojun, Shi Jinqiao, et al.Survey on private preserving set intersection technology[J].Journal of Computer Research and Development, 2017, 54(10): 2153-2169(in Chinese)(申立艳, 陈小军, 时金桥, 等.隐私保护集合交集计算技术研究综述[J].计算机研究与发展, 2017, 54(10): 2153-2169)

[2]Wei Lifei, Liu Jihai, Zhang Lei, et al.A survey of privacy preserving oriented set intersection computation[J].Journal of Computer Research and Development, 2022, 59(8): 1782-1799(in Chinese)(魏立斐, 刘纪海, 张蕾, 等.面向隐私保护的集合交集计算综述[J].计算机研究与发展, 2022, 59(8): 1782-1799)

[3]Yung M.From mental poker to core business: Why and how to deploy secure computation protocols?[C]//Proc of the 22nd ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2015: 1-2

[4]Privacy-preserving Data Mining: Models and Algorithms[M].Berlin: Springer, 2008

[5]Demmler D, Rindal P, Rosulek M, et al.PIR-PSI: Scaling private contact discovery[J].Proceedings on Privacy Enhancing Technologies, 2018, 2018(4): 159-178

[6]Duong T, Phan D H, Trieu N.Catalic: Delegated PSI cardinality with applications to contact tracing[C]//Proc of the 26th Int Conf on the Theory and Application of Cryptology and Information Security.Berlin: Springer, 2020: 870-899

[7]Ion M, Kreuter B, Nergiz E, et al.Private intersection-sum protocol with applications to attributing aggregate ad conversions[J/OL].Cryptology ePrint Archive, 2017[2020-11-30].https://eprint.iacr.org/2017/738

[8]Rabin M O.How to exchange secrets with oblivious transfer[J/OL].Cryptology ePrint Archive, 2005[2021-12-30].https://eprint.iacr.org/2005/187

[9]Kolesnikov V, Kumaresan R, Rosulek M, et al.Efficient batched oblivious PRF with applications to private set intersection[C]//Proc of the 23rd ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2016: 818-829

[10]Pinkas B, Rosulek M, Trieu N, et al.Spot-light: Lightweight private set intersection from sparse ot extension[C]//Proc of the 39th Annual Int Cryptology Conf.Berlin: Springer, 2019: 401-431

[11]Chase M, Miao Peihan.Private set intersection in the Internet setting from lightweight oblivious PRF[C]//Proc of the 40th Annual Int Cryptology Conf.Berlin: Springer, 2020: 34-63

[12]Pinkas B, Schneider T, Zohner M.Faster private set intersection based on OT extension[C]//Proc of the 23rd USENIX Security Symp.Berkeley.CA: USENIX Association, 2014: 797-812

[13]Pinkas B, Schneider T, Segev G, et al.Phasing: Private set intersection using permutation-based hashing[C]//Proc of the 24th USENIX Security Symp.Berkeley, CA: USENIX Association, 2015: 515-530

[14]Rindal P, Rosulek M.Malicious-secure private set intersection via dual execution[C]//Proc of the 24th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2017: 1229-1242

[15]Wei Lifei, Wang Qin, Zhang Lei, et al.Efficient private set intersection protocols with semi-trusted cloud server aided[J/OL].Journal of Software, 1-13[2022-06-15].http://www.jos.org.cn/1000-9825/6397.html(in Chinese)(魏立斐, 王勤, 张蕾, 等.半可信云服务器辅助的高效隐私交集计算协议[J/OL].软件学报, 1-13[2022-06-15].http://www.jos.org.cn/1000-9825/6397.html)

[16]Ion M, Kreuter B, Nergiz E, et al.Private intersection-sum protocol with applications to attributing aggregate ad conversions[J/OL].Cryptology ePrint Archive, 2017[2020-11-30].https://eprint.iacr.org/2017/738

[17]Huberman B, Franklin M, Hogg T.Enhancing privacy and trust in electronic communities[C]//Proc of the 1st ACM Conf on Electronic Commerce.New York: ACM, 1999: 78-86

[18]Cristofaro E D, Kim J, Tsudik G.Linear-complexity private set intersection protocols secure in malicious model[C]//Proc of the 16th Int Conf on the Theory and Application of Cryptology and Information Security.Berlin: Springer, 2010: 213-231

[19]Jarecki S, Liu Xiaomin.Fast secure computation of set intersection[C]//Proc of the 7th Int Conf on Security and Cryptography for Networks.Berlin: Springer, 2010: 418-435

[20]Rosulek M, Trieu N.Compact and malicious private set intersection for small sets[C]//Proc of the 27th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2021: 1166-1181

[21]Mansy D, Rindal P.Endemic oblivious transfer[C]//Proc of the 26th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2019: 309-326

[22]Cristofaro E D, Tsudik G.Practical private set intersection protocols with linear complexity[C]//Proc of the 14th Int Conf on Financial Cryptography and Data Security.Berlin: Springer, 2010: 143-159

[23]Cong K, Moreno R C, da Gama M B, et al.Labeled PSI fromhomomorphic encryption with reduced computation and communication[C]//Proc of the 27th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2021: 1135-1150

[24]Chen Hao, Huang Zhicong, Laine K, et al.Labeled PSI from fully homomorphic encryption with malicious security[C]//Proc of the 25th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2018: 1223-1237

[25]Bay A, Erkin Z, Alishahi M, et al.Multi-party private set intersection protocols for practical applications[C]//Proc of the 18th Int Conf on Security and Cryptography.Setubal: SciTePress, 2021: 515-522

[26]Bay A, Erkin Z, Hoepman J H, et al.Practical multi-party private set intersection protocols[J].IEEE Transactions on Information Forensics and Security, 2021, 17: 1-15

[27]Heinrich A, Hollick M, Schneider T, et al.PrivateDrop: Practical privacy-preserving authentication for Apple AirDrop[C]//Proc of the 30th USENIX Security Symp.Berkeley, CA: USENIX Association, 2021: 3577-3594

[28]Pinkas B, Rosulek M, Trieu N, et al.PSI from PaXoS: Fast, malicious private set intersection[C]//Proc of the 39th Annual Int Conf on the Theory and Applications of Cryptographic Techniques.Berlin: Springer, 2020: 739-767

[29]Rindal P, Schoppmann P.VOLE-PSI: Fast OPRF and circuit-PSI from vector-OLE[C]//Proc of the 40th Annual Int Conf on the Theory and Applications of Cryptographic Techniques.Berlin: Springer, 2021: 901-930

[30]Boyle E, Couteau G, Gilboa N, et al.Efficient two-round OT extension and silent non-interactive secure computation[C]//Proc of the 26th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2019: 291-308

[31]Kolesnikov V, Matania N, Pinkas B, et al.Practical multi-party private set intersection from symmetric-key techniques[C]//Proc of the 24th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2017: 1257-1272

[32]Efraim A B, Nissenbaum O, Omri E, et al.PSImple: Practical multiparty maliciously-secure private set intersection[R/OL].Cryptology ePrint Archive, 2021[2021-05-13].https://eprint.iacr.org/2021/122

[33]Inbar R, Omri E, Pinkas B.Efficient scalable multiparty private set-intersection via garbled Bloom filters[C]//Proc of the 15th Int Conf on Security and Cryptography for Networks.Berlin: Springer, 2018: 235-252

[34]Rindal P, Rosulek M.Improved private set intersection against malicious adversaries[C]//Proc of the 36th Annual Int Conf on the Theory and Applications of Cryptographic Techniques.Berlin: Springer, 2017: 235-259

[35]Nevo O, Trieu N, Yanai A.Simple, fast malicious multiparty private set intersection[C]//Proc of the 27th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2021: 1151-1165

[36]Garimella G, Pinkas B, Rosulek M, et al.Oblivious key-value stores and amplification for private set intersection[C]//Proc of the 41st Annual Int Cryptology Conf.Berlin: Springer, 2021: 395-425

[37]Bellare M, Hoang V T, Keelveedhi S, et al.Efficient garbling from a fixed-key blockcipher[C]//Proc of the 34th IEEE Symp on Security and Privacy.Piscataway, NJ: IEEE, 2013: 478-492

[38]Guo Chun, Katz J, Wang Xiao, et al.Efficient and secure multiparty computation from fixed-key block ciphers[C]//Proc of the 41st IEEE Symp on Security and Privacy.Piscataway, NJ: IEEE, 2020: 825-841

[39]Boneh D, Franklin M.Identity-based encryption from the Weil pairing[C]//Proc of the 21st Annual Int Cryptology Conf.Berlin: Springer, 2001: 213-229

[40]Joux A.A one round protocol for tripartite Diffie-Hellman[C]//Proc of the 4th Int Algorithmic Number Theory Symp.Berlin: Springer, 2000: 385-393

[41]Moenck R, Borodin A.Fast modular transforms via division[C]//Proc of the 13th Annual Symp on Switching and Automata Theory.Piscataway, NJ: IEEE, 1972: 90-96

[42]Hazay C, Venkitasubramaniam M.Scalable multi-party private set-intersection[C]//Proc of the 20th IACR Int Conf on Practice and Theory in Public Key Cryptography.Berlin: Springer, 2017: 175-203

[43]Chandran N, Dasgupta N, Gupta D, et al.Efficient linear multiparty PSI and extensions to circuit/quorum PSI[C]//Proc of the 27th ACM SIGSAC Conf on Computer and Communications Security.New York: ACM, 2021: 1182-1204

[44]Ghosh S, Nilges T.An algebraic approach to maliciously secure private set intersection[C]//Proc of the 38th Annual Int Conf on the Theory and Applications of Cryptographic Techniques.Berlin: Springer, 2019: 154-185

[45]Zhang En, Liu Fenghao, Lai Qiqi, et al.Efficient multi-party private set intersection against malicious adversaries[C]//Proc of the 27th ACM SIGSAC Conf on Cloud Computing Security Workshop.New York: ACM, 2019: 93-104

Efficient and Malicious Secure Three-Party Private Set Intersection Computation Protocols for Small Sets

Zhang Lei1, He Chongde1, and Wei Lifei2

1(College of Information Technology, Shanghai Ocean University, Shanghai 201306) 2(College of Information Engineering, Shanghai Maritime University, Shanghai 201306)

Abstract Private set intersection(PSI)allows participants who hold private sets to securely obtain the set intersection without revealing information about any elements other than the intersection.Most of the existing two-party/multi-party PSI protocols are based on the oblivious transfer(OT)protocol, which not only has high efficiency, but also brings huge cost of communication.However, expanding network bandwidth is very expensive or even infeasible in many scenarios, and there are few computationally efficient multi-party PSI protocols that do not rely on OT protocols.In this paper, three-party private set intersection computing protocols are constructed based on one round key agreement.The protocols are proved secure assuming the collusion attack of any two parties in the semi-honest model and malicious model, respectively.Through experimental simulation, in the large set scenario, compared with the existing OT-based multi-party PSI protocol, the three-party private set intersection computation protocols have the optimal number of communication rounds, and the amounts of communication is reduced by 89%~98%.In small set scenarios(500 items or less), compared with similar PSI protocols for weak communication networks, the protocols in our paper have optimal runtime and communication load, especially, and they get 10~25 times faster than PSI protocol relying on homomorphic encryption.

Key words private set intersection(PSI); key agreement; malicious adversaries; collusion resistant attack; small sets scenarios

中图法分类号 TP309

(Lzhang@shou.edu.cn)

DOI:10.7544/issn1000-1239.20220471

收稿日期20220610;修回日期:20220810

基金项目国家自然科学基金项目(61972241);上海市自然科学基金项目(22ZR1427100,18ZR1417300);上海市高可信计算重点实验室开放课题(OP202102);上海市青年科技英才扬帆计划(21YF1417000);上海海洋大学骆肇荛大学生科技创新基金项目

This work was supported by the National Natural Science Foundation of China(61972241), the Natural Science Foundation of Shanghai(22ZR1427100,18ZR1417300); The Open Project of Shanghai Key Laboratory of Trustworthy Computing(OP202102); Shanghai Sailing Program(21YF1417000); Luo Zhaorao College Student Science and Technology Innovation Fund of Shanghai Ocean University.

通信作者魏立斐(lfwei@shmtu.edu.cn)

Zhang Lei, born in 1983.PhD, associate professor.Member of CCF.Her main research interests include cryptography, data security and access control.

张 蕾,1983年生.博士,副教授.CCF会员.主要研究方向为密码学、数据安全、访问控制.

He Chongde, born in 1997.Master candidate.Student member of CCF His main research interests include cryptography and information security.

贺崇德,1997年生.硕士研究生.CCF学生会员.主要研究方向为密码学、信息安全.

Wei Lifei, born in 1982.PhD, professor, master supervisor.Senior member of CCF.His main research interests include information security, privacy preserving and cryptography.

魏立斐,1982年生.博士,教授,硕士生导师.CCF高级会员.主要研究方向为信息安全、隐私保护、密码学.