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

题 目多方安全计算经典问题整理摘要数据挖掘可以帮助人们在纷繁多样的数据中找出隐晦的有用 信息，并且已经在电信、银行、保险、证券、零售、生物数据分 析等领域得到了广泛的应用。然而，就在数据挖掘工作不断深入 的同时，数据隐私保护问题也日益引起人们的广泛关注，如何在 保护数据隐私的前提下进展数据挖掘已经成为当前亟待解决的一 个问题。本报告选取隐私保持数据挖掘中的多方安全计算领域进展相关的整理工作，排列了多方安全计算领域中较为经典的姚式百万富翁问题、安全电子选举问题以及几何位置判定问题。一方面， 在翻阅文献的根底上为这些问题筛选出前人给出的相对简洁易懂的解决方案；另一方面也对文中所展现的解决方案从时间简单度、 应用范围的局限性以及潜在安全隐患等角度进展了评价。另外， 本报告也对各个问题中有待进一步争论解决的问题进展了简洁的阐述，以起到抛砖引玉的效果。在报告的最终，也谈及了自己这门课程的上课感受。感谢学 院开设的这门课程，感谢授课的各位教师，让我在较短的时间内 得以大致了解当前数据库领域中所消灭的一些前沿性的成果和问 题，着实获益匪浅！期望这种类型的课可以连续办下去，越办越 好！.关键词：多方安全计算； 百万富翁； 电子选举； 几何位置判定名目1 引言12 多方安全计算概述23 百万富翁问题33.1 姚式百万富翁问题解决方案143.1.1 方案定义43.1.2 方案评价53.2 基于不经意传输协议的高效改进方案863.2.1 不经意传输协议63.2.2 改进方案74 安全电子选举问题84.1 选举模型94.2 多项选择多的电子选举方案14104.2.1 方案定义104.2.2 方案评价115 保护私有信息的几何判定问题125.1 安全点积定义125.2 安全点积协议136 小结147 课程感受错误!未定义书签。参考文献151 引言随着社会信息化和电子商务与电子政务的不断进展，数据成为社会的重要资源，面对时刻在高速增长着的数据，越来越多的人开头思考如何将这些数据转换成有用的信息和学问。比方连锁超市经理期望从交易数据库中开掘客户的消费习惯，电信运营商期望从客户通话记录中建立恶意欠费用户通话模型，银行经理期望能基于信用卡持卡人历史记录建立优良客户特征模型，传统的数据库技术远远不能满足这种深层次的数据分析处理需求，于是数据挖掘Data mining，DM应运而生。所谓的数据挖掘就是“从数据中提取出隐含的过去未知的有价值的潜在信息”1，它是数据库学问觉察Knowledge-Discovery in Databases，KDD中的一个步骤。然而，在数据挖掘技术应用不断深入的同时，数据挖掘技术对数据隐私的威逼也日益引起人们的关注。或担忧其数据被误用， 或顾虑某些隐蔽于数据背后的敏感信息被“挖掘”出来，人们往往不情愿供给数据参与数据挖掘工作，这就使得数据挖掘失去了根底。在这样一个背景下，争论如何在保持数据隐私的前提下进展数据挖掘是一件格外有意义的工作。当前，隐私保持数据挖掘Privacy Preserving Data Mining ，PPDM争论引起了国内外学者的广泛兴趣，已经开发了一系列的技术。隐私保持数据挖掘技术针对待处理数据分布的不同可以分为两类：集中式和分布式。集中式的主要有随机扰乱、随机响应、数据交换、规章隐蔽的启发式方法、k-匿名和 l-多样性方法等等，而分布式中最常用的是多方安全计算密码技术。本报告主要就多方安全计算技术，选取了该领域比较经典的几个问题做了一些整理工作。2 多方安全计算概述生活中，常常会有多方各自拥有自己的数据，期望协作进展数据挖掘，但每个参与方都不期望让其它方看到自己原始数据的情形。比方各商业银行期望进展合作进展信用卡欺诈分析，各电信运行商期望合作进展客户流失模型分析，它们的数据有相像的属性，但都不期望向合作方透露具体的数据，同时期望得到数据挖掘结果。这就是多方安全计算应用于数据挖掘的现实需求模型， 将该现实需求模型抽象化，得到多方安全计算的根本任务如下： 大于或等于 2 的参与方，在无可信第三方参与的状况下，执行协议，得到共同或分别拥有的结果，但参与方不期望向任意其它方泄漏自身的隐私数据。多方安全计算在密码学中更一般的描述是：n 个参与方 p ，p ，p ，每个参与方 p 持有隐秘的输入 x ，希12nii望计算一个共同函数：f(x ，x ，x )，计算完毕的时候，各方12n得到正确的输出 f(x ，x ，x )，同时自己的隐秘输入 x 没有12ni泄露给其它的参与方。留意到，假设有可信第三方，那么多方安全计算任务就变得 格外简洁：各参与方把自己的输入数据传给可信第三方，由可信第三方将计算结果传给参与方即可。但现实中可信第三方很难找 到，于是多方安全计算任务就变得很困难。多方安全计算争论由华人学者姚期智开创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有一个公开密钥 E 与私有密钥 D 。BB(1) Alice 选择一个大随机数 x，并用 Bob 的公开密钥加密。c = E(x)B(3-1)(3)Bob 计算下面的 100 个数：y = DuB(c - i + u ) , u Î 1,100(3-2)其中，DB是 Bob 的私有解密密钥 Bob 选择一个大的素数 p( p应当比 x 稍小一点，Bob 不知道 x，但Alice 能简洁地告知他 x 的大小) 然后计算下面的 100 个数：Z = ( yuumod p )，u Î 1,100(3-3)然后验证对于全部的 uv，并对全部的 u 验证：z - zuv³ 2(3-4)0 < zu< p - 1(3-5)假设不成立，Bob 就选择另一个素数并重复验证。(4)Bob 将以下数列发送给 Alice：z ，z，z ，z+1，z+1， ，z+1，p12jj+1j+2100(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 个数确定在数列z ，z ，z 之中的某一个，该数列中的数据逆向使用式3-212j自然得到 x；假设 i>j，那么第 i 个数确定在数列z +1，z +1，j+1j+2z +1之中的某一个，由于该数列中的数据都加了 1，逆向使用公100式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 个消息(或者数据)x ，x ，x ，通过执行不经意传输协议，Bob 能够基于自12m己的选择得到且只能得到其中的一个消息 x (1im)，而对其他i消息x ，x ，x ，x ，x 则一无所知。Alice 对 Bob 选12i-1i+1m择了哪一个消息也一无所知。现将文献 6和7提出的不经意传输协议做如下整理。设 q 为一素数，p=2q+1 也是一个素数。Gq为一阶 q 群，g、h为 G 的两个生成元，Zqq表示自然数模 q 的最小剩余集，(g，h，Gq)为双方共知，Alice 有 m 个消息：M ，M ，M ，Bob 期望得到其12m中的一个，Alice 不知道 Bob 得到了哪一个。协议如下：Step 1：Bob 选择一个期望的(1m)与一个随机数 rZ ，计算 y=grh mod p并将 y 发给 Alice。qStep 2：Alice 计算以下 m 个二元组的序列 C=(a ，b)，(a ，b )，(a ，b )其中：1122mm.a = g kimod p，bii= M (y / hii)k mod p，kiiÎ Zq，1 £ i £ m(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=Y ，Y，Y ，其中：Y = g i bì0 + R= ïi R12,假设i - b = 0- b >100( , )ií100 +ïi,假设i0î200 + Ri,假设i - b < 0Step 2：利用不经意传输，Alice 能够选择她情愿得到的唯一的数 Y =g(a，b)。不经意传输方案保证了 Alice 可以打算要得到a的唯一的数，而 Bob 并不知道Alice 选择了哪一个数。假设 Y <100，a那么 a=b；假设 100<Y <200，那么 a>b，假设 200<Y <300，那么 a<b。aaStep 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 个投票人P ，P ，P 在投票前均已12n注册，并知道全部注册选民的合法身份标识各选民地位公平，选 票权重一样投票完毕后，每个选民都可以计票，不需要设置特地 的可信第三方作为计票中心。（3） 选票构造。假设最多有n 个投票人P ，P ，P 参12n与投票，共有 m 个候选人C ，C ，C ，每一张的选票由 m12n列组成，每列由k 位构成k= êëlog n úû + 1 ，其中，前k-1 位为 0，2最终 1 位 ai值取决于投票人，假设投票人对候选人 Ci投赞成票，则a =1，否则 a =0，因此选票总位数为 mk，明显上述选票是一个多ii精度整数。4.2 多项选择多的电子选举方案144.2.1 方案定义假定选民是合法的投票人，已通过注册，取得合法的身份标识 P ，可以进入投票系统进展选举活动，方案分为本地表决、发i送选票、统计选票 3 个阶段。（1） 本地表决每个投票人 Pi1，n在电子选票上对 Cj1，ijm进展表决。a j1，m取值为 1 表示赞成，取值为j0 则表示反对，由此得到一个二进制序列，并将该二进制数转换成十进制数。（2） 发送选票每个投票人 Pi1，n均将自己的选票十进制数i随机地拆分为 n 个更小的整数 v ，使得v= ån v，然后利用安全ijijij =1信道将 v 发送给选民 P j1，n，ji每个 P在收到ijji其余 n-1 个投票人的随机数 vj1，n，ji之后，计算和式v¢i= ån vjij =1ji，其中 v 是 Piii自己持有的随机数。3统计选票每个投票人 P i1，n将自己的求和结果 v 播送ii给其余的投票人 P j1，n，ji。每个投票人 P 在收ji到其余 n-1 个投票人的播送结果之后，即可计算全部的选票之和T。.T = ån v ¢ii =1= åni =1ån vjij =1=ånj =1ån vjii =1=ån vjj =1= ån vii =1(4-1)最终每个 Pi将十进制整数转换成二进制数，然后对每位进展截取，即可得到每一位候选人 C j1，m的得票数。j4.2.2 方案评价外表上看，以上通过安全多方求和方法进展投票和计票，除了最终的计票结果外，不泄露任何投票人选票的隐秘，实现了保密投票。但是认真分析可以觉察，当候选人数 m 不是特别大的时候，投票人 Pi对于候选人 Cj是否投票就具有可破解性，由于候选人越少，投票人投票后所产生的二进制序列转化成十进制数得到的潜在组合就少，例如当候选人数只有三个人的时候，投票人的投票数转化成十进制只有 8 种可能：73，72，65，64，9，8，0。在这八种组合的根底上关心以拆分项大小的限制等信息，对投票人的投票构造进展破解是完全有可能的。因此，该方案的选票保密性还有待进一步完善，不过随着候选人人数的增加，该方案的优越性也会进一步得到表达。目前在电子选举问题中除了上文所展现的多项选择多问题外，还 有很多值得争论的问题，比方电子评审和陪审团表决时的保护隐 私的电子评审问题、上市公司股东大会中的含权选举问题以及工 程工程投标中的平均值中标问题等。这些问题与生活实际联系非 常严密，解决的难度也很大，还有待进一步争论。5 保护私有信息的几何判定问题随着科学技术的进展，人类争论开发太空的力量在不断增加， 国际上不同的科研机构之间都期望开展合作来加快自己的争论进程。然而由于涉及到国家的安全与利益，这种合作是极其有限的， 任何一个机构都不会轻易向其他合作方公开自己的技术。例如两个不同的国家各自都研制出自己的太空碎片分布图，为了确保自己的飞行器在太空飞行过程中不会与太空碎片发生碰撞，他们都期望能同时参考对方数据来提高飞行的牢靠性，然而为了各自国家的利益，两方都不会向对方泄露自己的数据信息。上述问题就是在安全两方计算环境下，判定空间几何对象间 的相对位置关系问题。当前，针对这一问题的争论成果还是较为 丰富的，前人已经给出了点到直线、平面的距离以及点、线、面 等几何对象的相对位置判定协议、线段相交判定协议、圆、椭圆 的关系判定方法、保护隐私的圆与圆、圆与直线的位置判定协议 等多种几何判定协议。由于本报告的篇幅限制，不行能对这些协 议一一进展整理，但是这些协议的根底大都是安全点积协议，因 此下文中重点对安全点积协议进展整理介绍。5.1 安全点积定义安全点积协议更早是在 Du Wenliang 等学者的一系列论文中实现的15，他们提出了安全点积定义：Alice 有向量 X=X ，X ，12X )，Bob 有向量 Y=(Y ，Y ，Y )和标量数值 v，计算完毕，Alicen12n.得到 X·Y+v，而 Bob 不知道这个值。Bob 不直接得到这个值，但Bob 可以将该值减去 v，进而间接使用 X、Y 两个向量的点积，可见满足这样定义的安全点积协议有着较高的安全性，为了简便起见，这里本文争论当 v=0 的状况，即：Alice 有向量 X=X ，X ，X )，Bob 有向量 Y=(Y ，Y ，12n12Y )，他们协作计算得到点积 X· Y = ån x´ y ，但相互并不知道对n方的数据安全点积协议。5.2 安全点积协议iii =1下面本文展现了文献16和文献17中设计和应用的一个安 全点积协议。这个协议表达了多方安全计算应用的一个原则：泄露一些不重要的信息，以猎取更好的效率。输入：Alice 有向量 X=X ，X，X)，Bob 有向量 Y=(Y ，Y ，Yv)。12n12输出：X 和 Y 的点积。Step 1：Alice 和 Bob 协商产生一个随机 n*n/2矩阵 C。Step 2：Alice 随机产生向量 n/2×1 向量 R=r ,r ,r ，12Alice 产生 n×1 向量 X，X=C×R， Alice 产生 X=X+X，Alice 将 X发送至 Bob。n/2Step 3：Bob 令s¢= X ¢¢· Y =åni =1x ¢¢i´ y ，iBob 产生 n×1 向量 Y=CT×Y，Bob 将 S和 Y向 Alice 发送。Step 4：Alice 计算s¢¢= Y ¢· R =ån /2 y ¢i =1i´ r ，iAlice 计算 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 C Protocols for secure computationA In： Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer ScienceC1986:l62-l673 Yao A CHow to generate and exchange secretsA In：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 symposium0n 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 IntematioalCryptologyConference，LNCS 537C1990:77-936 MNaor,BPinkas.EfficientoblivioustransferprotocolsA. Proc 12th Ann Symp Discrete AlgorithmsC.NewYork:ACMPress,2023. 448- 457.7 Wen Guey Tzeng. Efficient 12out2of2noblivious transfer schemes with universally usable parametersJ. IEEE TRANSACTIONS ON COMPUTERS,2023,53(2) :232- 240.8 李顺东，戴一奇，游启友姚氏百万富翁问题的高效解决方 案J电子学报，2023，(5)：769-7729 肖倩，罗守山，陈萍，吴波半诚恳模型下安全多方排序 问题的争论J电子学报，2023，36(4)：70971410 秦静，张振峰，冯登国，李宝无信息泄漏的比较协议J软件学报，2023，15(3)：421-42711 刘文，王永宾. 安全多方信息比较相等协议及其应用.电子学报，2023，5：871-875.12 D.Chaum.Untraceable ElectronicMailReturn Addresses and Digital Pseudonyms. Communications of theACM, 1981, 24(2): 848813 O Goldreich. Secure multi-party computation(working draft)OL. :/ wisdom.weizmann.ac.il/home/oded/publichtml/foc.html,19 98.14 仲红，黄刘生，罗永龙基于安全多方求和的多候选人电子选举方案J计算机争论与进展J2023，(8)：1405-141015 DuWenliang,AtlallahMJ.SecureMulti-partyComputationalGeometryA.In:Preceedingsof7thInternationalWorkshoponAlgorithmsandData Structures,LNCS2125C.2023: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 Mining2023：639-64417 Clifton C，Kantarcioglu M，VaidyaJ，et a1T00ls for privacy preserving distributed data miningJACM SlGKDD Exploration2023，4(2)：28-34