多方安全计算之百万富翁问题

百万富翁问题

问题提出

百万富翁问题是1982年姚期智先生在其论文中讨论的一个经典例子。该问题涉及两个富翁Alice和Bob，他们想要比较自己的财富，但又不想透露具体的财富数额。假设 Alice 和 Bob 的财富分别是 百万( )和 百万（ ）, 在 和 不暴露给对方的情况下如何进行比较呢？[1].

解决方案

设 是一个所有元素为 （二进制表示长度不超过N位） 非负整数的集合， 是 到 的置换群. Alice和Bob遵循一下协议就能在对自身资产保密的情况下进行比较：

1. Alice首先从 中随机选择一个元素 作为公钥，将其公开给Bob，同时保留 的逆 作为私钥自己保留.
2. Bob随机选择一个 的整数 ，并利用Alice给的公钥计算

   将 发给Alice.
3. Alice利用私钥 计算

   其中 .
4. Alice随机生成一个 的素数 ，并计算

   其中 . 保证所有 中至少有两个不相等, 否则重新选择 并计算.
5. Alice将素数 以及以下10个数发送给Bob

   重新标记为
6. Bob检查第 ，若 则说明 ，否则 . 将结果发送给Alice.

完成财富比较.

正确性分析

观察步骤2.和3.,由于 ，故必存在某个 （记为 ）值为 ，故有

于是，在步骤5.中，若 ，则

否则

所以在步骤 6. 中 Bob 只需要验证 是否成立就可以判断 与 的大小关系.

安全性分析

Alice 知道的只有 Bob 发来的 以及最后 Bob给的比较结果. 虽然包含 的信息，但是被 Bob 用随机数 遮蔽了，对于Alice 来说 就是一个随机数.

Bob 则只知道 Alice 发来数字 以及第 ，从而推出 ，但不知道其他 的信息，同样不知道 还是 ，也就无法得知 的值.

不过呢，保证以上安全性的前提是协议双方都只进行一次计算，无恶意攻击，且不出现边缘情况. 两种情况描述如下，

• 如 为 9，结果是 Alice 更富有，那 Bob 就自然知道 Alice 的财富 为 9，这种情况下，Alice 也没必要参与比较，因为 Alice 知道 Bob 的财富值肯定小于等于自己的财富值，反过来，若 为 2，同样没有比较的必要.
• 若不限制计算次数，则 Bob 可以通过多次计算窃取到更多关于 的信息. 在步骤5. 中，拿到 后，Bob可以通过攻击函数 获取更多关于 的信息. 如，若比较结果是 ， 则 Bob 随机取数 , 当满足 时, 则可以知道 , 继而知道 ，通过与 对比就可以判断 是否为 9. 这就让 Bob 获取到了不应该被获取的信息.

百万富翁问题描述的是双方（各自数据 ）在不暴露自身数据的情况下共同计算 bool 函数 的过程，

说明多方安全计算的可性行，可以推广到 个数据拥有方在保护各自数据安全的情况下共同计算出函数 的，这就可以实现数据在不可见的情况可用，打破数据壁垒，发挥敏感数据集的应用价值.

参考文献

[1] A. C. Yao, "Protocols for secure computations," 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), Chicago, IL, USA, 1982, pp. 160-164, doi: 10.1109/SFCS.1982.38.