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

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

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

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

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

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

甲取一个随机数 rr，计算并发送x=E(r)−ax=E(r)−a。

乙收到x=E(r)−ax=E(r)−a后，由于并不清楚aa的值，只能枚举 E(r)∈X={x+1,x+2,⋯,x+N}E(r)∈X={x+1,x+2,⋯,x+N}。然后解密集合XX里的所有数据：

R={C(x+1),C(x+2),⋯,C(x+N)}(1)(1)R={C(x+1),C(x+2),⋯,C(x+N)}

乙知道RR里面有一个是甲选择的rr，但不知道具体是哪个。

乙取一个质数pp，将集合 RR 里的数据改成：

Rp={C(x+i)modp | 1≤i≤N}(2)(2)Rp={C(x+i)modp|1≤i≤N}

保留RpRp的前bb项，后面的项增加 1 ，和pp一起发送给乙。

最终甲收到的NN个数分别为：

Rbp={δi,b+C(E(r)−a+i)modp | 1≤i≤N}(3)(3)Rpb={δi,b+C(E(r)−a+i)modp|1≤i≤N}

其中 δi,b=1 if i>b else 0δi,b=1 if i>b else 0。

甲检查收到的第 aa 个数，如果恰好等于rr，表示乙的bb大于等于自己的aa。否则表示乙的bb小于自己的aa。但甲无法获知准确的bb。

这里的第三步是关键，也是协议的神来之笔。缺少这一步，乙的bb将被暴露，甲只需要解析：

{E(δi,b+C(E(r)−a+i)) | 1≤i≤N}(4)(4){E(δi,b+C(E(r)−a+i))|1≤i≤N}

由于∀y,E(C(y))=y∀y,E(C(y))=y，甲只需要将上面的序列和{E(r)−a+i | 1≤i≤N}{E(r)−a+i|1≤i≤N}比较即可知道bb的大小。

一些中文参考资料：

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

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

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

Q. E. D.

Recommend