姚氏百万富翁问题的原始协议

作者: , 共 1547 字
系列:机器统治世界

查看该系列所有文章

机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》

这个问题和文章我很早就听说过,但一直没看过。直到最近思考机器统治世界的问题时,才阅读了这篇论文。简单描述如下。

1. 百万富翁问题

两个百万富翁,想知道谁的钱更多,但都不想让对方知道自己有多少钱。

2. 姚的原始协议

Yao 在论文《Protocols for secure computations》里给了一个非常精妙的答案。

假设富翁甲的钱数为 \(a\),富翁乙的钱数为 \(b\),均满足 \(1 \leq a, b \leq N\)。乙有一个公钥私钥密码对\((E, C)\),将公钥\(E\)发给甲,自己保留私钥\(C\)

第一步:

甲 取一个随机数 \(r\),计算并发送\(x=E(r)-a\)

第二步:

乙收到\(x=E(r)-a\)后,由于并不清楚\(a\)的值,只能枚举 \(E(r) \in X = \{x+1, x+2, \cdots, x+N\}\)。然后解密集合\(X\)里的所有数据:

$$ R = \{ C(x+1), C(x+2), \cdots, C(x+N) \}$$

乙知道\(R\)里面有一个是甲选择的\(r\),但不知道具体是哪个。

第三步:

乙取一个质数\(p\),将集合 \(R\) 里的数据改成:

$$R_p = \{ C(x+i) \mod p \ \ | \ \ 1 \leq i \leq N \} $$

第四步:

保留\(R_p\)的前\(b\)项,后面的项增加 1 ,和\(p\)一起发送给乙。

最终甲收到的\(N\)个数分别为:

$$R_p^b = \{ \delta_{i, b} + C(E(r)-a + i) \mod p\ \ | \ \ 1 \leq i \leq N \} $$

其中 \( \delta_{i,b} = 1 \text{ if } i > b \text{ else } 0\)

第五步:

甲检查收到的第 \(a\) 个数,如果恰好等于\(r\),表示乙的\(b\)大于等于自己的\(a\)。否则表示乙的\(b\)小于自己的\(a\)。但甲无法获知准确的\(b\)

这里的第三步是关键,也是协议的神来之笔。缺少这一步,乙的\(b\)将被暴露,甲只需要解析:

$$ \{ E(\delta_{i,b} + C(E(r)-a+i)) \ \ | \ \ 1\leq i \leq N \} $$

由于\(\forall y, E(C(y)) = y\),甲只需要将上面的序列和\(\{ E(r)-a+i \ \ | \ \ 1\leq i \leq N\}\)比较即可知道\(b\)的大小。

一些中文参考资料:

3. 协议的缺陷

论文里的协议非常简单,因而优美。但一个很大的不足是它的复杂度是指数级别的,即在计算过程中需要传递指数级别的信息。注意,这里的指数级是相对于\(\log(N)\)而言的,因为两个富翁的钱数可以用\(\log(N)\)长度的数来表示。

姚先生的这篇论文的引用数超过 4000 ,无数人做了更进一步的工作。其中有一些多项式复杂度的协议(更准确地说,平方级复杂度)。不过思路更复杂,等有时间再写一下。

另外还有一个问题是协议是非对称的。在操作之后,富翁甲可以知道自己的钱和富翁乙的钱谁更多(但不知道富翁乙的具体钱数),但富翁乙一无所知。

Q. E. D.

系列: 机器统治世界 »
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。
类似文章:
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。
机器统治世界提到,随着科技的发展,我们可以直接用机器来替代政府。所谓机器统治世界,并不意味着机器是世界的主人。机器还是听命于人类,只不过以一种无法被干预的民主投票的方式。所以,机器统计世界的第一要解决的问题就是投票协议。
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。
相似度: 0.102
最近《流浪地球》的热映,掀起了科幻热潮。很多人都在为电影和小说里的情节和逻辑争论不休。而我更感兴趣的是政府形态。
IT » 比特币
最近 bitcoin 很火,我也是最先从云风那里了解到的,后来发现李笑来&霍炬对其都有涉及。不过他们对其具体技术原理的描述还是不够细致,所以我自己把bitcoin wiki又重新看了一遍。 看完之后,疑惑挺多,我对这个体系远没有前面三位这么乐观。诚然,它会成为"Geeks "手中的玩物甚至灰色交易的工具,但要说的达到「一出天下反」的程度,那还需要解决一些技术和金融方面的问题。
今天北京车牌摇号开奖,如果只有一倍概率,中签概率只有万分之四,估计这一辈子都中不了吧。北京车牌目前有巨大的利益,组织者如何保证其中没有猫腻呢?
某些人对绩效评估和分解不屑一顾,认为没必要那么复杂,不就比比谁赚的钱多就行了吗?问题没有那么简单。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
比特币协议里使用了 ECDSA (椭圆曲线签名算法),我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科,才发现它们之间的差异挺大。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
碎碎念 » 奥数, 付云皓, IMO
作者: 付云皓。发表于 2016 年 7 月份。作为两届 IMO 满分金牌,后来一直参与中国顶级奥数圈的教练、阅卷者和出题者工作,作者其对奥数的认识非常深刻。每个想学奥数或者对奥数有疑问的人都应该看一看。
用手机上的微信读书快半年了。App 上显示的累计读书时间为 308 个小时。我越来越喜欢这个产品,给大家推荐推荐。