利用多的安全多方计算.DOC

1、利用“多”的安全多方计算贾伊迪普动态 Vaidya计算机系科学与 CERIAS普渡大学250 N 大学圣西拉斐特在 479072066jsvaidyacs.purdue.edu克里斯克利夫顿计算机系科学与 CERIAS普渡大学250 N 大学圣西拉斐特在 479072066cliftoncs.purdue.edu摘要安全多方计算实现与各方数据计算的全球协作功能，同时他们的私人数据并没有被透露。在折痕关于敏感数据的计算机联网，以及提高处理数据能力，整合和利用这些数据的方法下，使时间实际安全多方计算的时机已经成熟。本文调查的办法是给出了一个方法，即一个有效的协议，为双方使用不受信任的第三方，可用于

2、构建一个高效率的同辈对同辈安全的多方协议。分类和主题描述K.4.4 计算机与社会：电子商务安全一般条款安全关键词隐私，多方计算，分布式安全计算1。引言在增强的隐私和安全的新时代意识作用下，安全的分布式计算正在获得越来越多的张力。大量存在的情况下，各个方面有本地数据，并希望分享这些数据获取全球有益的成果。但这种愿望往往冲突，共享和整合这些数据可能侵犯隐私权的限制。理论结果显示它可以安全地计算几乎所有功能没有透露其他以外的任何输出。然而，在实际执行此计算方式是另一个问题。一般方法是对复杂的操作效率超过大型数据集。这促使许多领域对安全协议的研究计算的实际效率。重点一直是计算效率，沟通效率，或两者兼而

3、有之。大部分工作已经在两党协议，都是可证明安全和有效的。有三个或更多（越来越多的）当事人，挑战（和所谓的机遇）变得更加困难。但是，有希望。我们提出一个方法，其中，通过使对某些假设有什么可以做得到，不能透露，我们充分利用在多方计算各方很多种。建议对所有问题的具体解决方案是一个非常艰巨的任务。与其这样，我们提出一个有效的方法，允许多解的产生提供。安全两方解决问题的存在。未成熟，和可量化的，额外的信息集是可以被发现。我们首先是安全多方计算和有关工作的讨论简短评论。在第 3 节，我们给出一个通过安全多方计算执行的隐私限制非正式的定义，并说明各种办法，争取多方计算。我们的方法来产生方协议是在第 4 节，

4、其次是在第 5 节的一些示范性的例子。我们结束了今后工作的想法简短的讨论。2。相关工作目前已在计算工作之间的合作实体互相不信任对方。这可以是任何计算排序：科学，数据处理，甚至秘密共享。两方安全计算姚的首次调查，后来推广到多方计算。由戈德赖希等人的论文证明了一个安全的解决方案存在任何功能。该方法是采用如下：函数 f 来计算，首先作为一个方面代表的组合，然后运行为每个门电路中短期协议。每一个参与者得到（随机选择）部分，即输入和输出值。进行没有关于输入的功能，是因为哪一方获得的份额是随机决定的信息。在最后，双方交换他们的资料，使每个计算获得最终结果。该协议已经被证明起到预期的结果没有公布以外的任何其

5、他结果。这种做法，虽然它的吸引力在 SIM 卡和通用性，但意味着该议定书的大小对电路，对输入的大小取决于大小而定。其他一般技术已经被提出来。然而，一般的方法，通常是相当大的投入效率不高，特别是大量的当事人。该电路的评价大投入的成本，导致在一系列的算法更有效地为具体计算功能。许多协议已经发展到解决具体问题，都在安全文学出版以及在应用领域的文献。有些包括安全总结，数量积，有些科学计算，安全并集，安全交集的基数，私人置换和计算熵。林德尔和平卡斯研究了计算的水平分区的使用，这是聪明的泰勒级数展开的应用程序数据熵问题。阿格拉瓦尔等人还独立提出了计算交点，交点尺寸，加入和参加大型数据库大小的技术。瑙尔等人

