咱们先来回忆一下儿时玩的军棋游戏，而后讨论一下如何经常使用明码学来替代裁判。军棋游戏的指标是经过在棋盘上移动自己的部队攻占对方的军旗。当两方的棋子碰撞时，采取如下规定

军棋有明与暗两种下法。在明军棋中，双方的棋子侧面朝上搁置。暗军棋是一种更抚慰的玩法，双方把棋子扣上来反面朝上，用来暗藏自己的布阵和执行。然而暗军棋的特点是须要一个裁判：当两枚棋子碰撞的时刻，裁判观看棋子的侧面，而后执行上述的吃子规定。那么疑问来了：假设没有裁判，两团体还可以玩暗军棋吗？

YES!用明码学不只能成功暗军棋，还可以不依赖公正的第三方（裁判/法官/拍卖行）来启动任何博弈（古董拍卖，德州扑克，狼人杀等等。。。）不过成功的方法稍微有一点复杂，所以咱们先来讲便捷的情景～首先，两枚军棋的碰撞可以形象成一个比拟函数:

假定我的军长是10级，对方的连长是3级，那么由于10>3,所以比拟的结果是1，我的军长吃掉对方的连长。疑问是，我领有数字10，对方领有数字3，咱们怎样能在不泄漏详细军阶的状况下，比拟这两个数的大小呢？这里咱们就要浩荡引见---姚期智院士的百万富翁疑问！

百万富翁疑问

在文章[1]中，姚教员提出了如下疑问：

很容易看出，百万富翁疑问和暗军棋比拟军衔疑问是等价的：无非是比拟大小。咱们上方来引见姚教员的精妙解法---

假定富翁王有亿资产，李有亿资产。王选取一个公钥，使得李可以传递减密的消息。

首先，李选取一个随机的大整数，把用王的公钥加密，获取密文。李发送给王。

王收到密文之后，对启动解密，获取十个数字。再选取一个适当大小的素数,把这十个数字除以的余数记作.

留意:这十个数字看起来应该是齐全随机的，主要是等式成立。

最后，王对这一串数字作如下操作：前面i个数不动，前面的数字每个加一，而后发回给李。

这样一通复杂的操作之后，李审核第j个数字。假设等于的话，说明这个数字没有被加一，所以i>=j.反之，则i

这个环节的绝妙之处在于：在协定成功之后，王不知道j的详细值，而李也不知道i的值，然而双方都知道谁的财富更多，这就是 安保多方计算 。普通来说，在甲只知道x，乙只知道y的状况下，双方可以协作计算一个函数f(x,y)。协定成功时，只要函数值是地下的，而彼此都不知道对方的输入值。

回到暗军棋

在处置了百万富翁疑问之后，暗军棋的玩法就很便捷了。在每次两枚棋子碰撞的时刻，只要要对弈两方启动一次性上述的比拟计算就可以了。有认真的同窗要问了：且慢，这种玩法下难道无法以舞弊吗？比如我的棋子只是2级，但我可以在比拟的时刻输入一个10级，而对方是无法发现的，由于计算结果只会标明我的棋子比他大？确实如此，留意到上方的协定是无法确保输入的数字和棋子的军阶是分歧的。然而处置的方法也很便捷，如在游戏完结之后，双方都打开自己的一切棋子，再对照游戏记载启动明军棋的复盘，就可以找出有没有人舞弊了～

安保多方计算(SecuremultipartycomputatION)

安保多方计算，可以说是明码学中的又一项黑科技。它可以看作是上方比拟函数的一个推行，是可以成功 恣意数量 的介入者独特计算 恣意函数 的！它的运行就十分宽泛了，一切须要公正裁判的场景，都可以用这个协定来替代裁判～

两个经典的运行：

拍卖--对应的函数是取一切输入的最大值。应用安保多方计算，在拍卖完结后每团体的出价都还坚持隐衷。

选举--对应的函数是对一切输入求和（假定1代表选举人A,0代表选举人B)。在这里，安保多方计算可以确保每团体的投票是隐秘的，而且计票齐全公正。

两个陈腐的运行：

独特朋友--两个首次见面的人宿愿找到彼此的独特朋友，而不向对方泄漏自己一切的朋友。这里双方的输入是两个汇合，对应的函数是取交加。

协作机器学习--对应的函数是一个训练算法，而输入是每人各自的dataset。这个运行是近年来兴起的。假设经常使用切当，可以冲破数据的隐衷壁垒。。。

那么这么弱小的协定是怎样成功的呢？这就得引见到姚教员的神作 乱码电路 了。当天先到这里吧～

附加思索题 ：在上方的百万富翁疑问的解法，有一步是取十个明文除以素数p的余数。这一步可以省略吗？

参考文献

[1]Yao,andrewC."Protocolsforsecurecomputations."InProc.23rdAnnualSymp.onFoundationsofComputerScience(FOCS),pages160–164.IEEE,1982.

标签： 消息安保、 明码学、

本文地址： https://yihaiquanyi.com/article/d40934837d3db479d056.html

上一篇：BAT岗位之路如何拓展中间件技术大牛为你详...
下一篇：暗访实名制政策的影响暗访实名制政审怎么写...