安全多方计算应用的隐私度量方法.pdf

信息安全研究第10 卷第1期2 0 2 4年1月Journalot information Security ResearchVol.10No.1Jan.2024DOl:10.12379/j.issn.2096-1057.2024.01.02安全多方计算应用的隐私度量方法熊维王海洋唐祎飞刘伟1(神州融安数字科技(北京)有限公司北京2(北京国际大数据交易有限公司北京10 0 0 2 0）3（大数据协同安全技术国家工程研究中心北京10 0 0 7 1)()Privacy Measures for Secure Multi-party Computing ApplicationsXiong Weil,Wang Haiyang,Tang Yifei,and Liu Wei!1(Rongan China Digital Technology(Beijing)Co.,Ltd.,Beijing 100086)2(Beijing International Data Eachange Co.,Ltd.,Beijing 100020)3(National Engineering Research Center for Big Data Collaborative Security Technology,Beijing 100071)Abstract The privacy protection ability of secure multi-party computing application to inputinformation depends on the underlying security mechanism on the one hand,and on the other handdepends on the task functions.At present,the research on secure multi-party computing mainlyfocuses on the security mechanism to prevent information leakage in the process of computing.However,there are few studies on the measure of task functions ability to protect the inputinformation of the participants.The problem that each participant of the task function deduces theinput information of other participants through the legitimate input and output cannot be preventedby the security mechanism of secure multi-party computing,so the measurements of the privacyprotection power of the task function are related to the concrete implementation and application ofsecure multi-party computing schemes.In this paper,according to the information entropy model,the concepts of average entropy and specific entropy are defined from the point of view of theattacker,and a method to calculate information benefits is proposed.Then,the privacy protectionstrength of the specific application scheme of secure multi-party computing schemes is measured bycalculating the ideal privacy loss of the objective function and the actual privacy loss of the actualsecure multi-party computing application.Key words secure multi-party computing;privacy metric;information entropy;computing informationbenefits;privacy loss摘要安全多方计算应用对输入信息的隐私保护能力，一方面依靠底层的安全机制，另一方面依靠具体的目标函数.目前对安全多方计算的研究主要集中于防止计算过程泄露信息的安全机制；而对部署安全多方计算的目标函数对参与者的输入信息的隐私保护能力的度量或评估方法研究较少。目标函数的各参与者通过合法的输入和输出推导其他参与者的输入信息的问题不能由安全多方计收稿日期：2 0 2 3-0 4-2 5引用格式：熊维，王海洋，唐祎飞，等。安全多方计算应用的隐私度量方法J。信息安全研究，2 0 2 4，10（1)：6-1106100086)学术论文.ResearchPapers算的安全机制阻止，因此对目标函数的隐私保护强度的度量关乎安全多方计算方案的具体实施应用.根据信息摘模型，从攻击者的角度定义平均熵和特定熵的概念，提出计算信息收益的方法.进而，通过计算目标函数的理想隐私损耗和实际安全多方计算应用中的实际隐私损耗，衡量安全多方计算具体应用方案的隐私保护强度.关键词安全多方计算；隐私度量；信息熵；计算信息收益；隐私损耗中图法分类号TP309.2传统的计算模型如单机状态的图灵机模型，其计算的输人、输出和运算程序都由一方独自占有.多方计算是指由多个参与者提供数据或计算资源并进行联合计算的情况，其相对于单方计算会引发诸如公平性、数据隐私、计算成本等问题.常见的概念例如安全多方计算、外包计算、分布式计算、多方提供数据的中心式计算等均属于多方计算的范畴.其中,安全多方计算（secure multi-partycomputation，M PC)的基本思想是Yao 等人 1于20世纪8 0 年代提出的，它是指在无可信第三方的情况下，多个参与者可以安全地计算一个约定函数的系统.安全地计算指在函数计算过程中每个参与者不能获得其他参与者的输入和输出信息。影响安全多方计算方案隐私信息泄露的因素众多，设计一个既安全又高效的安全多方计算的实现方案很具有挑战性，这促使人们寻求方案可用性和隐私性之间的平衡.目前，安全多方计算研究多集中在如何防止计算过程中隐私信息的泄露，也就是说如何防止1个参与者通过计算过程获得其他参与者输人或输出的信息.然而，1个参与者通过其合法的函数输人和输出推导出其他参与者输人信息或者输出信息的可能性却没有进行充分研究.本文关注的是理想多方计算情况下目标函数本身对参与者输入提供的保护程度，只有能够衡量各个参与者在这种情况下隐私泄露的程度，才能真正评估各个参与者在实际进行安全多方计算应用过程中的隐私泄露情况.因此，隐私度量的研究对安全多方计算的应用和部署具有理论意义和实践价值。基于ShannonL21提出的信息嫡理论，本文首先研究并提出理想多方计算模型下目标函数对各方数据隐私保护的度量方法，进而提出实际情况下的安全多方计算的隐私保护强度的概念，最后提出隐私保护成本的计算方法.本文主要贡献如下：1)针对理想多方计算模型，从攻击者的角度定义平均熵和特定熵的概念，提出计算信息收益的方法，从而描述在攻击者的视角下其他参与者特定的输人对攻击者输出分布的影响程度；2)通过计算目标函数的理想隐私损耗和实际安全多方计算应用中的实际隐私损耗，衡量安全多方计算具体方案的隐私保护强度；3)为达到实际安全多方计算方案实用性与隐私性之间的平衡，需要对计算过程中的成本进行量化，本文提出计算目标函数需要付出的额外通信和计算开销来衡量隐私保护成本.1相关工作目前，隐私度量的研究主要集中于特定的隐私计算领域如位置服务、社交网络和数据挖掘等.王彩梅等人3提出基于信息熵度量匿名通信系统的隐私度量方法.其他方案主要是为特定协议4-6 1量身定做的简单概率模型的隐私度量方法.另外一些方案7-9 则是使用形式化的方法提供更高层次的抽象和更严格的匿名分析.彭长根等人10 于2 0 16 年提出基于Shannon信息论的几种隐私保护信息熵模型.隐私保护基本信息模型是将发送方拥有的信息集称为隐私信源，将接收方获取的信息集称为隐私信宿，隐私的泄露渠道假设为通信信道.该方案主要研究在隐私保护机制不泄露隐私信息的前提下攻击者通过隐私通信信道获取隐私信息的隐私度量方法.上述研究主要针对匿名性和位置隐私保护等信息发布场景的隐私保护度量，这些应用场景只对隐私信源信息进行一次隐私保护处理，且隐私保护处理过程固定.然而，在安全多方计算或者隐私计算11-12 1的应用场景下，各参与者之间进行多网址http:/1 07信息安全研究第10 卷第1期2 0 2 4年1月Journalotinformatien Security ResearchVol.10No.1Jan.2024次交互所联合实现的任务可以是任意的目标函数，因此，上述模型未充分考虑信源与信宿之间具有多次交互或者计算函数为任意函数的复杂情况。衡量安全多方计算目标函数对特定参与者的输入信息的隐私保护能力的另一个角度是密码分析.密码分析技术是测试函数安全强度的最有力工具.可将目标函数的隐私度量看作一种密码分析.对于MPC的计算函数z=f（,y)，由参与者P。输人，y由参与者Pi输人，计算结果由参与者P。获取.计算函数可转换为布尔函数的正规型表示，输人和输出以比特形式表述，可将函数f(,y)视为加密函数，输人视为明文消息，输入视为密钥，输出视为密文.由多个明文和密文对以及加密函数f（分析密钥信息的过程是典型的“选择明文攻击”目前，安全多方计算主要包括使用姚氏混淆电路1、秘密分享技术13、同态密码技术14等进行安全计算一个目标函数的方案.这些方案的设计更关注目标函数计算过程的安全性，却忽略了目标函数的输人及输出本身所带来的隐私信息泄露.Lindel115指出确保目标函数不泄露输入信息是隐私计算得以应用的隐含前提条件.2理想多方计算隐私度量方法对函数f(i,2,)=(yi,y2,y,),具有n个参与者Pi,P2，,Pn 进行联合计算,Pi持有输人1,P持有输人2，,P，持有输人n，所有输入的定义域是公开的，除此之外，每个参与者无法获得与其他参与者的输人相关的任何信息；所有参与者都无法获得关于函数计算过程中的任何信息（如由一个可信的中心收集各个参与者的输入，再执行运算，最后将相应的计算结果发送给相应的参与者，可信中心不会与任何参与者共谋）；函数计算结束后，每个参与者获得既定的计算结果，P1获得输出1,P2获得输出y2，,P，获得输出yn，每个参与者无法获得关于其他参与者输出的任何信息。上述情况是多方计算的理想情况，各方均不会从计算过程中获取任何其他的信息，可信中心也不会向任何一方泄露更多信息，在这种情况下，1个参与者想要攻击其他参与者只能通过其自身081的输人和输出以及目标函数的性质完成。对上述函数f(1,2,)=(y1,y2,y，），为适应计算设备的运算环境，假设函数的输人和输出均为离散的情况，设参与者输人的定义域分别为S1,S2,Sn,1Es1,2Es2,a,ESn，|s 1，ls 2 l，s,l分别表示定义域中可能的输人值的个数；设参与者输出的值域分别为U1，U2,.,Un,yi EUi,y2 E02,yn EUn,l0i l,2 l，n|分别表示输出值域中可能的输出值的个数。为简化模型的复杂程度，以下仅考虑两方计算的情况.多方计算函数可以简化成两方计算函数,对于多方计算函数f（1,2，,n）=（y i，y2，,y）,可假定在最恶劣的情况下,其中n一1方参与者共谋以窥探其中1个参与者的输人和输出情况，那么共谋的n一1方参与者会获得彼此之间的输入和输出信息，此时模型则等价于上述两方计算模型,共谋的n一1方作为一个参与者,被攻击的一方作为另一个参与者。对于只有两方参与的目标函数f（1,2）=（y 1，y 2），定义计算信息收益的概念，揭示在参与者P的视角下参与者 P1的特定输入1对参与者P的输出y2分布的影响程度.2.1平均炳设目标函数f(1,2）=（y 1,y 2)的2 个参与者分别为P1和P，在理想的多方计算条件下（计算过程不泄露任何信息），参与者P（攻击者)试图只通过其输人2和输出y2分析参与者P1的输人1或者输出y1.在上述环境下，参与者P2遍历PI的输入1和P2的输入2，构建函数输人和输出之间的对应关系，统计参与者P2的输出y2在输出值域 2中每个可能值的频数ai，a;表示值域2 中的第i个输出值的频数，当参与者P1的输人1和参与者P2的输人2的概率分布已知时，采用加权统计1021方法，设每个可能输出值的输出概率为i2aj-1定义目标函数f（1,2）=（y12)关于参与者P2的输出y2的平均熵U2H(f(P2.2)=2022aj 1b(aiaiZai12学术论文.ResearchPapers输出y2每个可能取值的频数的加权统计方法：当参与者P1的输人1和参与者P2的输人2的概率分布已知时,参与者P1的输人1的每个可能取值的概率分别为（p（），p（），(ls1l)）),参与者P的输人2的每个可能取值的概率分别为(p(),p(),p(s21),对于每个可能输人(),)）(1a l s 1,1b 1s2l),统计目标函数（，)的输出2 的频数时,其计人个数需要乘以权重p（a）p（）.函数输出的平均熵H（f(P2 y 2)）体现所有输人对P2输出的分布影响.2.2特定炳在上述环境下，固定P1的输人1为定义域S1中一个特定的值（Esi）,参与者 P2遍历所有可能的输人2，则参与者P2可获得新函数f(Pia)=f(,)=(yi,y2)的所有可能输出y2,f(Pia)表示固定参与者Pi输入为i=的函数；参与者P构建函数(Pi.)=f（，）输人和输出之间的对应关系，统计P2的输出y2在输出值域 2 中每个值的频数bi，b；表示 2 中的第i个输出值的频数，当参与者Pi的输入1和参与者P2的输人2的概率分布已知时，采用加权统计/12方法,设每个可能输出值的输出概率为b：b，j-1定义固定目标函数f(1,2）=（y 1,y 2)中参与者Pl的输人1=时关于参与者P的输出y2的特定10212-b:/2b;b(b:/2b,)H(f(P2.2.Pi.a)=1-1由于固定参与者P1 的输入，那么新函数f(Pi)的参与者P2输出的值域是原来值域2 的1个子集 2.该定义体现具体的参与者P1的输入为1=时对参与者P输出的影响.2.3信息收益对于参与者P1的特定输入1=，定义参与者P的输出关于参与者P1的输人1=时的信息收益为“函数输出的平均熵”与“函数输出的特定嫡 之间的差值或者比值，即H（f(P2）一H(f(P2 2 Pi.a)或者 H(f(P2 2)/H(f(P2/2.P1.a).差值越大或者比值越大表明该特定输人对参与者P2的输出分布影响越大，参与者P2越容易从其自身的输出推断出参与者P1的值.该定义可以理解为参与者P有一个特定的数据1=与参与者P共同计算函数f（1,2）,参与者P2通过不断试探的方法，也就是遍历其输人2获得额外的输出信息，以此推断参与者P1的输人情况.当参与者P2发现其输出熵严重偏离函数的平均情况(差值越大/比值越大)即可判定参与者P1的输人值.3安全多方计算的隐私保护强度3.1理想隐私损耗目标函数f(1,2)=（y 1,2)的2 个参与者分别为P1和P2,在理想的多方计算条件下（计算过程不泄露任何信息），定义“隐私损耗”的概念，揭示参与者P通过其输入2和输出y2推断出参与者P1输人1的可能性.在上述情形下，参与者P遍历P1输人1和P2的输人，构建函数输人和输出之间的对应关系，据此参与者P构建在其特定的1个输人2=和输出y2=时参与者P1的所有可能的输人集合S(a1=-y2=），设|s(a12=.y2=|表示该集合中元素的个数,则参与者P2对于1个特定的输人2=和输出y2=能以一的s(a122=,y2=)概率确定参与者P1的输人1，定义目标函数f(i,2)=(,y2)在2=和输出2=时参/.1021与者P1输入的理想隐私损耗为L（1，2=，j-1y2=,f(a1,a2)=该定义表明参与者P1的输人1取1个特定值的可能性由原始的上升为S隐私损耗的值越大则确定输人具体值的可能性越大。3.2实实际隐私损耗在理想的多方计算场景下，各参与者仅知道各自的输人和输出，而不知道其他的任何信息，但在实际的安全多方计算实现方案中，如基于同态密码的委托计算、基于秘密分享的安全多方计算等方案中，各方在没有可信第三方的情况下使用网址http:/ 1 091111信息安全研究第10 卷第1期2 0 2 4年1月Journalotinformatien Security ResearchVol.10No.1Jan.2024基于密码或者信息论的安全措施进行数据的交换，计算结束后各方可以获得与理想情况下的相同的输出，但除此之外各方都会获得大量的中间交互信息实际的安全多方计算方案可以模型化为原目标函数经过一系列的等价变换最终获取与理想情况下的目标函数相同结果的过程.所谓等价变换指2种不同的运算过程对相同的输人都得到相同的输出结果.设在理想计算环境下，目标函数f（1，2）=（y 1,y 2）的2 个参与者分别为P1和P2，输人分别为1和2，相应的输出分别为yi和y2.设目标函数f(i,2）=（y 1,y 2)安全等价变换为f(1,2)=fm(.fs(f2(fi(i,a2),.),.),）=（y 1,y 2），对相同的输人（1，2），安全多方计算函数（1，2）和理想情况下的目标函数f(1,2)输出相同的结果（y1,y2).安全多方计算函数f（1,2)由m个中间函数fi()，f 2（，f（)复合而成，每次中间函数运行结束后，各方均会获得相应的输出（y(1.1)，ya,2),(y(2,1)，y(2,2),（y(m.l),y(m.2),其中(i,1)为第i个中间函数的参与者P,的输出,y(i.2)为第i个中间函数的参与者P2的输出；并且各方会根据前一个中间函数的输出重新构造对下一步中间函数的输入（(1,1)=1,(1,2)=2），（(2,1)，(2.2),(m.1)，(m.2),其中(i,1)为第i(1im)个中间函数的参与者 P1 的输人,(i.2)为第i个中间函数的参与者P2的输入.概括来讲,中间输入和输出等价于实际安全多方计算过程中各方通过交互所获得的数据并执行下一次运算的过程。参与者P1在整个安全运算过程输人数据视图变化为a1=a.1(2.1)(m.),输出数据的视图变化为(l.1)(2.1)(m,l)=1;参与者P2的输人数据视图变化为2=(1.2)(2.2)(m,2)，输出数据的视图变化为(1.2)y(2,2).y(m,2)=y2 参与者P2固定输入2=和输出2=时，第i个中间函数fi(fs(f2(fi(1,2),),),),lim的隐私损耗为L=L（1,2=,yi.2),f,(f3(f2(fi(i,2),.),.),.),定义其中最大的隐私损耗为安全计算方案于（1，2)=fm(fs(f2(fi(1,2),.),.),.)=(y1,y2)在参与者P2输人2=和输出y2=时101参与者P1的输人1的实际隐私损耗为L(12=,y2=,f(1,2)=max(L;1iResearchPapers为T(f(1,2,a,)=n(T(fi(1,2,.,an)+T(f2(.)+.+T(fm(),n方参与者均需要在本地执行相关计算.隐私保护成本如下：额外的通信开销为2 mn一2 n次数据传输，额外的计算开销为T(f（a 1，2,)-T(f(i,2,.,cn).因为达到理想情况下的隐私保护强度会引发通信花费大、计算消耗多等问题，所以实际隐私损耗和计算成本都不是越小越好.在实际应用中，需要综合考虑隐私保护成本和隐私度量情况评估安全多方计算方案的实现，达到方案实用性与隐私性之间的平衡。5结语随着学术界、工业界对安全多方计算越来越重视，实际应用的落地需求越来越强烈.此时，度量目标函数本身、安全多方计算方案组合及工程优化过程中的隐私损耗的重要性日益突出.本文试图针对隐私计算领域提供参与者衡量方案安全性的框架，以此为基础对安全多方计算的实际应用可行性进行了量化评估参考文献i Yao A C.Protocols for secure computations C/Proc ofthe 23rd Annual IEEE Symp on Foundations of ComputerScience.Piscataway,NJ:IEEE,1982:160-1642Shannon C E.A mathematical theory of communicationJ.Bell System Technical Journal,1948,27(3):379-4233王彩梅，郭亚军，郭艳华。位置服务中用户轨迹的隐私度量J.软件学报，2 0 12，2 3（2）：352-36 04Reiter M K,Rubin A D.Crowds:Anonymity for Webtransactions JJ.ACM Trans on Information and SystemSecurity,1998,1(1):66-925 Wright M,Adler M,Levine B,et al.An analysis of thedegradation of anonymous protocols C/Proc of theNetwork and Distributed System Security Symp.SanDiego:The Internet Society,2002:1-126 Shmatikov V.Probabilistic analysis of anonymity C/Proc of the IEEE Computer Security Foundations Workshop.Piscataway,NJ:IEEE,2002:119-1287 Schneider S,Sidiropoulos A.CSP and anonymity C/Proc of European Symp on Research in Computer Security.Berlin:Springer,1996:198-2188 Shmatikov V.Probabilistic analysis of an anonymitysystem JJ.Journal of Computer Security,2004,12(3/4):355-3779 Syverson P F,Gray J W.The epistemic representation ofinformation flow security inprobabilistic systems C/lProc of the 8th Computer Security Foundations Workshop.Piscataway,NJ:IEEE,1995:152-16610彭长根，丁红发，朱义杰，等.隐私保护的信息熵模型及其度量方法J.软件学报，2 0 16，2 7（8）：18 9 1-19 0 311中国信息通信研究院安全研究所.隐私保护计算技术研究报告（2 0 2 0)EB/OL.北京：中国信息通信研究院，2 0 2 02023-05-11.http:/ 0 2 2，8（2：12 2-12 813Shamir A.How to share a secret J.Communications ofthe ACM,1979,22(11):612-61314Gentry C.Fully homomorphic encryption using ideallattices CJ/Proc of Annual ACM Symp on Theory ofComputing.New York:ACM,2009:169-17815 Lindell Y.Secure multiparty computation（M PC)EB/OLJ.20202023-05-11.https:/eprint.iacr.0rg/2020/300熊维硕士.主要研究方向为信息安全和密码学.wei.xiong 王海洋博士.主要研究方向为数据流通和数据交易平台唐祎飞高级工程师.主要研究方向为数据安全和数据流通刘伟博士，主要研究方向为信息安全和隐私保护。网址 http:/1 11