6、定义了一个由多方减少的方案将两方的解决方案。 Kantarcioglu 和 Vaidya 也定义了一个类似的架构，使隐私保护多方数据挖掘。这两种假设所有各方将能够商定具体各方的信任，也提升了安全风险失去所有的资料， “打击风险”的只有两个当事人。本文的削减要求，任何两个双方必须在至少一个对方同意的信任。这是一个可行的选择，有必要的外部受信任的第三方，这往往难以实现。杜和阿塔拉是一种安全多方计算问题及其应用，而优秀的调查提出一个实用的方法，采用安全的多方的计算，接受对安全的妥协。我们进一步扩大这一想法。根据有关隐私的限制较为实际的假设，我们演示了如何利用一个问题（特别是非常复杂的各方的多样性）

7、，以建立一个有效的解决方案。3。模型的安全多方计算我们现在举一个品种的安全多方协议的概述。说明，我们将用一个简单的和良好的研究例如，标量点积问题。虽然这是一个两方的问题，想法很容易扩展到更多的方面。问题是，正式定义如下：假设甲方有载体X =（ 1， 。 。 。时，Xn ）和乙方载体为Y =（Y1的。 。 。 ，吟） 。双方希望标量计算的产品（或点积）X Y =P ni=1 xi _ yi,没有透露任何有关X或信息，这不是没有原因的，结果发现X Y .3.1与信任的第三方安全协议最简单的方法是基于一个信任的存在第三方。一个方面是一个值得信赖的人私人价值可以发现在不违反隐私限制。如果我们只有一个方

8、面，是由参与者，一个非常简单的协议，所有的信任是可用。根本每一方发送其输入到受信任的第三方，各个方面的信任和共享的计算结果。而该相同的协议，可利用的数量与本地机构无关。在现实中，许多协议的工作是这样的。一个常见的例子是支付代管。买方发出支付给托管代理，谁验证收到付款，并告诉卖方进行交易。只有当货物交付并支付代管代理发行。在以上（如地产）复杂的交易，可能会有额外的当事方，例如按揭公司，以及代管代理人所需的计算可更为复杂。这是“黄金标准安全多方计算”。有了这个例子，我们假设一个值得信赖第三方T ，A和B 都送他们到T的载体产品执行点，并返回结果。明确地A 和B都没学到任何东西，除了从协议结果，也不

9、（假设保密通信）作出任何除了T，这也是一个普遍有效的协议。最大的缺点该模型是对失去隐私的 - 必须有一个方面，保证所有的数据可信。法律问题是，商业秘密和隐私问题结合起来利用这样的方面存在疑问，特别是与许多缔约方。安全多方计算的目标大约是在一个可信的情况下建立这种模式。3.2绝对安全的多方协议与此相反的极端是只进行了一个计算，各方谁拥有数据和愿望的结果。因此，一个安全的两方协议是完全进行，是由两方，如，艾丽斯和鲍勃，不涉及任何在计算其他各方。每个都有自己的输出，与别人得到什么无关。通常情况下，没有简单的假设，这些协议是非常低效。有几个在文献标注产品的有效和安全的协议标量运算只用两方产品。该协议是

10、在完全代数：一方添加偶合其价值观和发送给对方，而这部分计算和发送数据计算从自己的价值观回来。由聪明的选择原偶合，和正确的价值观被遣送回原来那方，第一方能够标量计算的产品。总成本大约是1.5次输入的大小。此协议是不完全私人的，因为在协议中看到随着外部学习的私人资料显示值的一半，只显示另一半。其他协议使用更昂贵的加密方法实现隐私逼近不可信第三方模型，假定各方不“作弊”的执行该协议。计算的SecureMulti的文献显示几乎所有的功能可以私下计算。在这个模型，一般的做法并不规模。由于好复杂的问题和对大型数据集，从而导致许多专门为特定功能的协议。我们现在看两个可供选择的模式，使实际和有效的解决方案，同

11、时保持同等程度的隐私。3.3两方协议的一个不受信任的第三方一个不受信任的第三方的存在使效率协议没有透露私人信息。这个想法的不受信任的第三方，它愿意执行某些在协议的计算（或许为各方费）。这是不可信的数据或结果。在这一方的信任，它是：1。不得相互串通同与会各方对任何侵犯隐私的信息，2。正确地执行该协议。正确执行该协议只规定，以保证正确的结果，甚至一个不诚实的第三方无法了解个人信息的相互勾结的情况下。通常情况下，第三方是在加密的形式提供了一些信息。通过加密，我们只是说，第三方不能给它的任何资料在该协议所涉及的当地各方的援助。第三方执行计算的加密数据，可能与其他各方的信息交流在这个过程中。最后，计算结

