基于秘密分享的高效隐私保护四方机器学习方案

阎允雪 马 铭 蒋 瀚,2

1(山东大学软件学院 济南 250101) 2(山东省软件工程重点实验室(山东大学) 济南 250101)

移动互联网、云计算和大数据等技术的快速发展,催生了众多新的服务模式和应用[1],这些服务和应用一方面为用户提供精准化、个性化的服务,给人们的生活带来了极大便利,另一方面又采集了大量用户的相关信息,而所采集信息中往往含有大量隐私数据，包括个人身份信息(如电话号码、身份证号等)、敏感信息(如金融财务、医疗健康等信息)，对这些信息的收集、共享、发布、分析与利用等操作会直接或间接地泄露用户隐私[2],给用户带来极大的威胁和困扰.

隐私保护机器学习(privacy preserving machine learning, PPML)是一个蓬勃发展的研究领域,允许机器学习对用户的私人数据进行计算,同时确保数据的隐私安全[3].安全多方计算(secure multi-party computation)协议允许多个参与者通过使用同态加密、秘密共享和不经意传输等密码技术，以一种安全的方式完成数据的聚合与计算，因此成为应用在高效并行分布式机器学习中的关键.近年来，随着数据的爆炸式增加,隐私保护机器学习中完成大量卷积、激活函数等非线性运算,这些计算的实现往往需要复杂的安全多方计算协议，并且需要根据具体的功能来选择不同的安全多方计算技术.总之，基于安全多方计算的隐私保护机器学习方案目前处于初步发展时期，在安全模型、通信效率等还存在没有解决的问题,距离真正应用还有一定的距离.

1 相关工作

PPML方法最早可追溯至2000年，Lindell等人[4]明确提出了允许两方在不泄露自己隐私的前提下，通过协作对联合数据集进行提取挖掘的方法.

传统的安全多方计算协议为了实现恶意敌手模型下的安全性，需要使用茫然传输(oblivious transfer, OT)、认证秘密分享、零知识证明、承诺等工具,使得安全多方计算协议设计严重依赖这些基础工具,效率较低.近年来,恶意敌手模型下基于Yao混乱电路的安全两方计算协议,以及基于秘密分享的安全多方计算协议都提出了高效的实现方案[5].

现有的基于安全多方计算协议的隐私保护机器学习方案有SecureML,ABY,ABY3,Trident,Swift等.其中Mohassel等人[6]提出的SecureML安全机器学习框架,由2个不合谋的参与方利用秘密分享执行安全两方计算协议.Demmler等人提出的ABY框架[7]利用Yao混乱电路来计算分段函数，该框架能够完成3种不同分享方式之间的转换，从而完成计算任务.ABY和SecureML两个方案在设计乘法协议时都利用Beaver三元组技术，因此方案的通信成本和协议的效率都并不理想.方案ABY3[8]在半诚实环境和恶意环境下，能够完成三方之间的算术共享、布尔共享和Yao共享，并且对SecureML[6]中的近似定点数乘法进行改进，使协议在三方参与环境下可以使用.但是ABY3方案均是专注于半诚实环境下的机器学习框架,在恶意环境下进行位提取,截断的效率都会不同程度地降低[9-10].

Trident方案[11]提出了最多可以容忍一方腐败的四方参与的隐私保护机器学习协议,在方案中对参与方要求比较高,通过引入一个额外的诚实参与方来提高协议在线阶段的效率,并且协议在安全性方面仅仅满足中止性,方案利用哈希值进行一致性检测,当出现不一致时,协议就会中止.当恶意参与方提供错误的值时,将导致计算中止,并且协议不会有任何的输出.虽然方案中都提出使用Abort的安全构建组件,但当出现争议时，不能保证协议一定有输出.只实现中止安全性的安全多方计算协议不能满足安全外包计算的要求，因为用户可能无法获得输出，导致用户的参与度降低.

