面向集合计算的隐私保护统计协议

目前，通过共享分散于多机构的孤立数据、挖掘其中蕴含的潜在价值，从而服务于政府决策以及提高服务质量，已经成为一种客观需求.然而，在很多场景下，数据持有者往往有隐私需求，并且待分享的数据通常包含一定的商业价值，因而数据持有者不想揭示持有数据的明文信息.况且，国内外关于数据安全的法律法规，如欧洲的数据保护总条例(general data protection regulation, GDPR)和《中华人民共和国密码法》的生效，为数据安全提出了更高的要求.因此，如何在保护数据隐私的前提下，对分散的数据进行融合计算，发掘数据的潜在价值，已经成为学术界和工业界的热点研究问题.

在数据共享场景中，一种典型应用需求是集合求交(private set intersection, PSI).以两方计算为例，参与方P0持有集合X，P1持有集合Y，执行集合求交运算后，双方得到交集结果X∩Y,而不泄露任何其他信息.集合求交可广泛应用于隐私需求较高的保险、医疗、征信等业务场景，如2个银行计算共同客户而不泄露自己持有的客户群体.然而，仅仅计算集合交集并不能满足持续扩大的需求.具体来说，很多场景下，协议双方可能不仅仅满足于交集计算，而想计算集合运算结果的某些函数.比如双方可能只想泄露关于交集的某个函数f(X∩Y)，如交集大小、交集权值和等.在这些应用场景中，很多时候泄露交集元素都是不被允许的.因此，需要对隐私保护的集合运算及性能进行拓展，从而满足法规约束下的越来越多的隐私保护数据共享需求.

通用安全多方计算可以实现以上需求.具体来说，安全多方计算能够允许互不信任的n个参与方P0,P1,…,Pn-1通过协议交互计算某个既定函数f，协议运行结束后，只揭示计算结果y=f(x0,x1,…,xn-1)，除此之外不泄露任何关于输入的信息.虽然近年来基于Yao电路和秘密共享的通用安全多方计算协议的效率得到极大提升，但对于集合运算，专用安全多方计算协议更高效.在本文中提出了计算集合运算统计量的专用安全计算协议.具体来说，在两方计算场景下，设计了计算集合运算统计量的协议架构.利用该协议，参与方可以高效地计算集合交集大小、并集大小以及交集权值和等统计量，而不泄露具体的交集元素.该协议主要利用了茫然传输(oblivious transfer, OT)作为协议的主要密码组件.由于OT可以通过OT拓展协议生成大量实例，从而使得协议具有较好的可拓展性.具体地，本文主要内容包含3个方面:

1) 提出了计算集合运算统计量的一组协议，能够实现针对集合运算的数据统计计算，包括交集大小、并集大小、交集权值和交集权值方差等集合运算的统计信息.

2) 该协议可以仅利用OT作为底层密码组件，因而可以借鉴高效的OT拓展技术实现较好的效率.本文对协议的通信和计算的渐进效率进行了复杂度分析和对比.

3) 在半诚实敌手设定下，利用理想现实模拟对协议进行了安全证明.

1 相关工作

基于Diffie-Hellman密钥协商的PSI协议可以实现较好的通信效率，但是计算效率较低.此类协议[1-2]利用了Hash函数H：{0,1}n→G，其中底层群G为素数阶p且判定Diffie-Hellman问题是困难的.具体来说，参与方P0和P1分别持有密钥k0,k1∈Zp.发送者P1计算Y′={H(y)k1}y∈Y并发送给P0，P0计算X′={H(x)k0}x∈Y并发送给P1.然后P1计算X″={H(x′)k1}x′∈X′并发送给P0.最终，P0计算Y″={H(y′)k0}y′∈Y′，并输出{x|x″∈X″∩Y″}.

基于OT的PSI协议[3-7]由于计算性能友好，近来成为主流设计思路.基于OT的方案主要想法是利用OT来进行等值比较计算.在等值比较协议中，P0输入x,P1输入y，协议结束后P0只能知道x是否等于y.利用这种方法，在最坏情况下，双方对所有可能的元素对执行运算，产生O(n2)的通信和计算复杂度.为了提高此类协议的效率，可以借鉴Hash分桶[8]的思想，将元素映射到Hash表中的每个桶中，然后逐桶执行等值比较.通过合理选取参数，可以达到O(n log n)甚至O(n)的复杂度.文献[9]提出了一个传输短消息的OT拓展协议.随后，通过对文献[9]中的OT拓展协议进行改进，Kolesnikov等人[10]设计了基于OT拓展的茫然伪随机函数(oblivious pseudorandom function, OPRF)，并将其利用到PSI协议中，实现了ω(n)的复杂度，接近于最优.近来Pinkas等人[11]设计了一个新的稀疏OT拓展协议，能够允许OPRF接收方计算多个点的OPRF输出.利用该OT拓展，可以实现O(n)的通信复杂度.

