姚氏百万富翁问题的高效解决方案

姚氏百万富翁问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的高效解决方案 姚氏百万富翁问题的高效解决方案 第36卷 1.36 第l4期 No.14 计算机工程 ComputerEngineering 2010年7月 July2010 ? 安全技术?文章编号:1o0o—3428(2ol0)14—0124—03文献标识码:A中圈分类号ITP305 姚氏百万富翁问题的高效解决方案 查俊,苏锦海,闫少阁,闫晓芳 (解放军信息工程大学电子技术学院,郑州450004) 摘要:姚氏百万富翁问题是安全多方计算的典型问题,但已有解决方案多数存在效率低的问题.通过采用0编码与1编码,将百万富翁 问题转换为集合交集问题,提出一种基于可交换加密函数的百万富翁问题高效解决方案,并进行了安全性证明.该方案无需复杂的模指数 运算,加解密运算为D(n),通信轮数为4,整体性能优于其他方案. 关奠词:百万富翁问题;编码;交集;可交换加密;安全性 EfficientSolutiontoYao'SMillionaires'Problem ZHAJun,SUJin-hai,YANShao—ge,YANXiao-fang (InstituteofElectronicTechnology,PLAInformationEngineeringUniversity,Zhengzhou4 50004) [Abstract]Yao'SMillionaires'problemisatypicalproblemofsecuremulti—partycomputation,butmostsolutionsareinefficient.Basedon commutativeencryptionscheme,thispaperproposesanefficientandsecuresolutiontomilli onaires'problem,whichreducestheproblemtotheset? intersectionproblemby0-encodingand1-encodingforprivateinputsProofofsecurityisfollo wedThereisnocomplicatedmodularexponentiation inthissolutionwhichonlyneeds0)encryption/decryptionand4roundsofcommunicationItis moreefficientthanothersolutions. [Keywords]millionaires'problem;encoding;set— intersection;commutativeencryption;security' 1概述 姚氏百万富翁问题…由AndrewC.Yao于1982年首次提 出.Yao给出了一个趣味性的例子:2个争强好胜的富翁Alice 和Bob在街头相遇,如何在不暴露各自财富的前提下比较出 谁更富有?经过文献[2]的研究,百万富翁问题已经发展成为 现代密码学中一个非常活跃的研究领域,即安全多方计算 (SecureMulti—partyComputation,SMC). 文献【1】就百万富翁问题给出了一个解决方案,但效率非 常低,计算复杂性为输入规模的指数函数,用于比较2个较 大的数时不实用;文献[2】利用算术电路解决了一般意义上的 安全多方计算问题,将其应用于百万富翁问题,计算及通信 成本均与输入规模呈线性关系;文献[3】直接针对百万富翁问 题,提出了一个基于茫然传输(ObliviousTransfer,OT)的解决 方案,利用简单的异或运算成功地解决了该问题;还有一些 学者将同态加密的思想应用于百万富翁问题,也取得了很 好的研究成果. 本文利用0编码与1编码,将百万富翁问题转换为集合 的交集问题,提出一种基于可交换加密函数的百万富翁问题 解决方案,其计算及通信复杂度明显降低.同时对该方案的 安全性进行了理论证明. 2预备知识 2.1数学模型 安全多方计算是一种分布式协议.在这个协议中,设 P={,,…,}是n个参与者集合,他们想要共同"安全地" 计算某个给定的有,z个输入和n个输出的函数 f(Jq,而,…,)=(y.,Y,…,),其中,函数,的n个输入 Xl,X2,…,分别由n个参与者,,…,秘密地掌握而不被 他人知道,在计算结束后,,只,…,分别得到输出 一 124一 百万富翁问题是一个典型的双方安全计算问题,其数学 描述如下:参与方Alice和Bob分别具有秘密输入X和Y, 双方协同计算以下函数: m= 用于解决该问题的协议万需要满足以下要求: (1)参与方Alice和Bob均形式化为概率多项式时间的图 灵机,且都为半诚实的.也就是说Alice和Bob在协议的执 行过程中将完全执行协议,但是他们也会保留中间计算结果, 试图推导出对方的输入. (2)正确性:协议1/"执行完以后,Alice返回1当且仅当 >. (3)Alice的保密性:Alice拥有X或.?')对于Bob来 说是不可区分的. (4)Bob的保密性:除了X和最终的结果f(x,),),Alice 不能得到任何信息. 2.2安全性定义 安全多方计算中的安全性证明采用了一个特殊的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 , 它通过定义一个理想模型,用理想模型仿真现实协议,如果 现实协议能被理想模型所仿真,且输出结果具有不可区分性, 那么现实协议就是安全的. 为了方便地给出半诚实模型下的安全性定义,首先引入 下列符号.假设协议的参与方分别为Alice和Bob.Alice和 Bob要计算的函数为f:(0,1J×{0,l}卜?f0,1}x{0,lr.函数 作者筒介:查俊(1986--),男,硕士研究生,主研方向:保密通信; 苏锦海,教授;闰少阁,闫晓芳,硕士研究生 收稿日期:2009—12.22E-mail:chazh~un@163.com f(x,)的第1个元素记为(,),第2个记为,_v),计 算函数厂的两方协议为.Alice和Bob在输入为(y)的情 况下执行协议得到的信息分别为WE(五),?日),其 具体值为{,',,m2,…,m,},({Y,,m,m!.…,}),其中,, 表示Alice和Bob拥有的随机数,m,表示所收到的第i条 消息.OUTPUTI(ty)(OUTPUT2'~(ty))表示Alice(Bob)在输入 为(,)的情况下执行协议.rt-时得到的输出结果,显然它隐含 在VIE(,),(VIEW;(,y))中. 定义1(半诚实模型的安全性J对于一个函数厂,如果存 在多项式时间算法(有时称为模拟器)s,S,满足以下关系: {Sl(,(,y)),(,y)} {(VIEW"(,y),OUTPUT~(,y)}.f1) {((,)),2(y,(,y))}…; {(OUTPUT~(工y),WE(,y)(2) 则认为协议安全地计算函数_厂,其中,表示计算不可 区分. 因此,要证明百万富翁问题解决方案的安全性必须构建 满足上述要求的模拟器S,S,. 2.30编码与1编码 本文解决方案的核心思想是通过0编码与1编码,将百 万富翁问题转换为集合交集问题,从而简化问题的求解. 令s=slls…s.?{0,1)为一个长度为n的二进制数据流, 表示需要进行比较的数据. 定义2二进制数据流s的0编码由如下形式表示: Sl={sn'?=0,1?i?} 定义3二进制数据流s的1编码S由如下形式表示: S={sns…sJsi=】,1?i?} 其中,ISoI?n,ISI?. 如果将数据x进行1编码S,数据Y进行0编码S?,可 以得到当且仅当S和S?的交集非空时,有x3'.需要注意 的是在进行0,1编码之前,数据x,_v的二进制数据流长度必 须相等,不足的高位补0. 定理x大于Y的充分必要条件是S,SIl的交集非空. 证明见文献[4】. 3半诚实模型下百万富翁问题解决方案 在介绍方案之前,首先说明可交换加密函数.简单地说, 满足性质Ea(()):Eh(Ea())的函数E(?)称为可交换加密函 数,其中,,()表示用密钥a加密. 本文基于0编码与1编码的结果提出了一种新的半诚实 模型下百万富翁问题的解决方案.假设需要保密比较2个自 然数x,Y的大小,首先需要对x,),所对应的二进制表现形 式分别进行1编码与0编码,得到集合S,S,然后判断 2个集合的交集是否为空,从而得到比较结果.可以看出, 如果逐次比较集合S,S?中的所有元素得到交集,需要 O(n)次操作,但是本文的目的不在于得到所有的交集数据, 而只需要判断S:,S:'的交集是否为空,因此使用可交换加密 函数判断集合的交集是否为空,从而得到问题所需的比较 结果. 输入集合:,I_ 输出n?f 根据前面讨论的结果,本文的解决方案如下: SteplA1ice和Bob通过协商获得一个可交换加密函数 E,并设定各自的私钥",b. Step2Alice和Bob分别计算: f)={().,(sl),….(31)} (?)={(SII).().…,()} 其中,s:,,sl:(1?i?)分别表示编码集合s,s?中第i个 元素.双方交换加密结果E(3IJ,和Eb(?). Step3Alice计算: E… E, o))={Eo(E…o.)),E((?)),…,(())} 将结果发送给Bob. Step4Bob计算: Eb(E~())={(:)),((1),…,(())} 从而可以得到ns: Step5Bob将最终的比较结果告诉Alice. 从上述过程可以看出lEb(E:))nE一一o))l=Inl. 如果J(())n({~SO-)J?0,则有Y,否则,?Y. 在方案的执行过程中,输入的数据都进行了加密处理,因此, 不会导致用户信息的泄漏. 4方案安全性及效率 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 4.1安全性分析 下面利用安全多方计算的安全性理论证明本文方案的安 全性.在本文方案的执行过程中,有: OUTPUT;(,)')=(.y)=IEh(E,())n((?))l= lnSll10(,y)=L(x,y): f(())n((?))f=fnSy.f WE(.y)=f,_,E(Si),(s?),(Eh(,o))} VIE(,y)={Y,r2,(s?),(),(:)),((?))} 其中,x,y表示Alice和Bob的输入;',为随机数.假 设lS:n?!=k,首先构造S模拟VIEW,(,_v)使式(1)成立. (】)S接受(,y))=(,)作为输入,同时选择一个可 交换加密函数E和密钥a,另外随机选择一个密钥b.S,构 建一个数据y,使得由Y'得到的0编码集合中存在对(,), 满足=S,I,|'=?f,…一:.= (2)根据上述解决方案,S.模拟计算: (SI):{().(SI),…,()) ()={(?).Eb(s)?一,El,(7)} (3),计算E((I1)1,(()及l(())n ((()j. (4)通过构造数据Y得到其0编码,则必存在k对(f,』) 满足: ((=((S,O),((5IlJ_),…,(E.1)= E(s?,) 一 l25— 因此,有如下结论: J((())n(((?))I=lslnI=k 令(,(),))={,,(),(s),((o))},则有 l(,(,y),L(x,))={,,(:),,(),(Eb()),k} {?z(,y),OUTPUT2~(,y)}={,(),(),((o)),} 由此可以推出 {Sl(x,(,),)),,2(,y)}{(V1EW~(,y),OUTPUT;(,y)}. 用类似的方法还可以构造一个模拟器S,,使得 {((,),)),()',(,y)))=-{(OUTPUT1(,),VIEW~(,y)l. 这样就完成了定理的证明. 4.2效率分析 作为安全多方计算协议的一个重要组成模块,百万富翁 问题解决方案的效率直接影响整个安全多方计算协议的效 率.下面针对本文提出的协议分析其计算及通信复杂度,并 与其他相关的百万富翁问题解决方案进行比较. (1)计算复杂度:假设0<max(Ixf,iy1)=n,其中,(}Yf) 表示输入(Y)的长度(二进制形式).本文方案需要D(,z)次加 解密运算.需要注意的是,与其他解决方案中公钥密码系统 的加解密运算不同,本文方案采用的是对称的可交换加密函 数,其加解密效率高于其他方案.另外,虽然模指数运算是 隐藏信息的一种常用技术手段,但该运算需要消耗大量的计 算资源,而本文方案不需要复杂的模指数运算(IJn解密算法中 除外),在这一点上,计算复杂度大大降低,其他简单运算需 要O(n).相关方案计算复杂度比较结果见表1. 表1各方案计算及通信复杂度比较 (2)通信复杂度:衡量一个计算方案效率的首要指标是其 计算复杂度,但是对于安全多方计算来说,仅计算复杂度无 法全面地描述一个解决方案的优劣.在安全多方计算中,参 与方相互之间要进行通信,而在通信过程中,所有参与方都 需要等待自己所需的数据,因此,通信复杂度也是衡量安全 多方计算效率的一个重要指标.本文用通信的轮数表示通信 复杂度,提出的解决方案包括3轮用以传输加密结果的通信, 1轮传输最终比较结果的通信,总的通信复杂度为4轮.由 表1可以看出,本文的解决方案整体性能优于其他方案. 5结束语 本文利用0编码与1编码构造了一种新的百万富翁问题 解决方案.该方案避免了复杂的模指数运算,有效地减小了 计算与通信复杂度,同时利用安全多方计算中理想模型与现 实协议相比较的方法,证明了方案的安全性.因此,本文方 案是一个安全的解决方案,高效地解决了无信息泄漏的数值 比较问题. 参考文献 【1】YaoAC.ProtocolsforSecureComputation[C]//Proceedingsofthe 23rdIEEESymposiumonFoundationsofComputerScience.Los Alamitos,CA,USA:IEEEComputerSocietyPress,1982:160—164. [2]GoldreichO,MicaliS,WigersonA.HowtoPlayAnyMental Game[C]//Proceedingsofthe19thAnnualACMConferenceon TheoryofComputingNewYbrk,USA:ACMPress,1987:218—229. [3]IoannidisI,GramaA.AnEfficientProtocolforYao'SMillionaires' Problem[C]//Proceedingsofthe36thHawaiiInternational ConferenceonSystemSciences.Hawaii,USA:Is.n.】,2003. [41SchoenmakersB,TuylsP.PracticalTwo—partyComputationBased ontheConditionalGate[C]//ProceedingsofAsiacrypt'04.Jeju, Korea:Is.n.],2004 [5JLiShundong,DaiYiqi,YouQiyou.AnEfficientSolutiontOYao'S Millionaires'Problem[J]ACTAElectronicaSinica,2005,33(5): 769.773. 编辑张正兴 原始签名者的身份标识,代理签名者B的身份标识及B的代如何减少由于代理者 私钥或是代理密钥泄漏所带来的损失. 理权限,使得本文提出的方案还具有强可识别性,强不可否本文基于前向安全的思 想提出了一个前向安全的代理多重签 认性及抗滥用性.名方案,在Hash函数的安全性假设及强RSA假定下分析了 (3)安全性的其他方面方案的安全性,证明该方案不仅满足一般代理多重签名方案 该方案中规定了代理终止时间,从而具有限制代理权的安全性,而且具有前向安全 性. 了签名权和代理权.算机工程,2009,():164-165. 4.3 ………………klyf~$)h蓑_lt/-脯搬鲱璐名 … 在譬的情况下,代.名妻篓..段的答苎孝望:张国印-锥曲线的前向安全环泄漏 ,由于=o'x~, modN攻击者无法得到,即使是原始签,签案. . 算,,3.4(6) :33- 一 34 … . .………一. 名人联合也只能得到modN,由强RSA假定还是不能求[4JAbdallaM,ReyzinL.ANewForward—secureDigitalSignature 泄漏,攻击者仍无法伪造代理签名者在第(<)时段的代理签名,f5】王玲玲 ,张国印,马春光.前向安全的多重数字签名方案【J].计 因为由强RsA假定攻击者无法从=modN=modN=算机,2004,27(9):1177.1181. …= 《modN得到.因而本文提出的方案具有前向安全 性.[61ItkinsCsReyzinLlForward'secureSignatureswithOptimalSigning 5结束语:nf1『11d:?of哪o'叭-Berhn'Gennany'Sng 在传统的代理多重签名方案中,仍没有有效的方法解决编辑索书志