2021年,Koti等人提出的Swift方案[12]中通过引入联合消息传递(joint message passing, JMP)原语,允许2个服务器将共有的消息发送给第3个服务器,当发现哈希值不一致时,没有中止协议,而是能够识别出诚实的服务器,将诚实方作为可信第三方(trust third party,TTP)服务器来完成计算.同时文中还将协议扩展到了第4个参与方,设计环境依旧是基于诚实大多数,在调用三方筛选协议进行哈希值一致性检测出现争议时，由于最多只有一个恶意方，因此恶意方只可能出现在3个服务器中，Swift方案将未参与筛选协议的第4个服务器作为TTP，参与方就会将消息发送给TTP,虽然方案能够保证在有恶意参与方的情况下保证用户一定可以获得输出结果，但对于作为TTP的参与方来说,就会掌握所有用户的敏感数据信息,不符合安全多方计算协议的初衷.

本文提出了一个基于秘密分享的高效隐私保护四方机器学习方案,在至多存在一个恶意敌手模型中，当协议出现争议时，能够准确从4个参与方中确定出2个诚实参与方，执行安全两方计算协议.本文设计的隐私保护机器学习方案主要贡献包括2个方面：

2)通过对方案的效率分析和对比,本文的四方协议与仅提供半诚实/被动安全性的高效诚实多数三方协议的性能相似，这表明添加第四方是实现主动安全而不损害性能的有效方法.其中乘法协议只需要3个参与方在在线阶段处于活跃状态，提高了在线阶段25%的通信.

2 预备知识

2.1 秘密分享

秘密分享是一个非常重要的基础原语[13-15],是许多安全多方计算协议的重要构造模块.如表1所示，4个参与方P={P0,P1,P2,P3}分享秘密v时的3种方式,这些分享都是在算数和布尔环上的.为了方便非交互通信,参与方利用Trident方案中的功能函数Fsetup为每个参与方建立预共享的随机密钥.参与方在分享秘密值v时，可以调用共享的密钥设置函数Fsetup获得满足条件的相应参数.

[·]-sharing:v∈2由3个参与方P1,P2,P3共同分享.参与方P1拥有[v]1,参与方P2拥有[v]2,参与方P3拥有[v]3并且v=[v]1+[v]2+[v]3.

〈·〉-sharing:v∈2由3个参与方P1,P2,P3共同分享.如果参与方P1,P2,P3依次拥有的值为(v2,v3),(v1,v3),(v1,v2),并且v=v1+v2+v3.

〖·〗-sharing:v∈2由4个参与方P0,P1,P2,P3分享,如果存在λv,mv∈2并且满足λv=λv,1+λv,2+λv,3,mv=v+λv,参与方P1,P2,P3都清楚地知道mv.

Table1 Secret Sharing Semantics

2.2 JMP原语

Swift方案中能够实现输出可达性的关键在于引入了JMP原语.JMP3PC协议在2021年由Koti等人提出.JMP原语允许2个服务器将公共消息中继到第3个服务器，以便中继成功或识别诚实服务器(或冲突对).如图1所示为3方参与的JMP原语的理想功能图.

如图2所示,JMP3PC协议内容简要来说,有3个服务器参与协议, 其中最多只有一个恶意服务器,通过JMP3PC协议可以确保输入一致性,并且当发生争议时,确保协议一定有输出结果.其中Pi,Pj作为发送方,Pk作为接收方.Pi发送值v给Pk,Pj发送值H(v)给Pk,接收方Pk将接收到的值与哈希值进行比较,如果哈希值不一致,通过JMP3PC协议可以确认出一个参与方作为TTP继续计算,并且不需要再次通信.

