互不知情，也能计算平均工资

互不知情，也能计算平均工资？

五个同事决定计算他们的平均工资：在大家互相不告诉薪水的情况下，如何才能做到这一点？

问题描述：

由于提问者绑定了「数学」话题，可以合理推测问题有隐含条件：不借助第六人。

更进一步，应当要求所选择的方法有一定防止作弊和少数人串通的能力。

□王希

答案分为以下几个部分：第一部分介绍一些基本概念和讨论的大前提，第二部分分析目前知友们提出的方案，第三部分基于一位知友的答案进行改进，第四部分讨论几何均值的情况，第五部分总结。

一、介绍

在一个有信息需要保密的过程中，我们应该如何考虑消息的安全性？主要分为两个方面：

第一是消息的保密性。也就是说，要尽量保证不该知道这个消息的人不能知道与消息相关的信息（注意是信息而非内容。内容是指完整地掌握所有的信息，而信息则是与之相关的东西，比如最后一个比特，二进制中 1 的个数等等。这些信息的泄露也是需要避免的）。

第二是消息的可靠性。也就是说，A 收到了 B 发出的消息，他应该有办法验证这条消息确实是 B 发出的，而不是中间人掉包后的消息。

在研究一个协议的安全性时，我们经常构造一个「游戏（game）」，游戏中有两方：敌手和挑战者。挑战者进行保密通信，而敌手则需要窃取秘密或破坏通信。根据不同的假设，我们给予敌手一些能力，同时对通信中消息的保密性和可靠性做一些要求。最后，我们考虑在面对有这种能力的敌手时，需要的保密性和可靠性是否能够达到要求。

具体到这个问题中，我们先讨论一些大前提，再讨论其他知友给出的方案的安全性，构造一些攻击，最后提出一个相对来说安全性较高的方案。为了一般性，我们直接讨论 n 个人的情况。

大前提 1：所有的节点必须是诚实的。也就是说，每个人提供自己的工资信息时不能撒谎。

说明：这是一个很不现实但又必须做的假设。原因很简单：如果有且只有一个节点撒谎，那么他将获得其他四个人的平均工资，同时其他四个人不知道五个人的平均工资，且完全无法验证；如果有至少两个人撒谎，那么没有人可以同时知道所有人的平均工资。无论如何，整个协议将变得没有意义。

大前提 2：最坏的情况下只有 n-2 个节点进行合谋，攻击其余两个节点。

因为如果 n-1 个节点攻击另外一个节点，无论如何都一定成功。

（注： n-1 个节点如果可以合谋，可以在这 n-1 个节点不泄露自己工资的情况下得到剩下一个人的工资，这是一个递归的过程。简单起见，我们不允许这样的攻击。虽然 @Pegasus 的答案讨论了这样的攻击）

大前提 3：他们只能靠互相交流信息来获得答案。

也就是说，没有一个可信第三方来帮助计算。这个要求否决了找会计等答案。

二、方案分析

下面我们分析一些知友提出的方案的安全性。

1. 扑克牌/麻将/大富翁钞票

在这些知友的方案中，每个人通过扑克牌等将自己的工资信息拆分，之后混在一起加起来求平均。由于这些牌是扣起来混合的，因此不可能知道其他人的工资。

分析：这个方法在大多数情况下可以保证自己的工资不被其他人所知，但一定会有信息泄露。比如说我们用红桃代表千位，你看到翻开后的牌里有一个红桃九，而你自己的工资只有一千多，矛盾是不是就产生了？但是如果是理想情况，你只能知道最后的平均工资，而不能知道每一个人工资的任何信息。

由于这个方案泄露了大家工资的信息，因此不可靠。

2.第一个人加上一个随机数，最后减掉（这个答案）

这样的方式是符合最基本的安全要求的。也就是说，如果每个人都只知道自己的工资和传来的数字，没有人可以知道其他人的工资。

分析：这个方案几乎没有直接泄露的信息，但少数人合谋可以对某个人的工资数进行攻击。如果第一个人知道了第三个人收到的数字，他就可以知道第二个人的工资；2 号知道了 4 号收到的数字，就知道 3 号的工资……对于任意一个 n ，只需要知道前后的数字就可以算出一个人的工资，这个协议还是比较脆弱的。

3.每个人拆分自己的工资并发给其他人（这个答案）

在这种情况下，任意 n-2 个人合谋也只能得到其余两人的平均工资，无法获得更多的信息。这是目前最好的方案。

但是注意，这个方案我们进行了一些假设：每个人发给其他人的信息不会被这 n 个人之外的敌手窃听，也不会被篡改。但实际中并不是这样。我们的方案应该能防止这些事情的发生。

下面，我们提出这个问题中的敌手能力和安全性要求，并对方案 3 做出改进来满足我们提出的要求。

三、方案改进

现在我们假设这 n 个人不在一起，彼此之间只能通过计算机发送信息。而通信的信道是不可靠的，也就是说我们不能验证这条消息是不是对方发来的、没有被篡改过的，传输的信息也会被敌手得到。