Dong等人[12]提出了一个高效的基于布隆过滤器的成员测试数据结构——混乱布隆过滤器，并将其应用到集合求交协议中；文献[13]基于混乱布隆过滤器构造了一个恶意敌手下安全的PSI协议.集合求交可利用通用安全计算协议来实现；Huang等人[14]提出利用混乱电路来执行集合求交运算，能够实现O(n log n)的复杂度.此外，利用多项式可以表示集合元素.具体来说，给定一个集合，可以将集合元素作为多项式零点值来生成代表集合的多项式，那么2个多项式的最大公约多项式为集合交集，而2个多项式相乘则代表了集合并集.因此，集合求交问题可以转换成针对多项式的运算；Kissner和Song[15]基于此想法构造了针对集合操作的隐私保护协议，包括集合求交、交集大小、门限并集等.

除了计算集合交集，很多时候参与方可能只想计算关于交集的某个函数f(X∩Y)，比如保密计算交集大小、交集元素权重求和、求方差等交集统计量.文献[16]中的协议可以计算集合交集大小.文献[17]基于加同态加密设计了保密交集求和协议，可以应用到计算广告转化率协议中.具体来说，该协议假设参与方P0持有集合X，另一个参与方P1不仅持有集合Y，同时对于Y中的每一个元素都有一个对应的权值，记该权值集合为V.双方执行交集权值求和协议，最终P0得到所有交集元素的权值和.随后，Miao等人[18]利用零知识证明对文献[16]的交集求和协议进行了安全加固，能够实现双输出模式的恶意敌手下安全.之前提到的文献[6]同样支持计算交集的函数，该文献基于GMW范型[19]的通用电路构造了计算关于交集的某些函数，本质上能够计算关于交集的任何函数.然而，基于GMW范型的安全计算一个主要的缺点是轮数较高.此外，Le等人[20]基于三方秘密共享设计了一个两方计算集合交集函数的协议，然而，该协议需要额外借助一个第三方服务器，且服务器不能和任何任意一方合谋；文献[21]对集合求交的基本构造技巧进行了归纳和总结.

2 预备知识

本节中主要介绍后文用到的符号和安全多方计算的一些基本组件.

2.1 符号说明

本文中，λ表示安全参数，函数μ:N→R是可忽略函数，即对于任意大的正多项式ploy(·)以及任何足够大的λ，都有μ(λ)<1 width=5,height=17,dpi=110

ploy(λ).

2.2 相关原语

1) 茫然传输(OT).OT是安全多方计算的核心组件.以应用最广泛的2选1 OT为例，发送者提供2个消息m0,m1,接收者提供选择比特b，最终接收者拿到mb.OT的安全性要求接收者不知道m1-b，而发送者不知道接收者的选择比特b.更一般地，可以定义N选1 OT，其中发送者提供N个消息，接收者只能拿到1个消息.OT的理想功能函数定义为：

① 接收方提供输入(m1,m2,…,mN)，接收方输入选择比特b;

② 将mb发送给发送方.

OT只能通过公钥密码原语进行构造，但是可以利用对称技巧进行高效拓展.具体来说，OT拓展协议只需要执行少量的基础OT，附加高效的对称操作，就可以产生大量的拓展OT实例.当前，OT拓展技术已经相当高效.

2) 茫然伪随机函数.茫然伪随机函数(OPRF)是一个两方协议，其中发送方持有伪随机函数F的密钥key,而接收方持有输入x.双方执行协议后，接收方输出F(key,x)而发送方输出为空.OPRF的理想功能函数定义为：

① 接收方提供输入(m1,m2,…,mt),随机选一个PRF密钥key;

② 将key发送给发送方，(F(key,m1),F(key,m2),…,F(key,mt))发送给接收方.

OPRF理想功能函数可通过多种方式实现，如通过两方计算AES电路来实现，其中发送方持有密钥key，接收方持有输入x，双方执行安全计算AES(key,x)，最终将安全计算结果揭示给OPRF接收方.此外，可利用专用协议计算F(key,x)=H(x,H′(x)key)，其中H是普通Hash函数，H′的输出为某个群元素.当然也可以利用文献[10]中的OPRF协议，该OPRF协议可以仅仅利用OT拓展协议来实现，因而其计算效率得到大大优化.在实际协议中，参与方可以根据具体场景的需求来选取合适的OPRF协议.为了描述简单，本文用理想功能函数FOPRF来代替具体的OPRF协议.

3) Hash技巧.当前的集合求交 width=5,height=17,dpi=110

求并协议中，往往利用到了某些特殊的Hash技术来提高协议的渐进复杂度.具体来说，假设参与方P0持有集合X，而参与方P1持有集合Y，其中X，Y的规模为O(n).为执行求交协议，P0需要对所有的x∈X测试其是否属于Y，从而造成总共O(n2)的复杂度.采用一些特殊的Hash方法，如布谷鸟Hash能够实现最优O(n)的协议通信复杂度.

