多方安全计算经典问题整理.doc

如有侵权，请联系网站删除，仅供学习与交流多方安全计算经典问题整理【精品文档】第 8 页题 目 多方安全计算经典问题整理摘要数据挖掘可以帮助人们在纷繁多样的数据中找出隐晦的有用信息，并且已经在电信、银行、保险、证券、零售、生物数据分析等领域得到了广泛的应用。然而，就在数据挖掘工作不断深入的同时，数据隐私保护问题也日益引起人们的广泛关注，如何在保护数据隐私的前提下进行数据挖掘已经成为当前亟待解决的一个问题。本报告选取隐私保持数据挖掘中的多方安全计算领域进行相关的整理工作，罗列了多方安全计算领域中较为经典的姚式百万富翁问题、安全电子选举问题以及几何位置判定问题。一方面，在翻阅文献的基础上为这些问题筛选出前人给出的相对简洁易懂的解决方案；另一方面也对文中所展示的解决方案从时间复杂度、应用范围的局限性以及潜在安全隐患等角度进行了评价。另外，本报告也对各个问题中有待进一步研究解决的问题进行了简单的阐述，以起到抛砖引玉的效果。在报告的最后，也谈及了自己这门课程的上课感受。感谢学院开设的这门课程，感谢授课的各位老师，让我在较短的时间内得以大致了解当前数据库领域中所出现的一些前沿性的成果和问题，着实获益匪浅！希望这种类型的课可以继续办下去，越办越好！关键词：多方安全计算； 百万富翁； 电子选举； 几何位置判定目录1 引言随着社会信息化和电子商务与电子政务的不断发展，数据成为社会的重要资源，面对时刻在高速增长着的数据，越来越多的人开始思考如何将这些数据转换成有用的信息和知识。比如连锁超市经理希望从交易数据库中发掘客户的消费习惯，电信运营商希望从客户通话记录中建立恶意欠费用户通话模型，银行经理希望能基于信用卡持卡人历史记录建立优良客户特征模型，传统的数据库技术远远不能满足这种深层次的数据分析处理需求，于是数据挖掘（Data mining，DM）应运而生。所谓的数据挖掘就是“从数据中提取出隐含的过去未知的有价值的潜在信息”1，它是数据库知识发现（Knowledge-Discovery in Databases，KDD）中的一个步骤。然而，在数据挖掘技术应用不断深入的同时，数据挖掘技术对数据隐私的威胁也日益引起人们的关注。或担心其数据被误用，或顾虑某些隐藏于数据背后的敏感信息被“挖掘”出来，人们往往不愿意提供数据参与数据挖掘工作，这就使得数据挖掘失去了基础。在这样一个背景下，研究如何在保持数据隐私的前提下进行数据挖掘是一件非常有意义的工作。当前，隐私保持数据挖掘（Privacy Preserving Data Mining，PPDM）研究引起了国内外学者的广泛兴趣，已经开发了一系列的技术。隐私保持数据挖掘技术针对待处理数据分布的不同可以分为两类：集中式和分布式。集中式的主要有随机扰乱、随机响应、数据交换、规则隐藏的启发式方法、k-匿名和l-多样性方法等等，而分布式中最常用的是多方安全计算密码技术。本报告主要就多方安全计算技术，选取了该领域比较经典的几个问题做了一些整理工作。2 多方安全计算概述生活中，常常会有多方各自拥有自己的数据，希望协作进行数据挖掘，但每个参与方都不希望让其它方看到自己原始数据的情形。比如各商业银行希望进行合作进行信用卡欺诈分析，各电信运行商希望合作进行客户流失模型分析，它们的数据有相似的属性，但都不希望向合作方透露具体的数据，同时希望得到数据挖掘结果。这就是多方安全计算应用于数据挖掘的现实需求模型，将该现实需求模型抽象化，得到多方安全计算的基本任务如下：大于或等于2的参与方，在无可信第三方参与的情况下，执行协议，得到共同或分别拥有的结果，但参与方不希望向任意其它方泄漏自身的隐私数据。多方安全计算在密码学中更一般的描述是：n个参与方p1，p2，pn，每个参与方pi持有秘密的输入xi，希望计算一个共同函数：f(x1，x2，xn)，计算结束的时候，各方得到正确的输出f(x1，x2，xn)，同时自己的秘密输入xi没有泄露给其它的参与方。注意到，如果有可信第三方，那么多方安全计算任务就变得非常简单：各参与方把自己的输入数据传给可信第三方，由可信第三方将计算结果传给参与方即可。但现实中可信第三方很难找到，于是多方安全计算任务就变得很困难。多方安全计算研究由华人学者姚期智开创23，他通过研究两个百万富翁希望不向对方透露彼此财富的情况下比较谁更富有的问题，形象地说明了多方安全计算面临的挑战和问题解决思路，并经Oded Goldreich5、Shaft Goldwasser6等学者的众多原始创新工作，逐渐发展成为密码学的一个重要分支。接下来，本报告将会对多方安全计算领域中比较经典的百万富翁问题、电子选举问题以及保护私有信息的几何判定问题进行简单的整理介绍。3 百万富翁问题百万富翁问题首先由华裔计算机科学家、图灵奖获得者姚期智教授提出2。文献2中，姚教授提出了这样一个问题：两个百万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让对方知道自己财富的任何信息，这就是百万富翁问题。下面，整理了该问题的两个解决方案，首先给出姚期智教授在提出问题时给出的一个解决方案，然后选取了清华大学李顺东等人提出的一个高效解决方案，该方案针对姚式解决方案存在的算法复杂度太高，效率过低问题做出了改进。3.1 姚式百万富翁问题解决方案13.1.1 方案定义对该问题进行抽象化其实就是两个数的安全大小比较问题，以确定哪一个较大。Alice知道一个整数i；Bob知道一个整数j。Alice与Bob希望知道究竟是i j 还是i >j，但都不想让对方知道自己的数。为简单起见，假设i 与j 的范围为1，100。Bob有一个公开密钥EB与私有密钥DB。(1)Alice选择一个大随机数x，并用Bob的公开密钥加密。(3-1)(3)Bob计算下面的100个数：(3-2)其中，DB是Bob的私有解密密钥Bob选择一个大的素数p( p应该比x稍小一点，Bob不知道x，但Alice能容易地告诉他x的大小) 然后计算下面的100个数：(3-3)然后验证对于所有的uv，(3-4)并对所有的u验证：(3-5)如果不成立，Bob就选择另一个素数并重复验证。(4)Bob将以下数列发送给Alice：z1，z2，zj，zj+1+1，zj+2+1， ，z100+1，p(5)Alice验证这个数列的第i个数是否与x模p同余。如果同余，她得出的结论是ij；如果不同余，它得出的结论是i>j。(6)Alice把这个结论告诉Bob。3.1.2 方案评价该方案的设计巧妙的利用了数据i、j本身的特点，式（3-2）通过引用变量u穷举整数i的值域将整数i隐含至最终Bob返还给Alice中的数据序列中。如果ij，那么第i个数肯定在数列z1，z2，zj之中的某一个，该数列中的数据逆向使用式（3-2）自然得到x；如果i>j，那么第i个数肯定在数列zj+1+1，zj+2+1，z100+1之中的某一个，由于该数列中的数据都加了1，逆向使用公式（3-2）就得不到x了。因此，通过这种方案是可以在不知道对方数据大小的情况下得到比较结果的。但是，正是这种巧妙也为该方案设置了一定的局限性：首先该比较方案只适用于整数间甚至是正整数间的大小比较，因为对于实数域，变量u是不可能穷举实数变量i的值域的；其次该方案仅适用于较小的整数，如果变量i、j很大的话，通过接下来的时间复杂度分析，方案的效率是很低的，基本没有实际应用价值。 假设该方案需要比较的两个数的长度(十进制表示的位数)为n，数的范围就是10n，是输入规模的指数。 比如在上述例子中两个数的长度为2，则数的范围就是100，式(3-2)中要解密的次数、式(3-3)中模运算的次数、式(3-5)中要验证的次数都是10n，式(3-4)中要验证的次数为102n/2。因此计算复杂性为输入规模的指数函数。如果输入规模为50，那么计算复杂性为O(1050)，这样的计算复杂性，实际上是不可能实现的。因此这个方案对于比较两个较大的数是不实用的。3.2 基于不经意传输协议的高效改进方案83.2.1 不经意传输协议文献8给出的高效解决方案是基于文献6和文献7提出的不经意传输协议形成的，不经意传输协议是一个重要的密码学协议，这个协议能够完成以下任务：Alice有m个消息(或者数据)x1，x2，xm，通过执行不经意传输协议，Bob能够基于自己的选择得到且只能得到其中的一个消息xi(1im)，而对其他消息x1，x2，xi-1，xi+1，xm则一无所知。Alice对Bob选择了哪一个消息也一无所知。现将文献6和7提出的不经意传输协议做如下整理。设q为一素数，p=2q+1也是一个素数。Gq为一阶q群，g、h为Gq的两个生成元，Zq表示自然数模q的最小剩余集，(g，h，Gq)为双方共知，Alice有m个消息：M1，M2，Mm，Bob希望得到其中的一个，Alice不知道Bob得到了哪一个。协议如下：Step 1：Bob选择一个希望的(1m)与一个随机数rZq，计算y=grh mod p并将y发给Alice。Step 2：Alice计算下列m个二元组的序列C=(a1，b1)，(a2，b2)，(am，bm)其中：(3-6)并将序列C发给Bob。Step 3：根据c=(a，b)，Bob计算M=(b/(a)r)mod p。完成这个协议，Bob就可以得到他希望得到的M，而Alice对则一无所知。3.2.2 改进方案接下来给出文献8提出的基于该不经意传输协议的大富翁问题高效解决方案。假设要保密比较两个自然数a，b的大小，为简单起见假设1a，b<100，方案如下：Step 1：令X=1，2， ，99，R=(X)是X的一个随机置换。Bob计算下面的100个数，得到一个数组Y=Y1，Y2，Y100，其中：Step 2：利用不经意传输，Alice能够选择她愿意得到的唯一的数Ya=g(a，b)。不经意传输方案保证了Alice可以决定要得到的唯一的数，而Bob并不知道Alice选择了哪一个数。如果Ya<100，那么a=b；如果100<Ya<200，那么a>b，如果200<Ya<300，那么a<b。Step 3：Alice将结果告诉Bob。就待比较的两数都在100以内来说，原方案需要式（3-1）进行1次模指数运算、式（3-2）需要进行100次模指数运算、式（3-4）需要进行100*100/2次比较（如果式（3-3）不成立，前述公式还需从进行运算）、式（3-5）需要进行100次比较；相应地，改进方案只需进行100次加法运算和101次模指数运算，减少了大量的比较和验证，效率有一定提升。但是，改进方案依然只能用于两较小自然数间的安全比较，原因就在于它所依据的不经意传输协议中，变量i依然是对值域的一个穷举。除此之外，这里仅仅是讨论两方间的安全比较问题，多方间的安全大小比较应该怎样实现呢，事实上这方面前人也有了一定研究91011，由于篇幅限制，本报告不再一一展示。4 安全电子选举问题当某一电子选举方案同时满足选票保密性、无收据性、健壮性、公平性和普遍验证性等性质时，我们就称该方案是安全的。安全电子选举问题可以追溯至1981年，D.Chaum首先提出了电子投票思想12，至今基于传统密码领域虽然已经提出了几类电子选举方案，但是没有一个方案可以满足电子选举的所有需求，总有一些缺陷，要么是效率不高，不够安全：要么是不够灵活，通过筛选，下文整理了文献14给出的一种基于多方安全求和协议的解决方案，该方案在整个选举过程不需要可信第三方，任何投票人都可以计票，比一般的方案具有更强的安全性，同时，该方案也实现了选举的无收据性和普遍验证性。4.1 选举模型通常，一个完整的电子选举方案由选民注册阶段、机构发布选票阶段、选民投票阶段、机构收集选票阶段、校验选票阶段、统计选票阶段、对选举结果的验证等阶段组成，每一阶段由相应的协议实现其功能。本报告所展示的电子选举方案主要针对多选多的选举情形，对选举过程中的各个阶段都做了一些简化，以下是方案所依赖的选举模型的定义：（1）通信信道。通信信道采用多方计算标准的安全广播信道模型13。（2）参与方。设n个投票人（P1，P2，Pn）在投票前均已注册，并知道所有注册选民的合法身份标识各选民地位平等，选票权重相同投票结束后，每个选民都可以计票，不需要设置专门的可信第三方作为计票中心。（3）选票结构。假设最多有n个投票人（P1，P2，Pn）参与投票，共有m个候选人（C1，C2，Cn），每一张的选票由m列组成，每列由k位构成（），其中，前k-1位为0，最后1位ai值取决于投票人，若投票人对候选人Ci投赞成票，则ai=1，否则ai=0，因此选票总位数为mk，显然上述选票是一个多精度整数。4.2 多选多的电子选举方案144.2.1 方案定义假定选民是合法的投票人，已通过注册，取得合法的身份标识Pi，可以进入投票系统进行选举活动，方案分为本地表决、发送选票、统计选票3个阶段。（1）本地表决每个投票人Pi（i1，n）在电子选票上对Cj（j1，m）进行表决。aj（j1，m）取值为1表示赞成，取值为0则表示反对，由此得到一个二进制序列，并将该二进制数转换成十进制数。（2）发送选票每个投票人Pi（i1，n）均将自己的选票（十进制数）随机地拆分为n个更小的整数vij，使得，然后利用安全信道将vij发送给选民Pj（j1，n，ji）每个Pi在收到其余n-1个投票人的随机数vji（j1，n，ji）之后，计算和式，其中vii是Pi自己持有的随机数。3）统计选票每个投票人Pi（i1，n）将自己的求和结果vi广播给其余的投票人Pj（j1，n，ji）。每个投票人Pi在收到其余n-1个投票人的广播结果之后，即可计算所有的选票之和T。(4-1)最后每个Pi将十进制整数转换成二进制数，然后对每位进行截取，即可得到每一位候选人Cj（j1，m）的得票数。4.2.2 方案评价表面上看，以上通过安全多方求和方法进行投票和计票，除了最终的计票结果外，不泄露任何投票人选票的秘密，实现了保密投票。但是仔细分析可以发现，当候选人数m不是特别大的时候，投票人Pi对于候选人Cj是否投票就具有可破解性，因为候选人越少，投票人投票后所产生的二进制序列转化成十进制数得到的潜在组合就少，例如当候选人数只有三个人的时候，投票人的投票数转化成十进制只有8种可能：73，72，65，64，9，8，0。在这八种组合的基础上辅助以拆分项大小的限制等信息，对投票人的投票结构进行破解是完全有可能的。因此，该方案的选票保密性还有待进一步完善，不过随着候选人人数的增加，该方案的优越性也会进一步得到体现。目前在电子选举问题中除了上文所展示的多选多问题外，还有许多值得研究的问题，比如电子评审和陪审团表决时的保护隐私的电子评审问题、上市公司股东大会中的含权选举问题以及工程项目投标中的平均值中标问题等。这些问题与生活实际联系非常紧密，解决的难度也很大，还有待进一步研究。5 保护私有信息的几何判定问题随着科学技术的发展，人类研究开发太空的能力在不断增强，国际上不同的科研机构之间都希望开展合作来加快自己的研究进程。然而由于涉及到国家的安全与利益，这种合作是极其有限的，任何一个机构都不会轻易向其他合作方公开自己的技术。例如两个不同的国家各自都研制出自己的太空碎片分布图，为了确保自己的飞行器在太空飞行过程中不会与太空碎片发生碰撞，他们都希望能同时参考对方数据来提高飞行的可靠性，然而为了各自国家的利益，两方都不会向对方泄露自己的数据信息。上述问题就是在安全两方计算环境下，判定空间几何对象间的相对位置关系问题。当前，针对这一问题的研究成果还是较为丰盛的，前人已经给出了点到直线、平面的距离以及点、线、面等几何对象的相对位置判定协议、线段相交判定协议、圆、椭圆的关系判定方法、保护隐私的圆与圆、圆与直线的位置判定协议等多种几何判定协议。由于本报告的篇幅限制，不可能对这些协议一一进行整理，但是这些协议的基础大都是安全点积协议，因此下文中重点对安全点积协议进行整理介绍。5.1 安全点积定义安全点积协议更早是在Du Wenliang等学者的一系列论文中实现的15，他们提出了安全点积定义：Alice有向量X=（X1，X2，Xn)，Bob有向量Y=(Y1，Y2，Yn)和标量数值v，计算结束，Alice得到X·Y+v，而Bob不知道这个值。Bob不直接得到这个值，但Bob可以将该值减去v，进而间接使用X、Y两个向量的点积，可见满足这样定义的安全点积协议有着较高的安全性，为了简便起见，这里本文讨论当v=0的情况，即：Alice有向量X=（X1，X2，Xn)，Bob有向量Y=(Y1，Y2，Yn)，他们协作计算得到点积，但互相并不知道对方的数据安全点积协议。5.2 安全点积协议下面本文展示了文献16和文献17中设计和应用的一个安全点积协议。这个协议体现了多方安全计算应用的一个原则：泄露一些不重要的信息，以获取更好的效率。输入：Alice有向量X=（X1，X2，Xn)，Bob有向量Y=(Y1，Y2，Yv)。输出：X和Y的点积。Step 1：Alice和Bob协商产生一个随机n*（n/2）矩阵C。Step 2：Alice随机产生向量n/2×1向量R=（r1,r2,rn/2），Alice产生n×1向量X，X=C×R，Alice产生X=X+X，Alice将X发送至Bob。 Step 3：Bob令， Bob产生n×1向量Y=CT×Y， Bob将S和Y向Alice发送。 Step 4：Alice计算， Alice计算s=s-s， Alice将结果告诉Bob。通过文献阅读，当前就隐私保持几何位置判定问题前人已经针对具体的位置关系判定分别给出了系列安全判定协议，这些安全判定协议的基础大都是上文所展示的安全点积协议，这里本报告也仅仅是起到了一个抛砖引玉的作用。6 小结在数据挖掘得到广泛应用的同时，隐私数据保持数据挖掘技术也日益受到人们的普遍关注，多方安全计算是隐私数据保持数据挖掘领域的一个重要研究方向，有着深远的理论意义和广阔的实际应用前景。多方安全计算的研究内容是丰富多样的，本报告目前仅仅是对该方向中的若干经典问题进行了相关的整理工作，由于能力所限，相应问题给出的解决方案也只是删繁就简，选取了前人简洁易懂的解决方案进行了展示。事实上，每一个问题截至目前为止仍有很多问题没有解决，比如目前提出的系列解决方案大都是基于半诚实模型（半诚实参与方使用正确的输入，并遵守协议规则，但有可能根据协议执行过程中收到的信息破解隐私数据）基础上的，而现实生活中很多安全性的攻击往往是恶意，这些恶意参与者除了会采取半诚实参与方的攻击行为外，还可能不遵循协议的规则，包括伪造输入数据、和其它参与方串谋等。因此，如何构建基于恶意模型的安全多方数据挖掘协议还需要人们进行更多地研究工作。再比如安全电子选举问题，若何解决身份认证和匿名投票问题也有必要进一步深入研究。总之，多方安全计算的研究和应用都方兴未艾，仍有着很多有意义的工作值得我们去做，希望不远的将来本报告所罗列的一些问题可以得到圆满的解决。参考文献1 W. Frawley and G. Piatetsky-Shapiro and C. Matheus (Fall 1992). "Knowledge Discovery in Databases: An Overview". AI Magazine: pp. 213-228. ISSN 0738-4602.2 Yao A CProtocols for secure computationAIn：Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer ScienceC1986:l62-l673 Yao A CHow to generate and exchange secretsAIn：Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer ScienceC1982:l60-l644 Goldreich O,Micali S,Wigderson A.How to play any mental game-a completeness theorem for protocols with honest majorityIn：Proceedings of the 19th ACM symposium 0n the Theory of ComputingC.1987:218-2295 Goldwasser S，Levin LAFair computation of general functions in presence of immoral majorityAIn：Advances in Cryptology-CRYPTO90，Proceedings of the10th Annual Intematioal Cryptology Conference，LNCS 537C1990:77-936 M Naor,B Pinkas.Efficient oblivious transfer protocolsA. Proc 12th Ann Symp Discrete AlgorithmsC. NewYork:ACMPress,2001. 448- 457.7 Wen Guey Tzeng. Efficient 12out2of2noblivious transfer schemes with universally usable parametersJ. IEEE TRANSACTIONS ON COMPUTERS,2004,53(2) :232- 240.8 李顺东，戴一奇，游启友姚氏百万富翁问题的高效解决方案J电子学报，2005，(5)：769-7729 肖倩，罗守山，陈萍，吴波半诚实模型下安全多方排序问题的研究J电子学报，2008，36(4)：70971410 秦静，张振峰，冯登国，李宝无信息泄漏的比较协议J软件学报，2004，15(3)：421-42711 刘文，王永宾. 安全多方信息比较相等协议及其应用.电子学报，2012，5：871-875.12 D.Chaum. Untraceable Electronic Mail Return Addresses and Digital Pseudonyms. Communications of the ACM, 1981, 24(2): 848813 O Goldreich. Secure multi-party computation(working draft)OL. http:/www. wisdom.weizmann.ac.il/home/oded/publichtml/foc.html,1998.14 仲红，黄刘生，罗永龙基于安全多方求和的多候选人电子选举方案J计算机研究与发展J2006，(8)：1405-141015 Du Wenliang,Atlallah M J.Secure Multi-party Computational GeometryA.In:Preceedings of 7th International Workshop on Algorithms and Data Structures,LNCS2125C.2001:165-179.16 Vaidya J，C1fton CPrivacy preserving association rule mining in venically panitioned dataIn：Proceedings of the 8th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining2002：639-64417 Clifton C，Kantarcioglu M，VaidyaJ，et a1T00ls for privacy preserving distributed data miningJACM SlGKDD Exploration2003，4(2)：28-34