对于s∈{i,j,k},参与方Ps将bs=0作为检测哈希值不一致的标志比特.协议分为发送阶段和验证阶段.当检测到哈希值不一致时,协议将不同的情况进行分类并选择出TTP.如果Pi是沉默的,Pk没有接收到发送的v,Pk广播(accuse,Pi),那么Pk和Pi中必定有一个是恶意的参与方，这时选择TTP=Pj.类似地，Pk广播(accuse,Pj), 那么Pk和Pj中必定有一个是恶意的参与方，这时选择TTP=Pi.如果当Pk收到不一致的消息对(v,H(v*))时,设定bk=1, 并将bk发送给Pi,Pj,由这两方通过交换不一致标志比特相互进行交叉检验,若从Pk收到的或者从其他发送方接收到的比特为1,则这两方将自己的不一致标志比特设定为1.当服务器的不一致标志比特为1时,服务器会广播相应值的Hash结果.Pk的值来自它从Pi接收到的值.接下来按照具体协议来选出合适的服务器做TTP.

Swift方案将JMP协议扩展为4个参与方Pi,Pj,Pk,Pl，方案的模型依旧是至多只有一个恶意的参与方.但是当调用三方参与的JMP3PC协议时,一定可以确定3个参与方中存在一个参与方是恶意的,因此将未参与的JMP3PC协议的第4个参与方直接作为TTP,其他参与方将自己的消息发送给它,由作为TTP的参与方完成剩下的所有计算.接下来为了描述方案更加清晰，三方参与的JMP协议表示为JMP3PC, 四方参与的JMP协议表示为JMP4PC.

2.3 现实-理想范式

令π为一个协议,F为一个功能函数,令C为攻陷参与方集合,令Sim为一个仿真者算法.定义以下2个随机变量的概率分布：1)Realπ(κ,C;x1,…,xn).在安全参数κ下执行协议,其中每个参与方Pi都将使用自己的私有输入xi诚实地执行协议.令Vi为参与方Pi的最终视角,令yi为参与方Pi的最终输出.因此可以将输出表示为{Vi|i∈C},(y1,…,yn).2)IdealF,Sim(κ,C;x1,…,xn):计算(y1,…,yn)←F(x1,…,xn).输出Sim(C,{(xi,yi)|i∈C}),(y1,…,yn).

如果现实世界中攻陷参与方所拥有的视角和理想世界中攻击者所拥有的视角不可区分,那么协议在半诚实攻击者的攻击下是安全的[16-18].

给定协议π,如果对于任意一个现实世界中的攻击者A,存在一个满足corrupt(A)=corrupt(sim)的仿真者sim,使得对于诚实参与方的所有输入{xi|i∉corrupt(A)}概率分布Realπ,A(κ;{xi|i∉corrupt(A)})和IdealF,Sim(κ;{xi|i∉corrupt(Sim)})是在κ下不可区分的,则称此协议在恶意攻击者存在的条件下安全地实现了F.

3 新的基于秘密分享的四方安全多方计算协议

3.1 四方安全多方计算基础协议

3.1.1 秘密分享协议

参与方通过调用秘密分享协议∏Sh(Pi,v)产生关于〖v〗的秘密分享,如图3所示.秘密分享协议分为在线阶段和离线阶段.

当执行秘密分享协议∏Sh(P0,v)时,在离线阶段：参与方P0持有值v,使用预先共享的密钥来生成参数λv,j,并且λv=λv,1+λv,2+λv,3,参与方P0持有份额为(λv,1,λv,2,λv,3),参与方P1持有份额为(λv,2,λv,3),参与方P2持有份额为(λv,1,λv,3),参与方P3持有份额为(λv,1,λv,2).在在线阶段:参与方P0计算mv,并发送给P1,P0,参与方P1通过调用JMP3PC协议发送给P2,P0,参与方P1通过调用JMP3PC协议发送给P3.因此各参与方拥有的份额为参与方P0持有份额为(λv,1,λv,2,λv,3,mv),参与方P1持有的份额为(λv,2,λv,3,mv),参与方P2持有的份额为(λv,1,λv,3,mv)，参与方P3持有的份额为(λv,1,λv,2,mv).