在布谷鸟Hash方案中，Hash表保存了b个桶B1,B2,…,Bb，布谷鸟Hash利用了2个Hash函数h1,h2:{0,1}σ→[1,b]将m个元素映射到b=2(1+ε)m个桶中.在布谷鸟Hash的元素插入过程中，当插入元素e时，首先利用2个Hash函数计算2个位置h1(e)和h2(e)，然后检查h1(e)和h2(e)哪一个位置空缺.如果有空缺，那么随机选一个空缺位置插入e.如果2个位置都已经存在元素，那么随机选一个位置，用e替换该位置原来的元素o.然后继续计算h1(o)和h2(o),对元素o继续做插入处理.持续以上过程，直到没有元素被移出或者移出次数达到某个界值.对于后一种情况，最后一个被移出的数据会被放置在缓存Stash中.现存结论[6-7]表明，当|Stash|≤ln m时，插入m个元素后失败的概率为m-s.布谷鸟Hash的查找非常高效，对于待查元素x，只需要计算h1(x)和h2(x)，然后查找b个桶中对应2个位置.如果元素x存在，必存在于h1(x)和h2(x)或者Stash中.

文献[6-7]设计了无Stash的布谷Hash.简单来说，通过增加布谷Hash函数个数(如Hash函数个数k设为3，4，5)以及合理设置桶的数目，可以在很大的概率下将所有元素放置在桶中，而无需Stash.这种无Stash的布谷Hash技巧，可以避免Stash中元素和集合Y的成员测试.在本文方案中，所有布谷Hash采用此类无Stash的布谷Hash构造技巧.

2.3 安全定义

本节回顾半诚实安全模型的定义，同时也是本文方案可以达到的安全属性.在半诚实安全模型中，参与方会诚实地参与协议执行，但好奇的腐化方会尝试分析协议交互视图来尝试学到额外(关于诚实方输入)的信息.

这里的安全定义沿袭经典安全两方计算定义[22]，令f=(f0,f1)为一个多项式时间的功能函数，协议π是计算f的一个两方协议.定义参与方Pi在输入为(x,y)的协议π中的执行视图为

其中wi∈{x,y},ri表示参与方Pi的内部随机带，

代表执行协议过程中参与方Pi收到的第j个消息.参与方Pi执行协议π之后的输出记为OUTPUTπ(x,y,λ)，给定输入和接收消息，OUTPUTπ(x,y,λ)是可以唯一确定的.

定义1. 令f=(f0,f1)为待计算功能函数，方案π在半诚实敌手下安全计算了功能函数f，必须存在该路多项式时间的模拟器Si,i∈{0,1}，使得：

其中,x,y∈{0,1}*,|x|=|y|且λ∈N.

对于确定性的功能函数，由于f(x,y)=OUTPUTπ(x,y,λ)，定义1可以简化为

3 协议构造

本节介绍隐私保护的集合求交集大小、并集大小以及交集权值和、权值方差等隐私保护统计协议.

3.1 协议组件

3.1.1 共享等值比较

在一个共享等值比较协议中，参与方P0和P1各自提供输入x和y，协议运行结束后，双方共享等值比较结果e.其中，如果x=y,P0和P1共享比特e=1；否则，共享e=0.其功能函数为

① 从P0收到x，从P1收到y;

② 如果x=y,e←1,否则e←0;

③ 随机选取r←Z2,发送r给P0,发送e⊕r给P1.

功能函数FSEQ可以通过YAO协议或者GMW协议计算等值比较电路来实现.然而，简单的基于电路的方法存在通信量或轮数过高的缺点.在本文中借助一个基于OT的等值比较协议ΠSEQ[23]来安全计算功能函数FSEQ，相比基于电路的实现，对于长度为l位的待比较字符串，该协议的轮数仅为O(log log l).

① 令v←l,x(v)←x,y(v)←y;

② while v>δ width=5,height=17,dpi=110

*δ最小可取为3*

Ⅰ) for i∈[1,v], P0随机选取ri←Zv+1,P0和P1计算调用FOT，其中P0输入

输入

最终，P1从FOT收到

mod (v+1);

Ⅲ) 令v←

log(v+1)

,P0设置x(v)←α，P1设置y(v)←β;

④ 令N←2v,P0随机选取b←Z2,计算(m0,m1,…,mN-1)，其中mx(v)←b⊕1，而对于任意i≠x(v)，mi←b⊕1;

⑤ P0和P1执行N选1 OT，P0输入(m0,m1,…,mN-1)，P1输入y(v).最终，P0输出b，P1输出my(v).

该协议的主要思想是将等值比较问题转化为计算2个输入比特串的汉明距离.这里的观察是，2个输入串相等当且仅当2个输入串的汉明距离为0.为此，可利用OT来计算2个输入串的汉明距离，并将计算结果共享到2个参与方.具体来说，参与方通过OT逐位计算2个输入串是否相等.对于第i位，P0输出ri，而P1输出

即双方通过OT共享了第i位的汉明距离

如果没有特殊说明，在Zv+1上的运算都是对v+1取模).这样，经过一轮计算后，双方共享了2个输入的汉明距离.另外一个观察是，对于长度为v的输入串，两者的汉明距离最多为v.因此，参与方的份额可以在一个更小的环Zv+1上共享，而Zv+1上的任意数据都只需要

log(v+1)

