姚氏百万富翁问题的原始协议
机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 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\)个数分别为:
$$Rp^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\)的大小。
一些中文参考资料:
- 密码学协议举例(四):秘密数字的比较,对每一步都举了例子。
- 姚期智百万富翁问题的 python 演示 。
3. 协议的缺陷
论文里的协议非常简单,因而优美。但一个很大的不足是它的复杂度是指数级别的,即在计算过程中需要传递指数级别的信息。注意,这里的指数级是相对于\(\log(N)\)而言的,因为两个富翁的钱数可以用\(\log(N)\)长度的数来表示。
姚先生的这篇论文的引用数超过 4000 ,无数人做了更进一步的工作。其中有一些多项式复杂度的协议(更准确地说,平方级复杂度)。不过思路更复杂,等有时间再写一下。
另外还有一个问题是协议是非对称的。在操作之后,富翁甲可以知道自己的钱和富翁乙的钱谁更多(但不知道富翁乙的具体钱数),但富翁乙一无所知。
作者暂无likerid, 赞赏暂由本网站代持,当作者有likerid后会全部转账给作者(我们会尽力而为)。Tips: Until now, everytime you want to store your article, we will help you store it in Filecoin network. In the future, you can store it in Filecoin network using your own filecoin.
Support author:
Author's Filecoin address:
Or you can use Likecoin to support author: