《半诚实模型下安全多方排序问题的研究.pdf》由会员分享，可在线阅读，更多相关《半诚实模型下安全多方排序问题的研究.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、半诚实模型下安全多方排序问题的研究肖 倩1,3,罗守山1,3,陈 萍2,吴 波4(1.北京邮电大学软件学院,北京100876;2.北京邮电大学电信工程学院,北京100876;3.西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安710071;4.北京邮电大学理学院,北京100876)摘 要:安全多方排序问题是百万富翁问题的推广问题,用于n个参与方在不泄漏各方秘密输入的前提下比较出其输入在全体输入中按照一定顺序所处的位置.本文首先提出了半诚实模型下基于同态加密的安全两方排序协议.然后将该协议推广到多方排序的情况,并提出两种提高效率的改进算法.最后本文还提出了基于模糊贴近度的安全多方
2、排序协议,并对这几个协议的安全性和效率做了分析、比较.关键词:百万富翁问题;安全多方排序;半诚实模型;同态加密;模糊贴近度中图分类号:TN91811 文献标识码:A 文章编号:037222112(2008)0420709206Research on the Problem of Secure Multi2party RankingUnder Semi2honest ModelXIAO Qian1,3,LUO Shou2shan1,3,CHEN Ping2,WU Bo4(1.School of Software Engineering,Beijing University of Posts an
3、d Telecommunications,Beijing100876,China;2.School of Telecommunication Engineering,Beijing University of Posts and Telecommunications,Beijing100876,China;3.National Key Laboratory of Integrated Service Networks,Xidian University,Xian,Shaanxi710071,China;4.School of Science,Beijing University of Post
4、s and Telecommunications,Beijing100876,China)Abstract:Secure multi2party ranking is a problem generalized from the millionairesproblem,which can be used by n peo2ple to know about their secretsorder among all their inputs without leaking further information.Through the study on millionairesprotocol,
5、we presented a secure two2party ranking protocol under semi2honest model based on homomorphic encryption.Then wegeneralized it to secure multi2party ranking,and we presented two algorithms whose efficiency are both improved.Finally,we gavea secure multi2party ranking protocol based on fuzzy nearness
6、 degree,and we analyzed the efficiency and security of these proto2cols.Key words:millionairesproblem;secure multi2party ranking;semi2honesty model;homomorphic encryption;fuzzy nearnessdegree1 引言 百万富翁问题是安全多方计算中一个非常重要的分支,由该问题又引申出安全多方排序问题.最早由A.Yao1提出了一个重要的安全多方计算协议 百万富翁协议:两个百万富翁在不泄漏各自财富信息的前提下比较出他们谁更富有.
7、将问题推广到多方,假设有n个参与方,每一方都拥有一个秘密输入mi,他们希望在不泄漏自己秘密输入的前提下得到其输入按照从大到小的顺序在这n个秘密输入中所处的位置,这就是安全多方排序问题.A.Yao在文献1中提出的百万富翁协议的复杂度是指数级的,因此不实用.近年来人们针对现有方案效率低、不实用等问题,设计出各种能够提高效率的百万富翁协议2-8,其中文献7中设计了一个常数复杂性的百万富翁协议,能够比较出两方秘密输入之间的关系究竟是“”,还是“”.现在虽然已经有很多有效的百万富翁协议,但是能够将“相等”关系单独区分出来的协议却很贫乏.这就使百万富翁协议在安全多方排序问题上的运用变得十分困难.本文首先在
8、半诚实模型下将文献7中的百万富翁协议进行推广,从“”和“”关系中将“等于”关系区分出来.然后将修改后的协议推广到安全多方排序问题上,并设计出改进算法来降低协议的复杂度.最后,本文基于模糊数学中模糊贴近度的概念和思想设计了另一收稿日期:2007204209;修回日期:2007210219基金项目:国家自然科学基金(No.60642008);西安电子科技大学综合业务网理论及关键技术国家重点实验室开放课题(No.ISN7-01)第4期2008年4月电 子 学 报ACTA ELECTRONICA SINICAVol.36No.4Apr.2008个安全多方排序协议.2 准备知识 定义1(安全多方排序问题
9、)有n个参与方,每一方都拥有一个秘密输入,他们希望在不泄漏自己秘密输入信息的前提下,得到其输入按一定的顺序在这n个秘密输入中所处的位置的问题.本文中,我们将对秘密输入按照从大到小的顺序排序.定义2(半诚实模型)9参与方将准确完成协议,但同时记录下所有中间结果,用以推导额外信息.定义3(基于语义安全的加同态加密体制)7设加密算法为E(),相应的解密算法为D(),其中加密密钥公开,解密密钥保密.明文空间MZ,E()满足下述两个性质:语义安全性:对任意两个消息m1,m2M,不存在任何多项式时间算法区分E(m1),E(m2);加法同态性:对任意消息m1,m2M,任意kZ,若m1+m2M,且km1M,则
10、D(E(m1)E(m2)=m1+m2且D(E(m1)k)=km1.3 半诚实模型下的两方排序协议311 协议描述假设Alice,Bob分别拥有秘密输入a,b(以下都只考虑秘密输入为整数的情况).他们希望不泄漏各自的秘密输入而比较出a,b的大小.设加、解密算法E(),D()满足基于语义安全的加同态性,本文首先将文献7中的一个常数复杂性的百万富翁协议作如下推广,从而完成比较:协议1 推广的两方排序协议Step1Alice用自己的公钥计算c=E(a)发送给Bob.Step2Bob随机选择整数u1,v1,w1,使|v1-w1|0,并用Alice的公钥计算X1=cu1E(v1),Y1=E(u1b+w1)
11、发送给Alice.Step3Alice解密D(X1)=u1a+v1,D(Y1)=u1b+w1,根据下述定理1:若D(X1)D(Y1),则ab,否则若D(X1)D(Y1),则ab.Step4Alice通知Bob再随机选择整数u2,v2,w2,使|v2-w2|0且(v2-w2)(v1-w1)D(Y2),则ab,否则若D(X2)D(Y1)Step5D(X2)D(Y2)则:ab;若Step3D(X1)D(Y1)Step5D(X2)D(Y2)则:aD(Y1)Step5D(X2)D(Y2)则:a=b;若Step3D(X1)D(Y2)则:a=b.Step7Alice把最终的比较结果告知Bob.312 协议分
12、析31211 正确性定理1 设D(X1)=u1a+v1,D(Y1)=u1b+w1,且满足|v1-w1|0;a,b为整数.那么若D(X1)D(Y1),则ab;若D(X1)D(Y1),则ab.证明 因(D(X1)-D(Y1)/u1=(a-b)+(v1-w1)/u1,且|(v1-w1)/u1|(v1-w1)/u1|,则D(X1)-D(Y1)的符号与a-b的一致;当|a-b|=0时,|a-b|=0 D(Y1)时,假设ab,根据上述结论知D(X1)D(Y1)矛盾,故ab.同理可证明若D(X1)D(Y1),D(X2)D(Y2),由上述定理1分别有ab或a=b;若a=b,则D(X1)-D(Y1),D(X2)
13、-D(Y2)的符号分别由v1-w1,v2-w2的符号决定,又(v2-w2)(v1-w1)0,所以(D(X1)-D(Y1)(D(X2)-D(Y2)b;因D(X1)D(Y1),由上述定理1,ab;D(X2)i.(以下,为书写简便,均用E()代替Eki(),D()代替Dki().)Step2pj(j=2,n,ji)随机选择整数u(1)ij,v(1)ij,w(1)ij,使v(1)ij-w(1)ij 0,pj计算:X(1)ij=cu(1)ijiE(v(1)ij),Y(1)ij=E(u(1)ijmj+w(1)ij)发送给pi.Step3pi解密:D(X(1)ij)=u(1)ijmi+v(1)ij,D(Y(
14、1)ij)=u(1)ijmj+w(1)ij,j=2,n,ji.若D(X(1)ij)D(Y(1)ij),则mimj;若D(X(1)ij)i)重新随机选择整数u(2)ij,v(2)ij,w(2)ij,使v(2)ij-w(2)ij0且(v(2)ij-w(2)ij)(v(1)ij-w(1)ij)i.若D(X(2)ij)D(Y(2)ij),则mimj;若D(X(2)ij)0/0,则compare(pk,pj),其中cmp(pLi,pj)0,jk,j1,n;若cmp(pLi,pk)0,则com2pare(pk,pj),其中cmp(pLi,pj)k,j1,n;若cmp(pLi,pk)=0,设与pLi的秘密输
15、入相等且角标最大(但其角标比k小)的成员为pLm,则pk在排列中所处的位置为pLm在排列中所处位置KLm加1,即Kk=KLm+1.若L1,Lk-1中与pk一起执行过协议1的参与方117第 4 期肖 倩:半诚实模型下安全多方排序问题的研究至少有两个,找出其中相隔最近的两个参与方Li,Lj,ij如果有多对,任取一对,完成以下步骤:pk根据mk与mLi,mLj的相对大小大致确定自己的位置:在Li之前,则compare(pk,pm),其中cmp(pLi,pm)0;在Li,Lj之间,则compare(pk,pm),其中cmp(pLj,pm)0;在Lj之后,则compare(pk,pm),其中cmp(pL
16、j,pm)0;以上m1,2,n.pk得到mk在排列中所处的位置,同时pk将比较结果告知对方;将已确定位置的参与方重新从前向后标号为L1,L2,Lk.Step3 当n方都执行完Step2后,新队列L1,L2,Ln就是n个参与方按秘密输入从大到小排成的队列.(2)算法1的复杂度分析 最差的情况:m1,m2,mn恰好从大到小或从小到大排列,这时的复杂度为O(n2),没有改进.几种特殊情况:二分的情况:假设在给n个参与方依次排序时,p1恰好位于已排序列的中间位置,将序列分成等长的两部分l1,l2;p2,p3分别恰好位于l1,l2的中间位置,分别将l1,l2分成等长的两部分:l3l6;为计算方便,设1+
17、2+22+2s-1=n,那么,n个参与方在总协议完成后分别执行协议1的次数是:1:p1:n-1次;2:p2,p3:(n-1-2)/2次;s:(n-1-2-22-23-2s-1)/2s-1次.所以改进算法一中总共执行协议1的次数为:n-120+n-1-2-22-2s-12s-1=(n+1)s-2s+1+2(1)又1+2+22+2s-1=n,即s=log2(n+1).代入式(1),得到(n+1)log2(n+1)-2n为执行协议1的总次数,算法复杂度为O(n+1)log2(n+1).同理,针对三分的情况,可估算出其执行协议1的次数为53(n+1)log3(2n+1)-4n,算法复杂度为O(n+1)
18、log3(2n+1).依此类推,p分的情况,可以求得算法复杂度为O(n+1)logp(p-1)n+1),是线性对数阶的.借助Matlab软件分析发现当n取定时,算法复杂度都随p的增大而减小.即p分的情况下,p越大,算法复杂度越小.41212 改进算法二(1)算法描述Step1p2与p1执行一次协议1,确定他与p1所处的相对位置:若m2m1,p2站p1后面;否则,p2站p1前面;将已排队列从前到后重新标号为L1,L2.Step2pk(k=3,n)依次执行以下步骤:pk与Lk-1执行一次协议1,确定他与Lk-1的相对位置:若mkmLk-1,pk站Lk-1后面;若mkmLk-1,pk与L1执行一次协
19、议1,根据结果选择pk的位置:如果mkmL1,pk站L1前面;如果mkmL1,则:若L1,Lk-1之间还有两个或以上参与方,将L2,Lk-2作为一个新的已排序列转Step2;若L1,Lk-1之间只有一个参与方L2,若mkmL2,将pk插入L2,Lk-1之间,若mkmL2,将pk插入L1,L2之间;若L1,Lk-1之间没有其他参与方,将pk插入L1,Lk-1之间;将已排队列从前到后重新编号L1,Lk.Step3 当n个参与方都执行完Step2后形成的新队列L1,Ln就是p1,pn按秘密输入从大到小顺序排列以后的队列.(2)算法2的复杂度分析分析以上算法,易知:pk在这个算法中最多执行k-1次协议
20、1,k=1,2,n,那么,在最坏的情况下总共执行n(n-1)/2次协议1,算法复杂度是O(n2),与未改进前相同.最好的情况:如果参与方的输入就是按照从大到小的次序排列的.那么在改进算法二中除p1外每一方只需主动执行一次协议1,而p1主动执行零次协议1.那么该协议总共执行了n-1次协议1,算法的复杂度降低到一阶O(n).一般情况下算法复杂度介于O(n)和O(n2)之间,一般比未改进之前均有改善.413 结合模糊贴近度的安全多方排序由于协议2中两两参与方之间需要执行一次协议1造成很高的算法复杂度,下面考虑结合模糊数学中模糊贴近度的定义来实现安全多方排序.41311 相关概念的介绍定义4(模糊贴近
21、度的公理化定义)10映射:F(U)F(U)0,1,(A,B)(A,B),若满足:(A,A)=1,(,U)=0;(A,B)=(B,A);若ABC,则(A,C)(A,B)(B,C),则称是F(U)上的贴近度函数,(A,B)称为A,B的贴近度.其中,F(U)表示论域U上的全体模糊集.在本文中,我们定义这样的贴近度函数:(A,B)=0;A=,B=U/A=U,B=1-cd(A,B);其他情况A=(a1,a2,al),B=(b1,b2,bl)217 电 子 学 报2008年其中,d(A,B)=li=1|ai-bi|2l-i,c值由其中一方随机选定.贴近度表征两个事物的相似程度,贴近度越大表示两个事物越相似
22、,否则表示它们差别越大.41312 结合模糊贴近度的安全多方排序(1)协议描述设加密和解密算法E(),D()满足基于语义安全的加同态性,结合模糊贴近度的安全多方排序协议的基本步骤如下:协议3 结合模糊贴近度的安全多方排序协议Step1p1与p2,pn各执行一次协议1,得到自己在有序排列中的位置,并将p1与pi的比较结果告知pi(i=2,n).Step2pi(i=2,n)首先根据自身秘密输入与p1秘密输入的大小初步确定自己的位置:mim1,pi站在p1前面;mim1,pi站在p1后面.Step3pi(i=2,n)与p1分别完成下列操作:p1,pi分别将自己拥有的秘密输入转化成二进制的形式:m1=
23、a11a12a1l,mi=ai1ai2ail.(l是p1,pn事先商定的足够大的数,若转化成的二进制形式长度小于l,则在其左边补充足够的0.)p1,pi按照如下步骤保密计算d(m1,mi),使两方得到的输出之和为d(m1,mi):pi将其秘密输入mi的全部奇数位发送给p1,p1计算:s1i=j|a1j-aij|2l-j,j=2k+1,0k(l-1)/2p1将其秘密输入m1的全部偶数位发送给pi,pi计算:s2i=j|a1j-aij|2l-j,j=2k,0k l/2Step4 完成Step3后,p1,pi分别拥有保密数据s1i,s2i,且s1i+s2i=d(m1,mi).p1随机选择一个足够大的
24、数R,R作为贴近度定义中的c将被应用在p1与所有pi贴近度的计算中,且它能使贴近度保持在0,1范围内.然后pi(i=2,n)与p1完成下列操作:pi选择一个公钥/私钥对,公钥公开、私钥保密.然后pi利用满足语义安全的加同态性质的加密算法加密s2i,得到Epi(s2i),将Epi(s2i)发送给p1;p1用pi的公钥加密s1i,得到Epi(s1i),然后p1计算Epi(s2i)R以及Epi(s1i)R,再把两个结果相乘得到Epi(Rs2i+Rs1i)发送给pi;pi用自己的私钥解密Epi(Rs2i+Rs1i)得到Rs2i+Rs1i,并计算(m1,mi)=1-(Rs1i+Rs2i).Step5p1
25、之前的参与方按照他们各自与p1贴近度的大小从小到大排列,形成队列L1;p1之后的参与方按照他们各自与p1贴近度的大小从大到小排列,形成队列L2(注意:在p2,pn按照贴近度比较大小时,它们各自的贴近度只在p2,pn之间公开,而不泄漏给p1,否则p1可以从中计算出其他参与方的秘密输入).L=L1,p1,L2就是p1,p2,pn按照秘密输入从大到小排成的队列.(2)协议分析.正确性可以验证本文中定义的贴近度满足贴近度的公理化定义:验证 第一二条性质容易验证,本文略;下面验证第三条性质:A=(a1,al),B=(b1,bl),C=(c1,cl),若ABC,则 i1,l,aibici,所以|ai-ci
26、|ai-bi|bi-ci|,为两者中取大,故(A,C)=1-cli=1|ai-ci|2l-i(1-cli=1|ai-bi|2l-i)(1-cli=1|bi-ci|2l-i)=(A,B)(B,C)为两者中取小.由于模糊贴近度表征了A,B之间的相似程度,因此任两个站在p1同一边的参与方pi,pj(不妨设他们站在p1前面),那么如果(p1,pi)pj;同理可以解释其他情况.因此,协议3是正确的.安全性p1,pi分别拥有s1i,s2i,求模糊贴近度的问题转化为p1,pi共同安全计算R(s1i+s2i)的问题:pi将Epi(s2i)发送给p1时,由于p1不知道pi的私钥,p1无法解密Epi(s2i)从而
27、得到s2i的信息;p1利用语义安全的加密算法的加同态性计算Epi(Rs2i+Rs1i),pi解密后得到Rs2i+Rs1i,由于pi不知道R,所以他无法从中得知s1i的信息,因此他们最终能够安全地完成模糊贴近度的计算.因此协议是安全的.效率分析首先该协议执行了n-1次协议1,复杂度为O(n).然后,p1执行了n-1次复杂度为O(1)的连加运算,pi(i=2,n)执行一次复杂度为O(1)的连加运算,故复杂度为O(n).最后,p1执行n-1次乘法运算.综上所述,协议3的算法复杂度为O(n).其算法复杂度始终是一阶的,故相对比较低.414 安全多方排序协议的比较我们可以通过下面的表1对上述几个安全多方
28、排317第 4 期肖 倩:半诚实模型下安全多方排序问题的研究序协议的效率和安全性作一比较:表1 各协议和算法的效率、安全性比较协议和算法算法效率安全性协议2O(n2)效率低每一方都不知道其他方秘密输入的具体值,只知道其他方的秘密输入与自己的大小关系;每一方都只知道自己在排列中的具体位置,而不知道其他方在排列中的位置和其他任何两方的秘密输入之间的大小关系;在四种算法中,其安全性最高.改进算法一O(n+1)logp(p-1)n+1)O(n2)效率较低每一方都不知道其他方秘密输入的具体值,只知道其他方的秘密输入与自己的大小关系;每一方虽不完全知道其他方在排列中的具体位置,但后参与排序的参与方能得到其
29、中一个已排好序的参与方的位置信息;其安全性较高.改进算法二O(n)O(n2)在一些特殊情况下能够获得较高的效率每一方都不知道其他方秘密输入的具体值,只知道其他方的秘密输入与自己的大小关系;但后参与排序的参与方能够得知已排好序的参与方之间的大小关系.其安全性在四种算法中比较低,但是已经满足协议要求的安全性.协议3O(n)效率始终较高每一方都不知道其他方秘密输入的具体值,只知道其他方的秘密输入与自己的大小关系;最终,每一方都能知道其他方在排列中的具体位置;在四种算法中,其安全性最低,但已满足协议要求的安全性.5 结束语 目前对于安全多方排序问题的研究还比较贫乏,没有很多有效的解决方案.本文给出了一
30、个安全多方排序协议,并通过两种改进算法提高了效率,然后本文基于模糊贴近度的定义给出了另一个安全多方排序协议,并对协议的正确性和安全性作了说明.正如文献7,9等中的大多数协议一样,协议被设计在半诚实模型下,但协议的复杂度是比较低的.参考文献:1 A Yao.Protocols for secure computationA.Proceeding of the23th IEEE Symposium on Foundations of Computer ScienceC.Los Alamitos,CA:IEEE Computer Society Press,1982.160-164.2 C Cach
31、in.Efficient private bidding and auctions with an oblivi2ous third partyA.Proceedings of the6th ACM Conference onComputer and Communications SecurityC.New York:ACMPress,1999.120-127.3 H Y Lin,W G T zeng.An efficient solution to the millionairesproblem based on homomorphic encryptionA.Proceedings oft
32、he4th International Conference on Applied Cryptography andNetworks SecurityC.volume3531of LNCS:2005.456-466.4秦静,张振峰,冯登国,李宝.无信息泄漏的比较协议J.软件学报,2004,15(3):421-427.Qing Jing,Zhang Zhen2feng,Feng Deng2guo,Li Bao.A proto2col of comparing information without leaking J.Journal ofSoftware,2004,15(3):421-427.(
33、in Chinese)5 Ronald Fagin,Moni Naor,Peter Winkler.Comparing informa2tion without leaking itJ.Communications of the ACM,1996,39(5):77-85.6李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案J.电子学报,2005,33(5):769-773.Li Shun2dong,Dai Yi2qi,You Qi2you.An efficient solution toyaos millionairesproblemJ.Acta Electronica Sinica,20
34、05,33(5):769-773.(in Chinese)7秦波,秦慧,周克复,王晓峰,王育民.常数复杂性的百万富翁协议J.西安理工大学学报,2005,21(2):149-152.Qin Bo,Qin Hui,Zhou Ke2fu,Wang Xiao2feng,Wang Yu2ming.Millionairesprotocol with constant complexityJ.Journal of Xian University of T echnology,2005,21(2):149-152.(in Chinese)8 Ioannidis I,Grama A.An efficient p
35、rotocol for Yaos million2airesproblemA.Proceedings of the36th Annual Hawaii In2ternational Conference on System SciencesC.2003.6pp.9罗文俊,李祥.多方安全矩阵乘积协议及应用J.计算机学报,2005,28(7):1230-1235.Luo Wen2jun,Li Xiang.The secure multi2party protocol of ma2trix product and its applicationJ.Chinese Journal of Comput2
36、ers,2005,28(7):1230-1235.(in Chinese)10李洪兴,汪培庄.模糊数学M.北京:国防工业出版社,1994.作者简介:肖 倩 女,1984年9月出生于湖南长沙,2007年毕业于北京邮电大学理学院数学与应用数学系,并进入北京邮电大学软件学院计算机科学与技术专业,现为硕士研究生.从事信息安全、安全多方计算方面的有关研究.E2mail:xiaoqianbupt 罗守山 男,1962年8月出生于北京市,1985年、1994年和2001年分别在北京师范大学、北京邮电大学和北京邮电大学获理学学士、理学硕士和工学博士学位,现为北京邮电大学教授.博士生导师,主要从事信息安全和网格安全等方面的研究工作.E2mail:buptlou 417 电 子 学 报2008年