位表示.也就是说，每经过一轮运算，待比较字符串的长度要严格小于上一轮比较的字符串(新的待比较串的长度为原比特串长度的对数规模)，而2个新字符串的等值关系(相等或不等)始终是保持的.因此，每经过一轮计算，待比较字符串长度要严格小于上一轮比特串长度，从而降低了下一轮地计算和通信量.直到待比较字符串足够小时(即v<δ，δ最小可取为3)，参与方可以通过1次N取1 OT将最终的等值比较结果共享，其中N←2v.

对于长度为l的初始输入，该协议仅需O(log log l)轮便可分享最终的等值比较结果.这意味着对于长度为128 b的字符串，参与方可以在3轮之内执行完该协议，而且每轮计算量相比于前一轮都大大缩减.此外，利用高效的OT拓展技术和OT预处理技术，协议的计算效率也是相当高效的.

定理1. 在FOT混合模式下，协议ΠSEQ安全计算了功能函数FSEQ.

证明. 该证明遵循理想现实模拟范式.在FOT混合模型下，假设存在针对OT的模拟器

能够模拟OT协议中发送方和接收方的交互视图.在此前提下，构造模拟器S0和S1，分别对参与方P0和P1在协议ΠSEQ的视图进行模拟，并最终证明该模拟视图和真实协议运行视图不可区分.

1) P0被腐化.模拟器S0需要根据输入输出(x，b)，模拟生成一个和真实协议不可区分的视图.令ΠSEQ中OT的调用次数为m+1,其中包括m次2选1 OT和1次N选1 OT.这里将构造m+1个中间视图，其中初始视图和最终视图分别为真实视图和模拟视图.需要证明任意2个相邻游戏的可区分概率为可忽略概率，因此最终得出真实视图和模拟试图不可区分的结论.

H0:H0的视图和真实协议的视图完全相同.

Hi(1≤i≤m):Hi的视图和Hi-1的视图相同，唯一的区别在于第i次调用2选1 OT时，采用OT模拟器

对参与方P0在第i次调用2选1 OT的视图进行模拟.

Hm+1:Hm+1的视图和Hm的视图相同，唯一的区别在于调用N选1 OT时，采用OT模拟器

对参与方P0的在第m+1次的OT视图进行模拟.其中N条消息根据b和Hm中的视图一样生成.

由以上游戏可知，H0为真实协议的视图，而Hm+1为最终模拟器构造的模拟视图.假如存在一个区分器D，能够以不可忽略的概率区分出H0和Hm+1.即：

那么必定存在i，使得：

可见，可以利用以上方法构造一个针对第i次OT发送者模拟的区分器D.然而，这和OT的安全性是矛盾的.因此，区分器D对H0和Hm+1的区分优势是可忽略的.

2) P1被腐化.模拟器S1需要根据输入输出(y，my(v))，模拟生成一个和真实协议执行不可区分的视图.类似于证明P0被腐化的情况，令ΠSEQ中OT的调用次数为m+1,其中包括m次2选1 OT和1次N选1 OT.将构造m+1个中间视图，其中初始视图和最终视图分别为真实视图和模拟视图.需要证明使得任意2个相邻游戏的可区分概率为可忽略，从而最终得出真实视图和模拟试图不可区分的结论.

H0:H0的视图和真实协议的视图完全相同.

Hi(1≤i≤m):Hi的视图和Hi-1的视图相同，唯一的区别在于第i次调用2选1 OT时，采用OT模拟器

对参与方P1的在第i次调用2选1 OT的视图进行模拟.

Hm+1:Hm+1的视图和Hm的视图相同，唯一的区别在于调用N选1 OT时，采用OT模拟器

对参与方P1的视图进行模拟.

根据第m次OT的模拟输出y(v)作为N选1 OT的输入，而my(v)可以由整体协议ΠSEQ的输出得到.给定了OT的输入输出，可利用模拟器

对N选1 OT协议的视图进行模拟.

由以上游戏可知，H0为真实协议的视图，而Hm+1为最终模拟器构造的模拟视图.假如存在一个区分器D，能够以不可忽略的概率区分出H0和Hm+1.即：

那么必定存在i，使得：

类似于之前的证明，可以利用以上方法构造针对第i次OT接收者模拟视图的区分器D.然而，这和OT的安全性是矛盾的.因此，区分器D对H0和Hm+1的区分优势是可忽略的.

3.1.2 共享成员测试

成员测试关注以下场景：P0持有元素x,P1持有集合Y,P0想测试元素x是否属于P1的集合Y.针对本文关注的场景，要求成员测试的结果共享在参与方，而任意一方不知道测试结果.为此，定义共享成员测试理想功能函数FSPMT：

FSPMT功能函数：

① P0输入元素x，P1输入集合Y;

② 计算成员测试结果c,如果x∈Y，则c←1,否则c←0;

③ 随机选取r←Z2,发送r给P0,发送c⊕r给P1.

针对该理想功能函数，给出了一个计算FSPMT的协议ΠSPMT，该协议利用了功能函数FOPRF和FSEQ，因此工作在(FOPRF,FSEQ)-混合模式.