12、果是加密透露给当地各方，谁能够解密的结果。对于我们的产品的协议标量，考虑以下几点：A 和B共同决定一个（可能是随机的）置换，N，这是只知道他们的内容。 A和B也随机生成一个共同的载体，包括n个元素。现在，A生成的向量X而B生成Y，A 和B 发送X 和Y不受信任的第三方U。U的计算数量积S=XY。恒置换两个向量的数量不会对产品的影响，只是因为它有效地改变了补充订单的总和。因此，S = X Y + X R + Y R + R R.。A和B 也发送到X和Y。U减去这些来自S 来获得， S0 = X Y + R R.。送回来到A 和B ，谁减去得到最终结果。由于没有R,也不知道到 U置换是什么或结果。

13、此协议也是非常有效的，由于通信复杂性，因为排列随机向量R可以用一个随机生成种子，通信成本为O（n），其中n的大小的载体。3.4两方协议服务器与商品比弗介绍了另一种模式的商品第三方服务器模型。在此模型中，服务器会生成一种商品是由双方所使用的数据，使他们能够“同步”及其议定书。这个信托要求是作为一个不受信任的第三方。关键的实际区别是，第三方，通常具有较低的计算成本，而不是作为一个不受信任的第三方商品的服务器。一个商品的服务器基础的协议是由于在：这个想法是，商品服务器生成两个随机向量，Ra和 Rb, 两个部分ra, rb, 在标准的产品R a Rb (i.e., ra + rb = Ra Rb).

14、这一对，(Ra, ra)发送到A，而(Rb, rb)发送到B 。A 和B进行一涉及这些对计算和自己的投入找到标产品。完整的协议是由于在：服务器协议是在商品普遍低于协议的第3.3类高效率。但是，一个有说服力的证明，第三者不知道什么是平凡的，因为它从来没有得到任何信息。3.5综述不使用任何其他各方的多方协议常常很复杂，效率低下。当一个可信的第三方，使我们能够轻松地解决问题，这样一个完全可以信赖的方假设并不总是现实。协议使用商品服务器或不受信任的第三方允许符合隐私权的限制，实现可接受的性能，优雅的解决方案。由第三方协议的基本假设是不勾结：第三方将不符合工作的参与者之一，以侵犯另一个参与者的隐私。不同

15、的计算模型概述图1。4。高效多方参加的协议一个问题与不可信的第三方和商品服务器协议是要求外部的一方愿意执行计算。虽然这可能是一个有趣的商业模式在本节中，但是我们提出一个替代办法。对于联想功能，如果我们稍有松懈的安全保障，我们就可以创造一个任何功能高效率的多方协议，而我们有一个有效的两方在不受信任的第三方模型协议。其基本思想是利用参加者为不可信的第三方。通过选择什么与会者可以看到他们作为一个不受信任的第三方的角色，我们可以确保他们的学习只是一个外部的一方更会。4.1假设关闭安全协议的一般行业的效率。然而，在安全产生一个大的效率改进小妥协。此外，由于这是一个特定的解决方案，而不是一个普通的技术，它

16、需要实际的两方协议将作为插件使用。这些问题现在讨论细节。4.1.1功能限制这里介绍的一般方法并不适用于所有的问题。事实上，它是只适用于一类函数纤维蛋白原（代表我们的一类函数的一般方法可解），其定义如下属性。一个K输入的公式y = f(x1, . . . , xk) 属于公式Fg,，当且仅当y = f(x1, . . . , xk) = x1 x2 xk, 并进一步，这就是联想。这些函数的例子包括设置联盟/ 交集，以及大多数添加剂/ 乘法功能。4.1.2两个厂商解决方案的协议P主要的假设是，一个有效的安全协议P的存在是为了解决双方的问题。该协议可能使一个不受信任的第三方服务器或单个商品，即使用，

