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

  • A+
所属分类:密码学协议
摘要从生活中的例子来解读关于密码学协议中的平均薪水问题。

平均薪水问题

问题来源

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

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

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

解决办法

  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公布平均薪水的结果;

 

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

  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: