6.2 保密的多方计算
保密的多方计算是一种协议，在这个协议中，一群人可在一起用一种特殊的方法计算许多变量的任何函数。这一群中的每个人都知道这个函数的值，但除了函数输出的明显东西外，没有人知道关于任何其他成员输入的任何事情。下面是几个例子：
协议#1
一群人怎样才能计算出他们的平均薪水而又不让任何人知道其他人的薪水呢？
（1）Alice在她的薪水上加一个秘密的随机数，并把结果用Bob的公开密钥加密，然后把它送给Bob。
（2）Bob用他的私钥对Alice的结果解密。他把他的薪水加到他从Alice那里收到的结果上，用Carol的公开密钥对结果加密，并把它送给Carol。
（3）Carol用她的私钥对Bob的结果解密。她把她的薪水和她从Bob那收到的结果相加，再用Dave的公开密钥对结果加密，并把它送给Dave。
（4）Dave用他的私钥对Carol的结果解密。他们他的薪水和他从Carol那收到的结果相加，再用Alice的公开密钥对结果加密，并把它送给Alice。
（5）Alice用她的私钥对Dave的结果解密。她减去第一步中的随机数以恢复每个人薪水之总和。
（6）Alice把这个结果除以人数（在这里是4），并宣布结果。
这个协议假定每个人都是诚实的。如果参与者谎报了他们的薪水，则这个平均值将是错误的。一个更严重的问题是Alice可以对其他人谎报结果。在第五步她可以从结果中减去她喜欢的数，并且没有人能知道。可以通过使用任何4.9节中的比特提交方案要求Alice提交她的随机数来阻止Alice这样做，但当Alice在协议结束时泄露了她的随机数，Bob就可以知道他的薪水。
协议#2
Alice和Bob一起坐在一家餐馆中，正在争论谁的年纪大。然而他们都不想告诉对方他们的年龄。他们可以都把他们的年龄悄悄地告诉一个可信赖的中立方（例如侍者），那个人在脑中比较两个数并对Alice和Bob宣布这个结果。
关于上面这个协议存在两个问题。一个是，普通侍者不能处理比确定两个数之中哪一个大更复杂问题的计算能力。另一个是，如果Alice和Bob真的关心他们的信息的秘密，他们不得不将这个侍者扔进一个汤碗淹死，以免他告诉酒楼服务员。
公开密钥密码术提供了一个远非如此残暴的解决办法。有一个协议是Alice知道一个值a，且Bob知道一个值b，他们能一起确定a是否小于b，而Alice得不到b的任何信息，Bob也得不到a的任何信息。并且，Alice和Bob能相信计算的有效性。所有的密码学算法是这个协议的重要部分，详细情况参见23.14节。
当然，这个协议不能防止主动欺骗者。没有办法能防止Alice（或Bob）谎报他们的年龄。如果Bob是一个隐蔽执行这个协议的计算机程序，那么Alice通过反复执行这个协议可以知道他的年龄（一个计算机程序的年龄是从程序被写出的时间长度？还是从它开始运行的时间长度？）。Alice可以在执行这个协议时，指定她的年龄为60。在得知她的年纪大时，她可以将她的年龄指定为30，再次执行这个协议。在得知Bob要大一些之后，她可以称她的年龄为45再次执行这个协议，依此继续下去，直到Alice发现Bob的年龄达到她所希望的精确度。
假设参与者不主动欺骗，很容易把这个协议推广到多个参与者。任何数量的人通过一系列诚实应用这个协议可以发现他们的年龄的顺序；并且没有一个参与者能够得知另一个参与者的年龄。
协议#3
Alice喜欢用玩具熊做一些古怪的事。Bob则沉迷于大理石桌子。他们都对他们的癖好特别难为情，但却想找一个有共同生活风格的伴侣。
在保密的多方计算约会服务（Secure Multiparty Computation Dating Service）中，我们为这样的人设计了一个协议。我们已将一个令人惊奇的嗜好名单编号，从“土豚”到“阻特层装”。Alice和Bob彼此分开，通过一个调制解调器相连，他们便能参与一个保密的多方协议。他们可以一起确定他们是否有同样的癖好。如果有的话，他们可以期望建立一种终生的幸福关系。如果没有，他们可以彼此分开，而且他们的特殊个人信息仍保持机密。没有人，甚至是保密多方计算约会服务也不知道。
下面是该协议如何工作的：
（1）使用一个单向函数，Alice将她的癖好做散列得到一个7个数字的字符串。
（2）Alice用这7个数字作为一个电话号码，拨号，给Bob留下一条消息。如果没有人回答或电话号码无效，Alice给这个电话号码申请一个单向函数直到她找到一个与她有相同癖好的人。
（3）Alice告述Bob她为她的癖好申请一个单向函数所需的时间。
（4）Bob花了与Alice相同的时间散列他的癖好。他也用这7个数字作为电话号码，询问其他人是否有留给他消息。
注意Bob有选择明文攻击。他可以散列一般的癖好并拨所得的电话号码，查找给他的消息。只有在不可能得到足够多的明文消息的情况下这个协议才能真正执行。
也有一个数学的协议，类似于协议#2。Alice知道a, Bob知道b，并且他们在一起可以确定是否a=b，但Bob不知道关于a的任何事且Alice不知道关于b的任何事。详细情况请参见23.14节。
协议#4
对保密的多方计算存在另一问题，见文献[1373]：这里有一个七方委员会，他们定期开会对某一些问题秘密表决。（不错，他们秘密地统治着世界——不要把我告诉你的事告诉任何人。）所有委员会成员可以投票表决Yes或No。另外，有两方有权利投“超级选票”：S—Yes和S—no。他们不一定要投“超级选票”，如果他们愿意，他们可以投一般选票。如果没有人投“超级选票”，则选票的多数决定这个问题。在一张或两张结果相同的“超级选票”情况下，所有普通选票被忽略。在两张结果相反的“超级选票”情况下，普通选票的多数决定这一问题。我们需要一个能安全执行这类投票的协议。
下面两个例子将阐述投票过程。假设有五个普通投票者：N1到N5，和两个超级投票者：S1和S2，下面是关于问题#1的选票：
S1 S2 N1 N2 N3 N4 N5
S - yes no no no no yes yes
在这个例子中唯一起作用的选票是S1的票并且结果是yes。下面是关于问题#2的选票：
S1 S2 N1 N2 N3 N4 N5
S - yes S -no no no no yes yes
这里两张超级选票抵消，普通选择的多数no选票决定这一问题。
如果隐藏“超级选票”抑或普通选票是决定性选票的信息无需隐藏，这就是一个安全投票协议的简单应用。如果隐藏这一点很重要，就需要一个更复杂的保密多方计算协议。
这种投票可能会发生在现实生活中。它可以是一个公司组织结构的一部分，在这里某些人比其他人有更大的权力，或者它是联合国的做法的一部分，其中某些国家比其他国家有更大的权力。
无条件多方安全协议
这只是一般定理的一种简单情况：任何n输入的函数可以被n个人用这种办法计算，使得所有人都知道函数的值，但任何少于n/2个人的一群人都得不到除了他们自己的输入以及输出信息值之外的任何附加信息。细节见[136，334，1288，621]。
保密电路计算
Alice的输入为a，Bob的输入为b。他们希望一起计算一些普通函数f（a，b），这样使得Alice不知道Bob的输入情况Bob也不知道关于Alice的输入情况。保密多方计算的一般性问题也称为保密电路计算。这里，Alice和Bob可以创造一个任意的布尔电路，这个电路接受来自Alice和来自Bob的输入并产生一个输出。保密电路计算是一个完成下面三件事的协议：
（1） Alice可以键入她的输入且Bob不能知道它。
（2） Bob可以键入他的输入且Alice不能知道它。
（3） Alice和Bob都能计算出这个输出，双方都确信输出是正确的且没有一方能窜改它。
保密电路计算的详细情况参见文献[831]。