17、协议P是在任一节描述的协议类协议3.3或3.4节。此协议P将被用来作为一个插件的一般协议。它提供的P允许的，而不是原来的结果，双方的第三方。这种不对称的协议允许使用情况是可逆的，即给予=预算外，我们还可以判断x的。在这种情况下，对称的协议，使该结果与数据将自动侵犯当事人的隐私。协议的例子这是在第5条所述的问题。4.1.3适应性协议P这不是一个实际的协议，我们提出一个如何建构一个协议，并证明它的安全方法。这就要求纳入总体规划的协议P一体化。小的修改就必须整合到协议。该协议P应该是合理的修改纳入可塑性。这也不是一个真正的假设，而是一个工程的要求得到整个事情的工作。4.1.4合谋核心安全的假设是相同

18、的，在不受信任的第三方需要/服务器模式的商品。所选择的第三方不得相互勾结，任何一方对另一方。因此，对每一个双方必须能够找到至少一个其他的方，它相信不勾结。虽然不诚实和不受信的当事人可以很难发现这个，但是在许多实际情况下，它是可行的。例如，在商业关系这一共同的信任程度（例如，不披露协议），但法律或合同规定可以并处比可以通过这样的协议感到满意较强的限制。这为我们寻找替代非勾结外部第三方愿意参加该议定书，但这实现起来常常是困难的。4.2总体框架考虑到多方，我们的目标是计算一个函数y 2Fg,，这里y = f(x1, . . . , xk), 是当地的k各方的投入，请注意，由假设4.1.1，由于y 2

19、 Fg, y = x1x2 x 。通过4.1.2假设，我们有一个协议P到安全的计算两个输入功能。关键的想法是创建两个分区P0和P1. 并且同样分裂成两个分区K表的各方。现在，我们可以利用分区中的各方Pi 为不受信任的第三方评估分区 P1i。想像这一点，该分区上建立一个二元树P i与叶作为在这一方的Pi（图2）。最多可以有P1i内部节点二进制树。由于（几乎）均匀，以及以下不变的一贯主张：|P1i| _ |Pi| 1, 把它们都赋值为i 。因此，在有足够的其他分区作为当事方的内部节点。在分区中的当事人P1i是作为商品在服务器或不可信的第三方分区中的各方Pi 。在第一轮， 把K / 4作为K / 2

20、双方在第一个分区其他第三方分区行为的当事人。至于余下的logK / 2 - 1轮为其他的K / 4，沿树作为第三方当事人的行为向上第二分区。对于每个第三方收到一些中间结果的形式，利用它的下一轮，重要的是要分析的数据量。如果需要限制信息的披露，那么这个显示，在这一点上的第三方就要修改该协议。整个过程如图2所示，在那里我们展示了分区的前k / 2求解P0各方组成的过程。因此，所有各方 Pk/2+1, . . . Pk作为一个单一的电话/ 商用服务器的应用协议P时，在叶节点向当事方的第三方发送的行为。有一种logK / 2在其中的协议 P几个通话的同时进行。类似的过程，是对其他分区做P1，用两个最顶

21、层的双方代表使用安全双方协议P0来计算最终结果。每一方可能获得了一些有关其他各方数，但这违反了安全多方计算的要求。但是，只要是在严格的信息披露（和可证明的）边界举行，就会使这个高效率和实用性有限的信息披露。正如我们将要显示在第5节，中间的信息披露一般都可以用介绍的形式，不透露私人信息。4.2.1安全鉴于安全多方计算（SMC）的风格证明安全协议P，它是直接提供整个安全协议的证明。这个被证明后，申请的组成酒取决于定理，考虑P是子程序调用。根据内部节点的意见，一般会做简单模拟，鉴于该协议P结果使用该节点的一方不可信一样，都是由该当事人看到的结果的一部分看待。这使得一个简单的模拟显示没有其他的证据显示

22、数据。这样的一个例子是用于以下证明。5。实例在本节中，我们给出了一些应用实例的一般方法，以解决实际问题。5.1节提供了一个解决办法计算的异或相当琐碎的问题。 5.2节的方法提供了更具体的表现来计算交集。5.1异或琐碎的应用在分布式计算的位集中这种方法提供了一个简单的演示。该问题如下：鉴于各K方P1 . . . Pk，各有它自己的私有位双向，安全计算s = b1_b2_ _bk,其中标志着XOR运算。安全地计算异或使只有双方没有任何意义，因为结果显示对方的输入，但它是一个对 n 2可行的问题时，当事人，或双方，如果一些第三方（只有第三方）允许查看结果。考虑A和B与它们源数据的双方x和y，和第三方

