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

1、精品文档题目 多方安全计算经典问题整理摘要数据挖掘可以帮助人们在纷繁多样的数据中我由隐晦的有用 信息，并且已经在电信、银行、保险、证券、零售、生物数据分 析等领域得到了广泛的应用。然而，就在数据挖掘工作不断深入 的同时，数据隐私保护问题也日益引起人们的广泛关注，如何在 保护数据隐私的前提下进行数据挖掘已经成为当前亟待解决的一 个问题。本报告选取隐私保持数据挖掘中的多方安全计算领域进行相 关的整理工作，罗列了多方安全计算领域中较为经典的姚式百万 富翁问题、安全电子选举问题以及几何位置判定问题。一方面， 在翻阅文献的基础上为这些问题筛选由前人给由的相对简洁易懂 的解决方案；另一方面也对文中所展示的

2、解决方案从时间复杂度、 应用范围的局限性以及潜在安全隐患等角度进行了评价。另外， 本报告也对各个问题中有待进一步研究解决的问题进行了简单的 阐述，以起到抛砖引玉的效果。在报告的最后，也谈及了自己这门课程的上课感受。感谢学 院开设的这门课程，感谢授课的各位老师，让我在较短的时间内 得以大致了解当前数据库领域中所由现的一些前沿性的成果和问 题，着实获益匪浅！希望这种类型的课可以继续办下去，越办越 好！精品文档几何位置判关键词：多方安全计算； 百万富翁； 电子选举;定精品文档目录 TOC o 1-5 h z 1引言 12多方安全计算概述 23百万富翁问题 3姚式百万富翁问题解决方案1 4方案定义 4

3、方案评价 5基于不经意传输协议的高效改进方案 网6不经意传输协议 6改进方案 74安全电子选举问题 8选举模型 9多选多的电子选举方案14 10方案定义 10方案评价 115保护私有信息的几何判定问题 12安全点积定义 12安全点积协议 136小结 147课程感受 错误！未定义书签。参考文献 15精品文档精品文档1引言随着社会信息化和电子商务与电子政务的不断发展，数据成 为社会的重要资源，面对时刻在高速增长着的数据，越来越多的 人开始思考如何将这些数据转换成有用的信息和知识。比如连锁 超市经理希望从交易数据库中发掘客户的消费习惯，电信运营商 希望从客户通话记录中建立恶意欠费用户通话模型，银行经

4、理希 望能基于信用卡持卡人历史记录建立优良客户特征模型，传统的 数据库技术远远不能满足这种深层次的数据分析处理需求，于是 数据挖掘（Data mining , DM应运而生。所谓的数据挖掘就是 “从 数据中提取由隐含的过去未知的有价值的潜在信息”1,它是数据库知识发现（Knowledge-Discovery in Databases , KDD 中的一 个步骤。然而，在数据挖掘技术应用不断深入的同时，数据挖掘技术对数据隐私的威胁也日益引起人们的关注。或担心其数据被误用，或顾虑某些隐藏于数据背后的敏感信息被“挖掘”由来，人们往 往不愿意提供数据参与数据挖掘工作，这就使得数据挖掘失去了 基础。在这

5、样一个背景下，研究如何在保持数据隐私的前提下进 行数据挖掘是一件非常有意义的工作。当前，隐私保持数据挖掘（Privacy Preserving Data Mining , PPDM 研究引起了国内外 学者的广泛兴趣，已经开发了一系列的技术。隐私保持数据挖掘 技术针对待处理数据分布的不同可以分为两类：集中式和分布式。精品文档集中式的主要有随机扰乱、随机响应、数据交换、规则隐藏的启 发式方法、k-匿名和1-多样性方法等等，而分布式中最常用的是 多方安全计算密码技术。本报告主要就多方安全计算技术，选取 了该领域比较经典的几个问题做了一些整理工作。2多方安全计算概述生活中，常常会有多方各自拥有自己的数

6、据，希望协作进行 数据挖掘，但每个参与方都不希望让其它方看到自己原始数据的 情形。比如各商业银行希望进行合作进行信用卡欺诈分析，各电 信运行商希望合作进行客户流失模型分析，它们的数据有相似的 属性，但都不希望向合作方透露具体的数据，同时希望得到数据 挖掘结果。这就是多方安全计算应用于数据挖掘的现实需求模型， 将该现实需求模型抽象化，得到多方安全计算的基本任务如下： 大于或等于2的参与方，在无可信第三方参与的情况下，执行协 议，得到共同或分别拥有的结果，但参与方不希望向任意其它方 泄漏自身的隐私数据。 多方安全计算在密码学中更一般的描述是： n个参与方pi, p2,，出，每个参与方p持有秘密的输

7、入 Xi,希 望计算一个共同函数：f(xi, X2,，Xn),计算结束的时候，各方 得到正确的输由f(x 1, X2,，Xn),同时自己的秘密输入 Xi没有 泄露给其它的参与方。注意到，如果有可信第三方，那么多方安全计算任务就变得 非常简单：各参与方把自己的输入数据传给可信第三方，由可信精品文档第三方将计算结果传给参与方即可。但现实中可信第三方很难找 到，于是多方安全计算任务就变得很困难。多方安全计算研究由华人学者姚期智开创3,他通过研究两个百万富翁希望不向对方透露彼此财富的情况下比较谁更富有的 问题，形象地说明了多方安全计算面临的挑战和问题解决思路， 并经Oded Goldreich、Sha

8、ft Goldwasser等学者的众多原始仓ij 新工作，逐渐发展成为密码学的一个重要分支。接下来，本报告将会对多方安全计算领域中比较经典的百万 富翁问题、电子选举问题以及保护私有信息的几何判定问题进行 简单的整理介绍。3百万富翁问题百万富翁问题首先由华裔计算机科学家、图灵奖获得者姚期 智教授提曲2 o文献2中，姚教授提生了这样一个问题：两个百 万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让 对方知道自己财富的任何信息，这就是百万富翁问题。下面，整 理了该问题的两个解决方案，首先给由姚期智教授在提由问题时 给生的一个解决方案，然后选取了清华大学李顺东等人提由的一 个高效解决方案

9、，该方案针对姚式解决方案存在的算法复杂度太 高，效率过低问题做生了改进。精品文档姚式百万富翁问题解决方案1方案定义对该问题进行抽象化其实就是两个数的安全大小比较问题， 以确定哪一个较大。Alice知道一个整数i; Bob知道一个整数j。Alice与Bob希望知道究竟是i j，但都不想让对方 知道自己的数。为简单起见，假设i与j的范围为1 , 100 o Bob 有一个公开密钥 6与私有密钥DBo(1)Alice 选择一个大随机数 x,并用Bob的公开密钥加密。 TOC o 1-5 h z c = Eb(x)(3-1)Bob计算下面的100个数：yu = DB c - i u , u 1,100

10、(3-2)其中，。是Bob的私有解密密钥 Bob选择一个大的素数 p( p 应该比x稍小一点，Bob不知道x,但Alice能容易地告诉他x的 大小)然后计算下面的100个数：Zu = ( yumod p ), u w 1,100(3-3)然后验证对于所有的u#v,zu I 22(3-4)并对所有的u验证：0 Zu 二 p - 1(3-5)如果不成立，Bob就选择另一个素数并重复验证。(4)Bob将以下数列发送给 Alice :Zi, Z2,Zj , Zj+1+1, Zj+2 + 1, ,Z100+1, p精品文档(5)Alice 验证这个数列的第i个数是否与x模p同余。如果 同余，她得由的结论

11、是i wj ；如果不同余，它得由的结论是ij 。(6)Alice 把这个结论告诉 Bob。方案评价该方案的设计巧妙的利用了数据i、j本身的特点，式(3-2)通过引用变量u穷举整数i的值域将整数i隐含至最终Bob返还 给Alice中的数据序列中。如果i wj ,那么第i个数肯定在数列 zi, Z2,，Zj之中的某一个，该数列中的数据逆向使用式(3-2)自然得到x；如果ij，那么第i个数肯定在数列乙+1+1,乙+2+1, Z100+1之中的某一个，由于该数列中的数据都加了1,逆向使用公式(3-2)就得不到x 了。因此，通过这种方案是可以在不知道对 方数据大小的情况下得到比较结果的。但是，正是这种巧

12、妙也为该方案设置了一定的局限性：首先 该比较方案只适用于整数间甚至是正整数间的大小比较，因为对 于实数域，变量 u是不可能穷举实数变量i的值域的；其次该方案仅适用于较小的整数，如果变量i、j很大的话，通过接下来的时间复杂度分析，方案的效率是很低的，基本没有实际应用价值。假设该方案需要比较的两个数的长度(十进制表示的位数)为n,数的范围就是10n,是输入规模的指数。比如在上述例子中两个数的长度为2,则数的范围就是100,式(3-2)中要解密的次数、 式(3-3)中模运算的次数、式 (3-5)中要验证的次数都是10n，式(3-4)中要验证的次数为102n/2。因此计算复杂性为输入规模的指精品文档数

