立即下载 知乎日报 每日提供高质量新闻资讯

知道了这个方法,两个人不需要裁判就能玩暗军棋

图片:Unaowphm / CC BY-SA

用密码学玩暗军棋 -- 闲聊多方计算

东天阳,微软研究院博士后

暗军棋

我们先来回顾一下儿时玩的军棋游戏,然后探讨一下如何使用密码学来代替裁判。军棋游戏的目标是通过在棋盘上移动自己的部队攻占对方的军旗。 当两方的棋子碰撞时,采取如下规则

  1. 司令 > 军长 > 师长 > 旅长 > 团长 > 营长 > 连长 > 排长 > 工兵
  2. 炸弹与任何非军旗棋子相遇时,双方都消失
  3. 工兵 > 地雷
  4. 地雷 > 除炸弹和工兵以外的任何子力
  5. 任何棋子 > 对方的军旗 (游戏结束,一方胜利)。

军棋有 明 与 暗 两种下法。在明军棋中,双方的棋子正面朝上放置。暗军棋是一种更刺激的玩法,双方把棋子扣过来背面朝上,用来隐藏自己的布阵和行动。但是暗军棋的特点是需要一个裁判:当两枚棋子碰撞的时候,裁判观看棋子的正面,然后执行上述的吃子规则。那么问题来了:如果没有裁判,两个人还可以玩暗军棋吗?

YES! 用密码学不仅能实现暗军棋,还可以不依赖公正的第三方(裁判 / 法官 / 拍卖行) 来进行任何博弈(古董拍卖,德州扑克,狼人杀等等…)不过实现的方法稍微有一点复杂,所以我们先来讲简单的情形~首先,两枚军棋的碰撞可以抽象成一个比较函数:

假设我的军长是 10 级,对方的连长是 3 级,那么因为 10 > 3, 所以比较的结果是 1 ,我的军长吃掉对方的连长。问题是,我拥有数字 10,对方拥有数字 3, 我们怎么能在不透露具体军阶的情况下,比较这两个数的大小呢?这里我们就要隆重介绍 --- 姚期智院士的百万富翁问题!

百万富翁问题

在文章[1]中,姚老师提出了如下问题:

两个富翁的财产是 1 到 10 之间的整数。他们如何在不透露自己财产的情况下,比较谁更富有?

很容易看出,百万富翁问题和暗军棋比较军衔问题是等价的:无非是比较大小。我们下面来介绍姚老师的精妙解法 ---

假设富翁王有  亿资产,李有  亿资产。王选取一个公钥,使得李可以传递加密的信息。

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

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

注意:这十个数字看起来应该是完全随机的,关键是等式  成立。

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

这样一通复杂的操作之后,李检查第 j 个数字。如果等于  的话,说明这个数字没有被加一,所以 i >= j. 反之,则 i < j。

这个过程的绝妙之处在于:在协议完成之后,王不知道 j 的具体值,而李也不知道 i 的值, 但是双方都知道谁的财富更多,这就是安全多方计算。一般来说,在甲只知道 x,乙只知道 y 的情况下,双方可以合作计算一个函数 f(x,y)。协议完成时,只有函数值是公开的,而彼此都不知道对方的输入值。

回到暗军棋

在解决了百万富翁问题之后,暗军棋的玩法就很简单了。 在每次两枚棋子碰撞的时候,只需要对弈两方进行一次上述的比较计算就可以了。有细心的同学要问了:且慢,这种玩法下难道不可以作弊吗?比如我的棋子只是 2 级,但我可以在比较的时候输入一个 10 级,而对方是无法发现的,因为计算结果只会表明我的棋子比他大?确实如此,注意到上面的协议是无法确保输入的数字和棋子的军阶是一致的。但是解决的方法也很简单,如在游戏结束之后,双方都翻开自己的所有棋子,再对照游戏记录进行明军棋的复盘,就可以找出有没有人作弊了~

安全多方计算(secure multiparty computation)

安全多方计算,可以说是密码学中的又一项黑科技。它可以看作是上面比较函数的一个推广,是可以实现任意数量的参与者共同计算任意函数的!它的应用就非常广泛了,所有需要公正裁判的场景,都可以用这个协议来代替裁判~

两个经典的应用:

拍卖 -- 对应的函数是取所有输入的最大值。利用安全多方计算,在拍卖结束后每个人的出价都还保持隐私。

选举 -- 对应的函数是对所有输入求和(假设 1 代表选举人 A , 0 代表选举人 B)。在这里,安全多方计算可以确保 每个人的投票是保密的,而且计票完全公正。

两个新颖的应用:

共同好友 -- 两个初次见面的人希望找到彼此的共同好友,而不向对方透露自己所有的好友。这里双方的输入是两个集合,对应的函数是取交集。

合作机器学习 -- 对应的函数是一个训练算法,而输入是每人各自的 data set。这个应用是近年来兴起的。如果使用得当,可以打破数据的隐私壁垒。

那么这么强大的协议是怎么实现的呢?这就得介绍到姚老师的神作乱码电路 了。今天先到这里吧~

附加思考题:在上面的百万富翁问题的解法,有一步是取十个明文除以素数 p 的余数。这一步可以省略吗?

参考文献

[1] Yao, Andrew C. "Protocols for secure computations." Foundations of Computer Science, 1982. SFCS'08. 23rd Annual Symposium on. IEEE, 1982.

扫描二维码下载知乎日报

支持 iOS 和 Android
二维码下载知乎日报
阅读更多 婴儿打疫苗,针打完几秒后才哭,是反应迟钝吗? 下载 「知乎日报」 客户端查看更多