① P0作为FOPRF的接收方，输入x.P1作为FOPRF的发送方.最终，FOPRF发送伪随机函数F的密钥key给P1，发送F(key,x)给P0;

② 针对任yi∈Y，其中i∈[1,|Y|],P1随机选取r←Fp，计算多项式：

P1发送多项式P的系数给P0;

③ P0计算s=P(F(key,x)).2个参与方调用FSEQ，其中P0输入s，P1输入r.最终参与方共享r和s的等值关系.

通过协议ΠSPMT，参与方首先调用FOPRF使得P0拿到OPRF输出F(key,x).随后，P1生成多项式P(x)并将多项式的系数发送给P0.这里的直觉是，如果x∈Y，那么x必定是P(x)-r的某个零点值，那么P0计算s=P(F(key,x))必定和r相等.因此，对s和r调用共享等值功能函数FSEQ，最终将x是否属于Y的信息共享到2个参与方.

ΠSPMT协议利用了功能函数FOPRF和FSEQ，其中FSEQ可以利用基于OT拓展的OPRF实现[9]，或者基于茫然伪随机函数F(key,x)=H(x,H′(x)key)实现.P1生成多项式P(x)并将多项式的系数发送给P0，该过程需要发送的系数规模和集合大小|Y|相当.最终的等值比较功能函数由协议ΠSEQ实现，轮数为O(log log l).

定理2. 在(FOPRF，FSEQ)-混合模式下，协议ΠSEQ安全计算了功能函数FSPMT.

证明. 通过构造针对腐化参与方P0和P1的模拟器

和

生成和真实协议运行不可区分的视图来证明协议ΠSPMT的安全性.因为协议ΠSPMT工作在(FOPRF,FSEQ)-混合模式下，因此可以借助已经存在的OPRF协议模拟器SOPRF[9]和针对ΠSEQ协议的模拟器SSEQ(具体见定理1).

1) P0被腐化.模拟器

工作如下.首先，从伪随机函数F的输出域随机选取元素fx，针对(x,fx)，调用模拟器

生成P0在OPRF协议中的视图，并将该视图附加到的模拟器

视图中.随后，随机选取|Y|个随机数模拟P1发送的多项式系数，记对应的多项式为P*(·),并将其附加到模拟器

的视图.随后，根据模拟的多项式计算r=P*(fx)并随机选取比特b.然后调用

模拟共享等值比较协议的视图.为了证明以上生成的视图和真实协议不可区分，可通过多个混合游戏生成最终的模拟视图，并证明每个游戏的区分概率为可忽略.

H0:H0的视图和真实协议的视图完全相同.

H1:H1的视图和H0的视图相同，唯一的区别在于，H1中OPRF协议执行中，随机选取fx，并利用模拟器

替换H0对应的视图.由OPRF协议的安全性，区分器无法区分H0和H1视图.

H2:H2的视图和H1的视图相同，除了模拟器随机选取多项式系数.由于密钥只有多项式生成方知道，因此随机生成的P*的多项式系数和真实协议接收得到的参数不可区分.因此，H1和H2的视图无法区分.

H3:H3的视图和H2的视图相同，除了模拟器随机选取比特b.然后计算r=P*(fx).随后，模拟器调用共享等值比较的模拟器

由于共享等值比较协议的安全性，H3和H2的视图无法区分.而H3为最终的模拟视图，得证.

2) P1被腐化.模拟器

首先随机选取伪随机函数key.然后调用

模拟OPRF协议视图.随后，根据

的PRF输出值，构造多项式P，其中包含秘密值r.最后，随机选取等值比较结果份额s，调用共享等值比较模拟器

模拟视图.类似P1的分析，该模拟视图和真实协议视图是不可区分的.因此，这里不再赘述每一步的具体混合游戏过程.

3.2 具体方案

协议ΠSPMT只是针对P0持有一个元素，而P1持有集合Y的情况.而本文关注P0持有集合X，P1持有集合Y，双方计算f(X∩Y)的情况.如果重复调用以上协议|X|次，会带来O(n2)的通信复杂度.

针对这个问题，同以往的PSI方案一样，采用Hash技巧降低上述协议的复杂度.具体来说，P0利用布谷Hash将其输入集合X映射到Hash表中，而P1利用普通Hash，将每个元素y∈Y放置到Hash表中的所有可能位置.布谷Hash的性质保证如果P0的某个元素x∈Yi，那么无论x被放在所有可能位置的哪一个位置i，在那个位置i上必有x∈Yi，其中Yi是P1利用简单Hash映射到位置i的所有元素.在接下来的协议中将阐述具体操作过程.

给定功能函数FSPMT，辅助以特定的Hash技巧，可以很方便地计算集合交集大小、交集权值和、方差等基于集合的统计计算.具体示意图如图1所示.

3.2.1 计算交集权值和

计算交集权值和关注以下场景：P0输入集合X以及权值集合V，其中V中的每个元素对应集合X中的每个元素x，记Vx为元素x的权重，每个权重值的位长度为l.P1输入集合Y，其中|X|=|Y|=O(n).双方想要计算交集的权值之和