当执行秘密分享协议∏Sh(P1,v)时,在离线阶段：参与方P1拥有值v,使用预先共享的密钥来生成参数λ,参与方P0持有份额为(λv,1,λv,2,λv,3),参与方P1持有份额为(λv,1,λv,2,λv,3),参与方P2持有份额为(λv,1,λv,3),参与方P3持有份额为(λv,1,λv,2).在在线阶段:参与方P1计算mv,并且发送给P2,P1,参与方P2通过调用JMP3PC协议发送给P3.因此各参与方拥有的份额为参与方P0持有份额为(λv,1,λv,2,λv,3),参与方P1持有份额为(λv,1,λv,2,λv,3,mv),参与方P2持有份额为(λv,1,λv,3,mv)，参与方P3持有份额为(λv,1,λv,2,mv).参与方P2,P3执行协议∏Sh(Pi,v)的过程和参与方P1类似,这里不再详细展开了.

如图4所示，执行协议∏ash(P0,v),参与方P0可以在离线阶段计算值v的〈·〉-sharing.参与方P0拥有值v,参与方利用提前约定好的函数共同生成相关的参数.参与方P1拥有份额为(v2,v3)，参与方P2拥有份额为(v1,v3), 参与方P3拥有份额为(v1,v2).注意在文中第4节乘法截断协议中完成r不同秘密分享方式的本地转换中可以用到.

3.1.2 重构协议

如图5所示,在重构协议∏Rec中,每个参与方可以从其他2个参与方中依次接收到自己缺失的份额和对应缺失份额的哈希值,参与方通过调用JMP3PC协议进行一致性输入检测,如果一致的话,那么该参与方可以根据自己持有的份额和收到的自己缺失的份额计算值v.如果收到的值不一致的话,则由JMP3PC协议选出的TTP和未参与JMP3PC协议的参与方进行安全两方计算来重构值v.例如,P0,P2调用JMP3PC协议发送λv,1给P1.如果JMP3PC协议的执行结果是TTP=P0,则由P0和P3来计算值v.

3.1.3 乘法协议

首先简单描述一下加法协议,对于输入x,y,参与方可以利用秘密分享方案的线性属性本地完成方案中的份额计算，即对于z=x+y来说，可以本地计算份额[z]=[x]+[y].接下来描述乘法协议,在协议执行过程中需要参与方进行交互，具体内容如图6所示：

乘法协议执行分为2个阶段：离线阶段和在线阶段.在离线阶段,需要参与方本地计算γxy的分享.其中γxy=λxλy.通过调用JMP3PC协议来验证其他参与方发送过来的份额的正确性.在计算过程中,通过调用∏zero协议[11]产生随机数目的是随机分配份额,以防止隐私泄露,注意这里的A+B+Γ=0.在在线阶段,协议的目的主要是计算mz,其中mz=z+λz=xy+λz=(mx-λx)(my-λy)+λz=mxmy-λxmy-λyλx+λxλy+λz.

3.2 四方协议框架

本文方案的参与方是由4个服务器P={P0,P1,P2,P3}组成,通过同步网络中私有和真实通道连接,最多容忍一个静态恶意敌手.

本文设计的四方协议如图7所示，当利用哈希值进行一致性检测存在争议时，通过调用JMP3PC三方协议一定可以找出一个TTP=Pi,由Pi和未参与JMP3PC协议的服务器进行下一步的计算.4个参与方P0,P1,P2,P3利用复制秘密共享,对秘密v进行分享,执行秘密分享协议∏Sh(P0,v)后,每个参与方持有的份额是：参与方P0持有份额为(λv,1,λv,2,λv,3),参与方P1持有份额为(λv,2,λv,3,mv),参与方P2持有份额为(λv,1,λv,3,mv),参与方P3持有份额为(λv,1,λv,2,mv).当执行重构协议，为了确保获得一致性输入，参与方会调用JMP3PC来发送份额，并进行一致性检测，当检测出不一致的情况时，假设调用JMP3PC协议的是P0,P1,P2三个参与方,并且输出结果为TTP=P2时，那么由P2和P3来执行安全两方计算协议，并将秘密值v重构出来.其他协议也是同样的过程,这里不再一一展开描述.

4 机器学习隐私保护组成模块

