既想比富，又不愿泄露家底，换你会如何做？「隐私计算系列之二」

“假设有两个百万富翁，他们都想知道谁更富有，但又都想保护好自己的隐私，不愿意让对方或任何第三方知道自己真正的财富值。那么，如何在保护好双方隐私的情况下，比较出谁更有钱呢？”

1982 年，那时还没有 Windows，Nvidia 也还没有成立，苹果公司还没有名气，姚期智在他的论文里面提到了一个有意思的问题：百万富翁问题。

你或许没有听说过姚期智，但你大概率知道，中国最好的计算机学科在清华，而清华大学中又有一个班，聚集了一批最顶尖的计算机学生，这个班就叫做“姚班”，姚期智正是这个班的领导者。

姚期智是中国计算机学术和教育的第一人，也是图灵奖创立以来首位获奖的亚裔学者。

我们看回开头的烧脑问题，里面有一对矛盾：想知道谁更富有，似乎非公布个人财产情况不可，但两人又都不愿对方或者第三方知道自己的财产数。

乍一看，这根本是个无解的悖论。

但在密码学研究者的眼中，这其实是一个加密学问题，换成稍微专业点的表述是：一组互不信任的参与者，在需要保护隐私信息一集没有可信第三方的前提下，如何进行协同计算的问题。

这个问题也叫做“多方计算问题” (Secure Multi-Party Computation，MPC) 。

回到百万富翁的问题中，解答逻辑其实并不深奥，为了好理解，我们将问题简化一下。

姑且认为这两人都是十万富翁，财富值大于 1 小于 10，单位为万，两人都坦诚不虚报财产，过程中也不做任何小动作，简单的解题思路如下：

1、两人先找来 10 个一模一样的密闭投币纸箱，再去金店购买全新的金币、银币、铜币若干。

找个空无一人的屋子，把箱子摆成一排。

2、富翁甲独自进屋，假设他的财产是 7 万，就往第 7 个箱子里投入一枚金币，前面 1-6 个箱里各投入一枚铜币，后面 8-10 个箱里各投入一枚银币。

给所有的箱子上锁，离开屋子，叫富翁乙进来。

3、富翁乙进屋，假设他的财产是 5 万，就找到第五个箱子，给这个箱子上锁。

然后抱着这个被上了两把锁的箱子出来，烧掉其余九个箱子。

4、由于这 10 个箱子完全一样，所以屋外的富翁甲并不知道富翁乙抱出来的是哪一个箱子。

两人分别打开自己上的锁：如果箱子里是金币，说明两人钱一样多；如果是银币，说明富翁乙更有钱；如果是铜币，说明富翁甲更有钱。

百万富翁问题的提出和解答，体现了多方安全计算面临的困境和解题的思路，但严格来说，百万富翁问题是安全多方计算的一个特例，它属于安全两方计算 (Secure Two-party Computation) ，因为故事里只涉及到两个人。

4 年后的 1986 年，在百万富翁问题的基础上，姚期智又提出了学界第一个安全多方计算通用解决方案：混淆电路。

混淆电路要解决的问题是，当几个通信方需要一起输入某些数据，并通过相同函数计算出一个结果，但通信各方又都不希望其他人知道自己的输入是什么。

和百万富翁问题相比，混淆电路能够在多方参与的情况下给出答案，有兴趣的朋友可以自行了解，后面有机会也会单独出一篇内容。

关注好奇拆解计划，带你轻松拿捏硬核知识。