具体来说，计算交集权值可以通过理想功能函数FPSI-SUM来描述.

FPSI-SUM功能函数：

① P0输入X以及权值集合V，P1输入集合Y;

② 计算

并将该值发送给P1.

针对该理想功能函数，设计了计算交集权值和的协议ΠPSI-SUM，利用3.1节中共享等值比较协议和OT来安全实现FPSI-SUM.

输入：P0输入集合X以及每个元素的权值集合V，P1输入集合Y，其中|X|=|Y|=O(n)，以及共享布谷Hash桶个数m=k(1+ε)n，其中k是某个常数值；

输出：P0无输出，P1输出

① P0利用布谷Hash将X映射到Hash表B1,B2,…,Bm中，令桶i中的元素为xi.P1利用简单Hash，将集合Y映射到m个桶中，其中每个桶中的元素们定义为Yi.

② 参与方对逐桶执行协议ΠSPMT.P0输入xi，P1输入Yi，参与方共享xi是否属于Yi的信息ci.最终P0输出[ci]0，P1输出[ci]1，其中ci=[ci]1⊕[ci]0.

③ P0随机选一个元素

Z2l.P0和P1执行2选1 OT，P0作为发送者输入(ri+[ci]0×Vxi,ri+(1⊕[ci]0)×Vxi),P1作为OT接收者输入[ci]1，最终P1输出ri+([ci]0⊕[ci]1)×Vxi mod 2l.

④ P0计算

mod 2l, P1计算

mod 2l.P0发送a给P1，后者输出计算结果

mod 2l.

协议开始时，P0和P1分别持有集合X和Y.首先，参与方利用Hash技巧，对元素进行组织.具体来说，P0利用布谷Hash将X映射到m=O(n)个桶中，而P1利用简单Hash将Y映射到m个桶中，其中每个桶中可能有多个元素.为了保护桶中元素个数的信息，P1可以在桶中加入无用元素，使得所有桶的元素个数相等.当桶中最大的元素数目设置为O(log n)时，能够保证以上分配的失败概率足够小[7].随后，参与方逐桶执行共享成员测试协议.这样，对于每个桶i，参与方共享了xi是否属于Yi的信息ci.然后，利用共享的等值比较结果，参与方联合计算

其中Ve为元素e的权值.为此，协议采用一个基于OT的协议来实现以上需求.具体来说，针对每个桶Bi，P0作为OT发送者输入2个消息(ri+[ci]0×Vxi,ri+(1⊕[ci]0)×Vxi), P1作为OT接收者输入[ci]1.由于OT的性质，P1最终输出ri+ci×Vxi mod 2l.参与方对所有桶执行上述操作后，对每个桶i，本质上参与方共享了保密值ci×Vxi.也就是说，如果ci=1，那么参与方共享了Vxi；否则，参与方共享0.最后，参与方逐桶将份额相加取模，并由P0将计算结果

揭示给P1(不可反方向揭示)，完成计算.

以上方案可以很方便地计算交集和并集权值大小.针对交集大小，发送者只需将每个元素对应的权值统一设置为1即可，这样只有在交集中的元素被计数为1，否则为0.此外，由于并集大小可以通过公式|X∪Y|=|X|+|Y|-|X∩Y|求得.给定共享的交集大小，只需要计算加法(加法在安全计算中不需要交互就可完成)，可以很高效地计算得到并集大小.ΠPSI-SUM支持交集、并集大小计算，本文把以上2个协议特别地记为ΠPSI-CA和ΠPSU-CA.

针对更一般的情况，ΠPSI-SUM可以用于计算广告转化率.在计算广告转化率协议中，广告投放商拥有访问广告的用户集合，用户点击广告后，可能会转向零售商购买商品.因此，零售商不仅拥有购买商品的用户集合，还额外拥有用户的消费金额.广告商和零售商想要计算所有交集用户的消费总和.可见，计算广告转化率本质上是求交集用户的消费之和，因而可以通过协议ΠPSI-SUM解决.文献[17-18]中的方案可以实现以上计算需求，然而，这些协议需要额外泄露交集大小，并且严重依赖公钥密码.本方案不需要泄露交集大小，并且仅仅需要OT就可以实现计算需求.考虑到当下高效的OT拓展和OT预处理技术，本方案的计算效率更加高效.

定理3. 在(FSPMT,FOT)-混合模式下，协议ΠPSI-SUM安全计算了功能函数FPSI-SUM.

证明. 可以通过构造针对腐化参与方P0和P1的模拟器

和

生成和真实协议运行不可区分的视图来证明协议ΠSPMT的安全性.因为协议ΠPSI-SUM工作在(FSPMT，FOT)-混合模式下，因此可以借助已经存在的共享成员测试协议模拟器SSPMT(见定理2的证明)和针对OT协议的模拟器SOT.

1) P0被腐化.P0输入为X，输出为空.模拟器

工作过程如下.模拟器首先按照布谷Hash将X分配到Hash表.随后，逐桶调用共享成员测试模拟器