23、U，这是可以知道结果的是XY ，但是不信任的任何X或Y。一个合适的协议P如下：A 和B 两个随机比特共同同意 R1和R2。然后, A 发送M a = x _ r1 _ r2 到U, 同时 B发送M b = y _ r1 _ r2 到U . U现在可以轻松地找到的结果：U可以采取两个它接收到的信息获取所需的逆 x y的异或结果。这个协议可以很容易地扩展到两个以上当事方的一般方法，即为简单的应用程序。各当事方的全套分为两个分区。为一个分区计算树的内部节点，我们用来自其他分区的各方。对重复应用协议P 各级要给予预期的效果。每一方都没有学习，但由于这些包括它自己的位没有一些额外的信息（即低于它的子树中

24、的位异或），但没有获得有关在树的叶子个人数据值的信息。唯一的例外是根，作为其位于包含在它的结果得知，但由于学习一切需要的最终结果是什么，学习是不可避免的。一个轻微的变化将允许一个完全安全的协议。而不是只选择R1和R2，双方将选择在与其他叶子节点的随机值，这样才会从根本上取消了额外的偶合合作。5.2安全交集一个更安全的获得有用的例子是在几个集合的交集中比较大小。问题的定义如下。有k个方面，P1, . . . , Pk, 与每一个集合SK 来自一个共同的（全局）U。他们希望计算| kj=1 Sj |,，即共同相交集的基数。这是非常有用的几个应用，例如数据挖掘关联规则（见21详情 。）由于交集是结合

25、的，我们可以利用我们提供的第4条协议有一个安全的两方协议来使用不受信任的第三方。现在，我们勾勒出双方协议P使用不受信任的第三的方来计算|S a Sb|。协议背后的核心思想P是用一个交换加密方案（例如，与这两个键的 RSA 18保密）。交换性确保Ek1(E k2(x) = Ek2(Ek1(x)。缔约方A 和B生成加密密钥在EA和EB中区别。一个加密的设置项中EA将其发送到 B。类似地，乙加密EB 发送到 A。现在每个网站有自己的加密密钥的接收项目，并发送双重加密设置起点S0a和S0b到U。U现在发现这些两个集合的交集。由于加密，一个项目x 2 Sa Sb将对应于一个项目Ea (Eb(x) = E

26、b(Ea(x)，在这两种S0a和S0b中出现。因此，该路口的大小为|S0a S0b| = |Sa Sb|。因此U的交集的大小，和有关的项目没有什么交集。作为最底层以上的收益，扩大这两个以上当事方很简单。那么，在较高的层次，给他们的兄弟姐妹的子女的关键各方加密。由于一方从来没有看到来自兄弟姐妹的孩子中的任何值（即使加密），知道密钥提供任何信息。详情载于以下。类似的协议可以构建以确定并集的大小。6。结论保护隐私和在分布式计算有意义的数据是一个艰巨的任务。然而，已在研究安全的分布式计算了很大进步。从理论上讲，这两个双方和多方协议是可能的，几乎任何计算。切实可行的解决方案已被发现双方计算的几种类型中。

27、然而，安全的多方计算都没有得到很好的探索。我们已经提出了转换双方的协议，使用到安全的多方协议，不需要第三方不可信的第三方的方法。通过对合成定理和第4款可证明安全协议的使用，它是直接产生，并证明安全的多方协议能给予安全不受信任的两个第三方当事人的协议。该方法只需要非勾结的假设，并愿意透露一个小而可证明的其他信息有限。这种方法适用于任何关联功能。开发一个通用的方法去超越联想功能，是一个有趣的未来研究方向。实用的安全多方计算的使用容易产生对新的计算对应于一组特定的参与者的要求。产生这样的协议和证明任务，他们的安全必须变得更加容易。一种方法是通过提供一个安全的协议工具包和方法，去结合他们。我们已经提出了一次这样的组合方法。沿着这些路线的进一步工作，使安全多方计算成为一个电子的合作，这样可以成为保留隐私的重要推动者。