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

作者: , 共 1956 字 , 共阅读 0
系列:机器统治世界

查看该系列所有文章

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