为此，对于每个桶，模拟器随机选取比特bi，调用共享成员测试模拟器

生成共享等值比较协议的视图，并将其附加到

的视图中.随后，为了完成结果传输模拟，针对每个桶i，随机选取

Z2l，调用OT模拟器

实现.接下来证明以上模拟和真实视图时不可区分的.

H0:H0的视图和真实协议的视图完全相同.

H1:H1的视图和H0的视图相同，唯一的区别在于，对H1的视图中执行共享成员测试协议时，通过调用模拟器

来生成视图.有定理2中共享成员测试的安全性，可知H1和H0的视图无法区分.

H2:H2的视图和H1的视图相同，除了模拟器调用OT模拟器来生成OT发送过程中的视图.由OT的安全性，H1和H2的视图无法区分.

至此，H2对所有需要交互的组件进行了替换，H2和模拟器

的工作过程完全一直.由于任意2个游戏之间是不可忽略的，可知区分器不能以不可忽略的优势区分真实协议视图和模拟视图.

2) P1被腐化.针对P1模拟器

需要仅仅通过输入输出(Y,sum)来模拟出和真实协议不可区分的视图.类似之前对P0的证明，模拟器

首先按照普通Hash对集合Y分配到Hash桶中.随后，随机选取密钥key，调用共享成员测试模拟器

生成共享等值比较协议的视图，并将其附加到

的视图.要知道，

视图中包含每个桶执行成员测试之后的份额，

可以将所有份额相加,记为a*.根据

可以计算接收份额sum-a*，从而完成最后一块视图的模拟.和之前证明P0被腐化类似，可以通过混合游戏证明以上模拟生成的视图和真实协议执行视图不可区分，这里不再赘述.

3.2.2 计算交集权值的方差

随机变量V的方差定义为Var(V)=E[V2]-E[V]2.协议ΠPSI-VAR允许参与方计算交集权值的方差，其中P0持有

持有集合Y，双方想要计算交集元素对应权值的方差Var(VX∩Y)，其中VX∩Y表示交集元素对应权值的随机变量.

协议ΠPSI-VAR可通过简单改进交集权值和协议ΠPSI-SUM方便地实现.具体来说，发送者P0可以针对每个输入(xi,vi)预先计算

利用ΠPSI-SUM协议，参与方可以共享

和

与之前协议不同，P0不需要在最后一步将

和

的份额揭示给P1，只需要最终揭示计算结果

此外，在执行以上计算时，参与方同样执行调用协议ΠPSI-CA，向P1揭示交集大小|X∩Y|.最终P1可计算交集权值的方差为Var(VX∩Y)=

完成计算.当然，协议ΠPSI-VAR向P1额外泄露了交集大小.为保护交集规模信息，参与方需要执行秘密共享数据上的除法运算，即

除以|X∩Y|，该计算是比较低效的.而将|X∩Y|揭示给P1可大幅度提高协议效率.如果要保护交集大小信息，可以借鉴文献[24]中的技术执行共享数据上的除法运算.只不过，需要将文献[24]中三方共享除法协议作适当修改，以适应两方计算场景，此修改留作未来工作.

4 效率分析

共享成员测试作为本文的最重要的支撑协议，其效率影响着后续基于交集函数的协议的效率.因此，本节主要分析共享成员测试协议的轮数、计算和通信效率，以及和相关方案的比较.

1) 轮数复杂度.共享成员测试协议主要包含OPRF协议、多项式构造、共享等值比较协议.其中OPRF协议根据具体实现不同，轮数会有相应的区别.基于OT拓展的OPRF协议需要执行一轮的基础OT然后本地生成OPRF输出，加上利用OT拓展协议中的接收矩阵生成多项式并传输系数，总共需要2轮.随后，基于OT的共享等值比较协议中，针对长度为l的待比较字符串，仅需要O(log log l)轮复杂度即可完成计算.在通常l=64的设定下，这意味着至多需要3轮即可完成等值比较运算.而通常基于GMW范型的等值比较电路的构造，需要O(log l)轮完成计算.从渐进意义上来说，协议的论复杂度为O(log log l),具体轮越数为5轮.而基于电路的构造，渐进意义下至少为O(log l),在l=64的具体参数下，轮数约为10轮.

2) 计算复杂度.本方案不需要同态加密或者通用的电路构造得到，而是高度依赖OT.要知道，执行O(n)次OT，其中n≫λ，可以通过仅仅执行O(λ)次的基础OT协议(基础OT协议需要公钥操作)，附加高效O(n)次对称操作，因而可以非常高效地生成大量OT实例.从这个意义上讲，相比于依赖同态加密的构造[17]和通用电路的构造[6]，本方案计算效率更有优势.此外，P1的Hash表中每个桶的元素数量最多为O(log n)，利用简单的多项式计算方法需要O(log n)，总共O(n log n).