为了执行隐私保护机器学习,我们需要有效地实例化3个组件,其中主要包括共享截断、安全比较、非线性激活函数.

4.1 共享截断

协议在ABY3,Trident协议的基础上进行了改进.ABY3方案是在评估乘法门之后对份额进行截断,以较高的概率保留基础值；Trident方案通过不使用任何的布尔电路,从而将离线阶段的复杂性降到了常数.本文在2个协议的基础上,在满足诚实大多数的条件下,结合JMP3PC协议,保证在线阶段参与方可以接受到相应的份额,最后一定可以得到正确的输出结果.

协议的具体内容如图8所示.首先协议执行离线阶段，在执行协议∏mult(x,y,z)的离线阶段后,参与方本地计算r并进行截断后获得rt.参与方执行协议∏ash(P0,rt),获得〈rt〉，并通过验证H(m1+m2)≠H(c)等式是否成立来判断份额是否正确.协议执行在线阶段,与乘法协议在线阶段类似,z的截断值可以由〖z〗t〗=〖(z〗-r)t〗+rt获得.

4.2 安全比较

参与方检测x

4.3 激活函数

在隐私保护机器学习中最常用的2个激活函数为rectified linear Unit(ReLU)和Sigmoid(sig).

1)ReLU

2)Sigmoid

5 安全分析

5.1 正确性

(rd,1+rd,2+rd,3)+c=(r)-(2drt+rd)+

c=0+c=c.

5.2 协议安全证明

本文提供的安全性是基于理想世界或现实世界模拟来展开的描述[19-20].现实世界中参与方至多有一个是恶意服务器,我们用A来表示现实世界的敌手,用S来表示理想世界的敌手.证明来自于敌手的模拟视图和现实视图是不可区分的.

协议的证明过程简要来说,从输入共享阶段开始,S将诚实方的输入设置为0.模拟器可以从共享协议中提取A的输入.S可以获得整个协议的所有输入,因此S可以计算电路的所有中间值和输出.参与方P0,P1,P2,P3中至多有一个恶意参与方.除了图11所示协议的安全性证明,其他基本协议的证明也很容易推导出来,这里就不全部展开描述了.

5.3 隐私保护鲁棒性

本文提出隐私保护鲁棒性的4PC隐私保护机器学习方案,是针对JMP四方协议的扩展,可以更好地保护诚实方的隐私.在协议的执行过程中,正在参与JMP协议的3个服务器,当接收方接收到的哈希值不一致时,可以确认出恶意方在哪一对服务器中,同时确认出一定是诚实方的参与方作为TTP，由TTP和未参与JMP协议的第4个服务器进行下一步的计算.因此,该协议可以在恶意参与方破坏的情况下仍然保持正确的输出,同时诚实方不能恢复私有输入.在协议执行的过程中,我们可以准确地判断协议的问题出现在哪一步,能够更好地对服务器的性能进行综合评估，并且当协议中确认TTP后会及时广播.

在通过JMP3PC协议确认TTP后，TTP与未参与协议的参与方执行安全两方计算协议.方案能够更好地保护用户隐私,不会将全部的信息以明文的形式由一个参与方保存,同时锁定了可能的恶意方,并且恶意方在整个过程中不会得到额外的消息.协议的调用过程中不会泄露正在计算的私有信息,但仍然允许计算完成.诚实方不存储非协议的消息,在恶意方存在的情况下,能够保持计算的正确性.隐私保护鲁棒性协议的安全性和实用性具有非常重要的意义.

6 方案效率分析

6.1 通信开销

如何降低协议的通信量和轮数复杂度一直都是设计一个更加高效的隐私保护机器学习方案的关键.接下来主要包括本文涉及到的基本协议具体效率分析,如表2所示,将本文方案的离线阶段和在线阶段的交互轮数以及通信量与ABY3方案进行了详细的对比.通过对比可以发现，本文提出的改进之后的四方隐私保护方案降低了通信量.

Table 2 Communication Overhead of Protocol

