密码学协议举例[5]–平均薪水问题|文艺数学君

平均薪水问题

问题来源

指某个公司的n个员工想了解他们的月平均薪水是多少，但是每个员工又不想让其他人知道自己的薪水，那么他们的平均薪水应该如何计算。

对上述问题进行抽象，得到下面的模型：对于n个秘密输入x1,x2,x3...,xn，如何计算如下的函数值，并且上述计算不能有任何第三方参与。

解决办法

1. A1选择一个随机数r，并使用r+x1(x1表示A1的薪水)发送给A2；
2. A2收到后，是不知道A1的薪水的，因为里面加了一个随机数（这个随机数可以很大，以至于看不出原始数据的数量级），在加上他的薪水r+x1+x2；
3. A3执行与A2同样的操作，A4，A5...An-1继续同样的操作；
4. An将r+x1+x2+... ... +xn发给A1；
5. A1收到后，减去随机数r，得到x1+x2+... ... +xn，在除以n就可以得到公司员工的平均薪水；
6. A1向A2，A3，A4，... ... An公布平均薪水的结果；

存在的问题即改进方法

但是上面的做法会存在一个小问题，如果A1截取了A2发给A3的数据r+x1+x2，此时A1就可以计算出A2的薪水（通过使用r+x1+x2-r-x1）。

其实问题的解决也是十分简单的。我们可以在n个员工之间共同确认一种公钥密码体制。当A2将消息传给A3的时候只需要拿A3的公钥加密即可。由于此时A3的私钥只有A3有，而其他人没有，故此时A1无法计算出A2的薪水。

修改后的流程如下：

1. A1选择一个随机数r，并计算出r+x1(x1表示A1的薪水)，将r+x1用A2的公钥加密并发送给A2；
2. A2收到后，使用A2的私钥解密，并加上他的薪水得到r+x1+x2，将r+x1+x2使用A3的公钥加密并发给A3；
3. A3执行与A2同样的操作，A4，A5...An-1继续同样的操作；
4. An将r+x1+x2+... ... +xn使用A1的公钥加密并发给A1；
5. A1收到后使用A1的私钥解密，得到r+x1+x2+... ... +xn，减去随机数r，得到x1+x2+... ... +xn，再除以n就可以得到公司员工的平均薪水；
6. A1向A2，A3，A4，... ... An公布平均薪水的结果；

这个比较好理解，就不举例子了。