而我们的要求包括两方面。第一，这 n 个人中即使有 n-2 个人合谋，也只能知道剩下 2 人的平均工资，不能获得更多的信息；第二，敌手即使可以获得所有的通信消息，也可以进行篡改。在这种情况下，敌手不能获得关于工资的任何信息，也不能篡改通信内容而不被发现。

在这里我们还要再做两点补充。第一是敌手的计算能力是有限的，这允许我们进行公钥加密和签名（这两个概念马上会具体介绍）；第二是公开信息是可靠的，也就是说，我可以公开一个字符串作为我的一个「公钥」，这个公钥没有保密性，任何人都可以看到。而这种情况下这个字符串是无法伪造的，也就是所有人都可以确定我确实公开的是这段字符串。

下面我们分别介绍公钥加密和数字签名。在传输中的消息是会被敌手看到的，所以要对消息进行加密。但如果使用传统的加密方式，需要加密者和解密者拥有共同的密钥，在这种情况下是做不到的（不考虑密钥交换，这个过程还是用公钥思想实现的）。因此我们需要使用另一种加密方式：加密密钥是公开的，每个人都可以看到并使用；但解密密钥是保密的，只有消息的接受者持有。这样，当 Alice 想给 Bob 发送一条保密消息时，他只需要使用 Bob 的公钥对消息进行加密再发给 Bob ，Bob 使用解密密钥进行解密即可。

这种加密方式需要一个困难问题，大家把困难问题理解为一个敌手和挑战者都无法进行的计算问题即可。比如说离散对数问题：在一个群 G 中， ，给出群 G 和 的值，求 。这里的对数和我们之前讨论的不同，是在群中的。实数中的对数是容易计算的，而一般情况下，群里的离散对数是难以计算的。

另外，我们还要做一个假设（CDH 假设）：在群 G 中，给出 ，计算 是困难的。

这样，我们就可以构造一个公钥加密体制，也就是著名的 ELGamal ：

1.Bob 找一个群（比如 ）和一个生成元 ,私钥为 ，公开 ，保密 . 

2.Alice 先随机选择一个数 ，然后分别计算 和 ,将其发送给 Bob. 

3.Bob 计算 ，可以验证其等于 ,解密成功。 （这里的描述不是很严谨，大家理解意思即可）

下面我们介绍数字签名。在现实生活中，我们经常需要对文件进行签名，证明我们已经阅读并认可该文件。类似地，在数字世界中，我们也需要对文件进行签名。签名可以防止信息的伪造：因为我们提到了，每个人可以公开一个字符串，这个字符串是可靠的，所有人都可以验证它属于你。类比公钥，你把一个消息用你的私钥进行处理，得到的值任何人都可以用你的公钥进行验证，这就达到了目的。

类似地，ELGamal 同样可以进行签名的构造。比如 Alice 要对消息 m 进行签名：

sAlice 随机选择 k 计算 和 dsis

Bob 验证

其实具体的方法不重要，大家只要知道有一种方法，可以验证一条消息是不是由某个人发送的就行了。

好了，下面我们完整地过一遍：

1.每个人的工资分别记为

2.每个人将工资随机地分解为 n 个数之和，记为 等等

3.每个人在自己分解的 n 个数随机排序，将第 个数用第 个人的公钥加密（如果是给自己的则省略），用自己的私钥对加密后的消息进行签名，然后将消息与加密结果一起发送给第 个人

4.每个人验证签名后用自的私钥解密其余 n-1 条消息，将其与自己留下的一个数共 n 个数求和

5.把求和结果用其余 n-1 个人的公钥分别加密，并对结果签名，将加密后的消息与对应的签名发送给对应的人

6.每个人验证签名后解密所有消息，计算平均值即可

四、几何均值

在第三部分最后，我们已经给出了所有人算术平均值的方案，可以证明在加密算法和签名算法安全的情况下，这种方案也是足够安全的。下面我们讨论求几何均值的情况。

如果用类似的方法，我们需要把每个数分解为若干个数的乘积，这是很难做到的。一方面，对整数进行素因子分解本身就不是一件容易的事情；另一方面，有些整数没有足够的素因子，将 1 作为因数之一并不是一个好办法。

看来只有另寻出路了。注意到 ELGamal 加密算法中的消息是作为一个因子的，这给了我们一个提示。构造这样的算法：

1. 其中任何一个人公开一个群 和一个生成元 ，每个人选取一个私钥 和一个随机数 ,公开所有

2. 第一个人计算 ,传给第二个人

4.第一个人计算 ,交给第二个人

关于可靠性只需要再加一个签名即可，不再赘述。

五、总结

这个看起来很简单的问题，深究起来竟然涉及如此多的密码学知识，连我都有些惊讶。这也是我们思考问题的方式：假设每个环节都有泄密或被篡改的可能，然后逐个去排除，让协议更加安全可靠。

第二部分第三个方案是一个很不错的方案，不仅泄露的信息最少，而且很容易类比到任意人数的情况。因此很容易想到在此基础上进行修正。而第四部分纯粹是我突然想到的，画蛇添足了。

事实上，问题本身是一个最简单的安全多方计算问题，有兴趣的朋友可以顺着这个关键词查阅相关的资料。

最后我想说，密码学真的很好玩~

2017-05-23