从2个方面将本文提出的方案进行分析,包括线性计算协议和非线性计算协议.1)关于秘密分享的加法协议和常数的乘法是可以本地完成份额的计算,因此其线性属性可以以非交互方式来执行协议.2)秘密分享协议∏Sh在离线阶段通过使用Fsetup生成共享密钥.在在线阶段,当Pi=P0时,协议∏ash计算并发送值mv给其他参与方,并且调用JMP协议,确认收到了正确的mv，因此需要2轮交互和通信量是2.协议∏ash可以完整地在离线阶段执行.P0计算v3发送给P1.P0,P1调用JMP协议发送给P2.因此需要一轮交互和通信量是2位.对于发送给其他参与方也是类似的情况.3)重构协议∏Rec在在线阶段每一个参与方接收自己的缺失的份额并进行验证,因此需要的一轮交互和通信量为4位.4)乘法协议的执行分为2个阶段,在离线阶段,P1,P2,P3需要与其他参与方交互获得γxy的份额,同理，离线阶段,P1,P2,P3需要获得的份额，因此需要的一轮交互和通信量是3位.

机器学习的组成模块中进行非线性计算时，常用到截断协议、安全比较协议、激活函数等.本文涉及到的基本协议包括：1)协议∏MultTr在离线阶段,需要调用∏ash协议来产生关于γt的分享,通过判断哈希值是否相等来验证分享是否正确，因此需要2轮交互和6位的通信量.2)协议∏ReLU在离线阶段需要3轮交互和8+2位的通信量，在在线阶段需要4轮交互和8+2位的通信量.3)协议∏Sigmoid在离线阶段需要3轮交互和15+7位的通信量，在在线阶段需要5轮交互和16+7位的通信量.

6.2 方案对比

结合安全多方计算工具来实现隐私保护机器学习,不同的安全多方计算协议可以适用于不同的场景,因此出现了许多使用不同安全多方计算原语组合构建机器学习隐私的保护方案.如表3所示:

Table 3 Comparison of Privacy Preserving Machine Learning Schemes Based on Multi-party Computation

为了更好地理解本文提出方案的实现功能和应用范围，本文提供了多方参与的隐私保护机器学习相关方案在参与方个数、模型及方案的主要特征进行了对比.通过方案对比可以得出：1)ABY和SecureML只满足半诚实环境下的安全多方计算协议；2)Trident方案需要额外引入一个诚实的参与方；3)Swift方案虽然通过筛选协议选出了一个TTP，但是不论是三方还是四方的安全多方计算协议都是其他参与方把所有信息发给TTP继续计算，不符合安全多方计算协议设计的初衷；4)本文提出的四方隐私保护机器学习方案能够在协议发生争议时,筛选出2个诚实参与方继续执行协议，保证用户可以得到输出结果,不用担心因为恶意敌手的行为而拒绝服务.确定出的2个诚实参与方能够高效地完成安全两方计算协议.

7 总结与展望

近年来,隐私保护机器学习方案在实用性和模型准确性等方面取得了很大的进步,但是仍然有许多问题需要解决.基于安全多方计算的隐私保护机器学习中的模型设计和通信开销一直是研究的重点.本文提出了一个完整的四方参与的隐私保护机器学习方案,遵循诚实大多数的原则,不需要单独引入额外的诚实方,同时能够保证在有恶意参与方的情况下,协议依然能够正确计算保证输出.

下一步的工作主要由3个方面展开：1)关于方案参与方的数量问题,如何将协议的参与方个数扩展到N,并且协议实现的环境不再只是针对至多一个恶意参与方.2)如何在提升安全属性的前提下,将性能开销进一步优化.3)针对不同的应用需求和不同的应用架构,如何更好地保护模型参数信息、降低隐私泄露的风险,都是未来我们需要关注和解决的问题.

作者贡献声明：阎允雪提出了方案的具体思路和实验方案并撰写论文;马铭负责完成实验的对比分析并撰写论文;蒋瀚提出指导意见并修改论文.