13、函数。如果输入规模为50,那么计算复杂性为 0（10）,这样的计算复杂性，实际上是不可能实现的。因此这个方案对于比较两 个较大的数是不实用的。基于不经意传输协议的高效改进方案网不经意传输协议文献8给由的高效解决方案是基于文献6和文献7提由的不经意传输协议形成的，不经意传输协议是一个重要的密码学 协议，这个协议能够完成以下任务：Alice 有m个消息（或者数据） xi, X2,，xd ,通过执行不经意传输协议，Bob能够基于自己的选择得到且只能得到其中的一个消息Xi（1i n）,而对其他消息xi, X2,，Xi-i, Xi+i,，Xm则一无所知。Alice 对 Bob 选 择了哪一个消息也一无所

14、知。现将文献6和7提由的不经意传输协议做如下整理。设q为一素数，p=2q+1也是一个素数。G为一阶q群，g、h 为G的两个生成元，Zq表示自然数模q的最小剩余集，（g, h, G。 为双方共知，Alice有m个消息：M, M,，M, Bob希望得到其 中的一个，Alice不知道Bob得到了哪一个。协议如下：Step 1: Bob选择一个希望的 a （K a ba), Bob计算 M =(bJ(a )r)mod p。完成这个协议，Bob就可以得到他希望得到的而Alice对a则一无所知。改进方案接下来给由文献8提由的基于该不经意传输协议的大富翁 问题高效解决方案。假设要保密比较两个自然数a, b的

15、大小，为简单起见假设1a, b100,方案如下：Step 1 :令 X=1, 2, ，99, R=% (X)是 X 的一个随机置 换。Bob计算下面的100个数，得到一个数组 Y=Y, Y2,，Yoo, 其中：0 + R,如果 i b = 0Y = g(i , b) = ；100 + R ,如果i - b A 0200 + R ,如果 i b 0 JStep 2:利用不经意传输，Alice能够选择她愿意得到的唯一 的数Y=g(a, b)o不经意传输方案保证了Alice可以决定要得到的唯一的数，而Bob并不知道Alice选择了哪一个数。如果Y100, 那么 a=b;如果 100Yb,如果 200

16、Y300,那么 ab。Step 3 : Alice 将结果告诉 Bob。就待比较的两数都在 100以内来说，原方案需要式(3-1 )进 行1次模指数运算、式(3-2)需要进行100次模指数运算、式(3-4)精品文档需要进行100*100/2次比较（如果式（3-3）不成立，前述公式还 需从进行运算）、式（3-5）需要进行100次比较；相应地，改进 方案只需进行100次加法运算和101次模指数运算，减少了大量 的比较和验证，效率有一定提升。但是，改进方案依然只能用于两较小自然数间的安全比较， 原因就在于它所依据的不经意传输协议中，变量 i依然是对口值 域的一个穷举。除此之外，这里仅仅是讨论两方间的

17、安全比较问 题，多方间的安全大小比较应该怎样实现呢，事实上这方面前人 也有了一定研究91011,由于篇幅限制，本报告不再一一展示。4安全电子选举问题当某一电子选举方案同时满足选票保密性、无收据性、健壮 性、公平性和普遍验证性等性质时，我们就称该方案是安全的。 安全电子选举问题可以追溯至1981年，D.Chaum首先提由了电子投票思想12,至今基于传统密码领域虽然已经提由了几类电子选 举方案，但是没有一个方案可以满足电子选举的所有需求，总有 一些缺陷，要么是效率不高，不够安全：要么是不够灵活，通过 筛选，下文整理了文献14给由的一种基于多方安全求和协议的 解决方案，该方案在整个选举过程不需要可信

18、第三方，任何投票 人都可以计票，比一般的方案具有更强的安全性，同时，该方案 也实现了选举的无收据性和普遍验证性。精品文档4.1选举模型通常，一个完整的电子选举方案由选民注册阶段、机构发布 选票阶段、选民投票阶段、机构收集选票阶段、校验选票阶段、 统计选票阶段、对选举结果的验证等阶段组成，每一阶段由相应 的协议实现其功能。本报告所展示的电子选举方案主要针对多选多的选举情形， 对选举过程中的各个阶段都做了一些简化，以下是方案所依赖的 选举模型的定义：(1)通信信道。通信信道采用多方计算标准的安全广播信道 模型13 O(2)参与方。设n个投票人(Pi,的，Pn)在投票前均已 注册，并知道所有注册选民