3) 通信复杂度.在共享成员测试协议中，参与方逐桶执行协议.其中P1利用简单Hash将集合Y分配到规模为O(n)的Hash表中，其中每个桶的元素个数最多为O(log n).由于P1发送的多项式系数个数和桶中的元素个数相等，所以执行所有桶的成员测试协议总共需要O(n log n)的通信量.对于共享等值比较协议，一次l位字符串的比较，通信量为O(l).而在实际情况下n≫λ，因此总体的通信复杂度为O(n log n).为了进一步降低通信量，可采用文献[6]中多项式插值的技巧，将通信复杂度降低到O(n)，然而该优化需改变多项式计算方法，一定程度上牺牲了部分计算效率.是否接受该优化，取决于协议应用的具体场景.

目前能够两方计算(不依赖第三方服务器)交集函数的集合求交方案中，最高效的方案是基于电路的构造[6].和其相比，本方案在轮复杂度上更具优势.具体信息如表1所示：

5 结束语

保密集合求交是很重要的隐私保护数据处理协议，具有实际的商业应用前景.本文仅利用茫然传输，设计了一组支持计算集合交集函数的协议，能够在不泄露交集元素的前提下，计算集合交集大小、并集大小以及交集权值和、交集权值方差.利用Hash技巧，对协议的通信量进行了优化.协议可以在半诚实敌手下证明安全.在未来，将探索支持更多统计功能的协议，以及将这些协议应用到具体的应用场景中.

[1]Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C] //Proc of IEEE Symp on Security and Privacy. Los Alamitos, CA: IEEE Computer Society, 1986: 134-134

[2]Huberman B A, 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

[3]Pinkas B, Schneider T, Zohner M. Scalable private set intersection based on OT extension[J]. ACM Transactions on Privacy and Security, 2018, 21(2): 1-35

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

[5]Pinkas B, Schneider T, Tkachenko O, et al. Efficient circuit-based PSI with linear communication[G] //LNCS 11478: Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2019: 122-153

[6]Pinkas B, Schneider T, Weinert C, et al. Efficient circuit-based PSI via cuckoo hashing[G] //LNCS 10822: Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2018: 125-157

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

[8]Pagh R, Rodler F F. Cuckoo hashing[C] //Proc of European Symp on Algorithms. Berlin: Springer, 2001: 121-133

[9]Kolesnikov V,Kumaresan R. Improved OT extension for transferring short secrets[G] //LNCS 8043: Proc of Annual Cryptology Conf. Berlin: Springer, 2013: 54-70

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

[11]Pinkas B, Rosulek M, Trieu N, et al. Spot-light: Lightweight private set intersection from sparse OT extension[G] //LNCS 11649: Proc of Annual Int Cryptology Conf. Berlin: Springer, 2019: 401-431

[12]Dong Changyu, Chen Liqun, Wen Zikai. When private set intersection meets big data: An efficient and scalable protocol[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 789-800

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

[14]Huang Yan, Evans D, Katz J. Private set intersection: Are garbled circuits better than custom protocols?[C/OL] //Proc of the 19th Network and Distributed Syetem Secuirity Symp. Reston, VA: Internet Society, 2012 [2020-06-11]. https://www.ndss-symposium.org/wp-content/uploads/2017/Po6_4.pdf

[15]Kissner L, Song Xiaodong. Privacy-preserving set operations[G] //LNCS 3621: Proc of Annual Int Cryptology Conf. Berlin: Springer, 2005: 241-257

[16]DeCristofaro E, Gasti P, Tsudik G. Fast and private computation of cardinality of set intersection and union[G] //LNCS 7712: Proc of Int Conf on Cryptology and Network Security. Berlin: Springer, 2012: 218-231

[17]Ion M,Kreuter B, Nergiz E, et al. Private intersection-sum protocol with applications to attributing aggregate ad conversions[DB]. [2020-05-01]. https://eprint.iacr.org/2017/738

[18]Miao Peihan, Patel S, Raykova M, et al. Two-sided malicious security for private intersection-sum with cardinality[DB]. [2020-05-01]. https://eprint.iacr.org/2020/385

[19]Micali S, Goldreich O, Wigderson A. How to play any mental game[C] //Proc of the 19th ACM Symp on Theory of Computing. New York: ACM, 1987: 218-229

[20]Le P H,Ranellucci S, Gordon S D. Two-party private set intersection with an untrusted third party[C] //Proc of the 2019 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2019: 2403-2420

[21]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)

[22]Hazay C, Lindell Y. Efficient Secure Two-party Protocols: Techniques and Constructions[M]. New York: Springer Science & Business Media, 2010

[23]Couteau G. New protocols for secure equality test and comparison[G] //LNCS 10892: Proc of Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2018: 303-320

[24]Wagh S, Gupta D, Chandran N. SecureNN: Efficient and private neural network training[J]. Proceedings on Privacy Enhancing Technologies, 2019, 2019(3): 26-49

面向集合计算的隐私保护统计协议

1 相关工作

2 预备知识

2.1 符号说明

2.2 相关原语

2.3 安全定义

3 协议构造

3.1 协议组件

3.2 具体方案

4 效率分析

5 结束语

Privacy-Preserving Statistics Protocol for Set-Based Computation