19、的合法身份标识各选民地位平等，选 票权重相同投票结束后，每个选民都可以计票，不需要设置专门 的可信第三方作为计票中心。(3)选票结构。假设最多有 n个投票人(R, ，Pn)参 与投票，共有 m个候选人(G, G,，G),每一张的选票由 m 列组成，每列由k位构成(k = log2 n +1),其中，前k-1位为0, 最后1位a值取决于投票人，若投票人对候选人G投赞成票，则a=1,否则a=0,因此选票总位数为 mk显然上述选票是一个多 精度整数。精品文档4.2多选多的电子选举方案144.2.1方案定义假定选民是合法的投票人，已通过注册，取得合法的身份标 识P,可以进入投票系统进行选举活动，方案分

20、为本地表决、发 送选票、统计选票 3个阶段。(1)本地表决每个投票人P (i W1 ,n)在电子选票上对 C (jW1, m)进行表决。a (j W1 ,，m)取值为1表示赞成，取值为 0则表示反对，由此得到一个二进制序列，并将该二进制数转换成 十进制数。(2)发送选票每个投票人P (i W1 ,n)均将自己的选票(十进制数) n随机地拆分为n个更小的整数Vij ,使得Vi = Vji ,然后利用安全 j 二信道将Vij发送给选民P (j W1 ,，n , j #i )每个P在收到 其余n-1个投票人的随机数 Vji (j W 1 ,，n , j i )之后，计 n算和式v = Vj ,其中V

21、ii是P自己持有的随机数。 ijlj =13)统计选票每个投票人P (i W1 ,，n)将自己的求和结果 v广播 给其余的投票人 P (j W1 ,，n , j #i )。每个投票人 P在收 到其余n-1个投票人的广播结果之后，即可计算所有的选票之和精品文档 TOC o 1-5 h z nn nn nnnT =，Vi -Vj 小 Vj = - %(4-1)i 1ijjjJiJj 1i 1最后每个P将十进制整数转换成二进制数，然后对每位进行 截取，即可得到每一位候选人C (j W1 ,，m)的得票数。4.2.2方案评价表面上看，以上通过安全多方求和方法进行投票和计票，除 了最终的计票结果外，不泄

22、露任何投票人选票的秘密，实现了保 密投票。但是仔细分析可以发现，当候选人数m不是特别大的时候，投票人P对于候选人C是否投票就具有可破解性，因为候选 人越少，投票人投票后所产生的二进制序列转化成十进制数得到 的潜在组合就少，例如当候选人数只有三个人的时候，投票人的 投票数转化成十进制只有 8种可能：73, 72, 65, 64, 9, 8, 0c 在这八种组合的基础上辅助以拆分项大小的限制等信息，对投票 人的投票结构进行破解是完全有可能的。因此，该方案的选票保 密性还有待进一步完善，不过随着候选人人数的增加，该方案的 优越性也会进一步得到体现。目前在电子选举问题中除了上文所展示的多选多问题外，还

23、 有许多值得研究的问题，比如电子评审和陪审团表决时的保护隐 私的电子评审问题、上市公司股东大会中的含权选举问题以及工 程项目投标中的平均值中标问题等。这些问题与生活实际联系非 常紧密，解决的难度也很大，还有待进一步研究。精品文档5保护私有信息的几何判定问题随着科学技术的发展， 人类研究开发太空的能力在不断增强， 国际上不同的科研机构之间都希望开展合作来加快自己的研究进 程。然而由于涉及到国家的安全与利益，这种合作是极其有限的， 任何一个机构都不会轻易向其他合作方公开自己的技术。例如两 个不同的国家各自都研制由自己的太空碎片分布图，为了确保自 己的飞行器在太空飞行过程中不会与太空碎片发生碰撞，他

24、们都 希望能同时参考对方数据来提高飞行的可靠性，然而为了各自国 家的利益，两方都不会向对方泄露自己的数据信息。上述问题就是在安全两方计算环境下，判定空间几何对象问 的相对位置关系问题。当前，针对这一问题的研究成果还是较为 丰盛的，前人已经给由了点到直线、平面的距离以及点、线、面 等几何对象的相对位置判定协议、线段相交判定协议、圆、椭圆 的关系判定方法、保护隐私的圆与圆、圆与直线的位置判定协议 等多种几何判定协议。由于本报告的篇幅限制，不可能对这些协 议一一进行整理，但是这些协议的基础大都是安全点积协议，因 此下文中重点对安全点积协议进行整理介绍。5.1安全点积定义安全点积协议更早是在 Du W

25、enliang等学者的一系列论文中 实现的15,他们提由了安全点积定义：Alice有向量X=（X, X, 淘，Bob有向量Y=（Y, Y,，）和标量数值 v,计算结束，Alice精品文档得到xY+v,而Bob不知道这个值。Bob不直接得到这个值，但 Bob可以将该值减去 v,进而间接使用 X、Y两个向量的点积，可 见满足这样定义的安全点积协议有着较高的安全性，为了简便起 见，这里本文讨论当 v=0的情况，即：Alice 有向量 X= (X, X ，乂)，Bob有向量 Y=(Y, Y, nY),他们协作计算得到点积XY = Xi M yi ,但互相并不知道对i 1方的数据安全点积协议。5.2安全

26、点积协议下面本文展示了文献16和文献17中设计和应用的一个安 全点积协议。这个协议体现了多方安全计算应用的一个原则：泄 露一些不重要的信息，以获取更好的效率。输入：Alice 有向量X= (X, X,，X), Bob有向量 Y=(Y,Y,，Yv)o输由：X和Y的点积。Step 1 : Alice 和Bob协商产生一个随机 n* (n/2)矩阵 CStep 2： Alice 随机产生向量 n/2 x 1 向量 R= (r 1,r 2,r n/2),Alice 产生 nX1 向量 X , X =CX R,Alice 产生义,=X+X , Alice 将X发送至 Bobo nStep 3 : Bob

27、 令 s =x *y = z x x yi ,11Bob产生nx 1向量Y =CTx Y,精品文档Bob 将S和丫,向Alice 发送。n/2Step 4 : Alice 计算 s = 丫 r = y * x ri ,i J iAlice计算 s=s -s,Alice将结果告诉Bob。通过文献阅读，当前就隐私保持几何位置判定问题前人已经针 对具体的位置关系判定分别给由了系列安全判定协议，这些安全 判定协议的基础大都是上文所展示的安全点积协议，这里本报告 也仅仅是起到了 一个抛砖引玉的作用。6小结在数据挖掘得到广泛应用的同时，隐私数据保持数据挖掘技 术也日益受到人们的普遍关注，多方安全计算是隐私

28、数据保持数 据挖掘领域的一个重要研究方向，有着深远的理论意义和广阔的 实际应用前景。多方安全计算的研究内容是丰富多样的，本报告目前仅仅是 对该方向中的若干经典问题进行了相关的整理工作，由于能力所 限，相应问题给由的解决方案也只是删繁就简，选取了前人简洁 易懂的解决方案进行了展示。事实上，每一个问题截至目前为止 仍有很多问题没有解决，比如目前提由的系列解决方案大都是基 于半诚实模型（半诚实参与方使用正确的输入，并遵守协议规则， 但有可能根据协议执行过程中收到的信息破解隐私数据）基础上 的，而现实生活中很多安全性的攻击往往是恶意，这些恶意参与精品文档者除了会采取半诚实参与方的攻击行为外，还可能不遵

29、循协议的 规则，包括伪造输入数据、和其它参与方串谋等。因此，如何构 建基于恶意模型的安全多方数据挖掘协议还需要人们进行更多地 研究工作。再比如安全电子选举问题，若何解决身份认证和匿名 投票问题也有必要进一步深入研究。总之，多方安全计算的研究和应用都方兴未艾，仍有着很多 有意义的工作值得我们去做，希望不远的将来本报告所罗列的一 些问题可以得到圆满的解决。参考文献W. Frawley and G. Piatetsky-Shapiro and C. Matheus (Fall 1992). Knowledge Discovery in Databases: An Overview. AI Magaz

30、ine: pp. 213-228. ISSN 0738-4602.Yao A C . Protocols for secure computationA. In :Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer ScienceC . 1986:l62-l67Yao A C. How to generate and exchange secretsA . In : Proceedingsof the 23rd Annual IEEE Symposium onFoundations of Comput

31、er ScienceC . 1982:l60-l64GoldreichO,Micali S,Wigderson A.How to play anymental game-a completeness theorem for protocols withhonest majority . In : Proceedings of the 19th ACMsymposium精品文档0n the Theory of ComputingC.1987:218-229Goldwasser S , Levin LA . Fair computation of general functions in pres

32、ence of immoral majorityA . In : Advances in Cryptology-CRYPTO 90, Proceedings of the10th Annual Intematioal Cryptology Conference , LNCS 537C . 1990:77-93 .M Naor,B Pinkas.Efficient oblivious transfer protocolsA. Proc 12 th Ann Symp Discrete AlgorithmsC. NewYork:ACMPress,2001.448- 457.Wen Guey Tzeng. Efficient 12out20f2noblivious transfer schemes with universally usable parametersJ. IEEE TRANSACTIONS ON COMPUTERS,2004,53(2)