姚期智院士有哪些学术贡献？ 第1页

Yao's Millionaires' Problem 是一个有趣但复杂的问题，其描述如下：两个富翁如何能够在不暴露具体资产的情况下，比比谁更壕呢？

类似场景还有：公司同事想在不暴露具体工资的情况下看看谁挣得更多；闺蜜们想在不暴露体重的情况下比比谁更瘦；基友们想在不暴露具体数据的情况下比比谁更长。。。凡此种种，都属于 Yao's Millionaires' Problem。

形式化一下这个问题：爱丽丝为，鲍勃为，谁更大？即，是否有？

==============

我们先看一下问题的简化版：不比较的相对大小，只看二者是否相等，即是否有？

对于简化版问题，Twisted Oak 给出了一个非常直观的理解。

假设且，鲍勃首先需要准备4个密码箱并打上标记：

之后鲍勃丢弃掉除标有的箱子之外的所有钥匙（因为对于鲍勃，）。

之后鲍勃把所有箱子给爱丽丝，由于，爱丽丝向标有的箱子内投入纸条YES，向其他箱子投入纸条NO，并将箱子返还给鲍勃。

这时鲍勃用自己仅有的一把钥匙打开标有的箱子，显然里面的纸条是NO，则此时鲍勃知道了，同时不清楚的具体数值。

注意这只是一个非常直观的解释，可以帮助人理解算法的大体流程和原理，实际的细节要复杂很多。比如“密码箱”其实代表着非对称加密算法，而上文加粗的一句话“鲍勃丢弃钥匙”更代表着算法的核心思想：如何让鲍勃只能打开一个箱子（Oblivious Transfer）？

==============

回到原始问题，爱丽丝为，鲍勃为，是否有？

让我们仍旧假设且，相对于简化版问题，算法会复杂一些。基本思想如下：

首先鲍勃生成一个随机数，这里不妨令，鲍勃将 （即）发给爱丽丝。

由于，因此爱丽丝并不知道和的具体数值，他需要做的是，对每个，令 ，并将所有发回给鲍勃。显然，在本例下，。

鲍勃这时只需要查看返回数组中的第2个数，如果，则说明，反之有。

很明显上面的原理是 naive 的，仍旧会暴露的具体数值，这是由于实数域的有序性和加减的可逆性。Yao 转换数域并用加密算法包装了上面 naive 的过程，避免了多余信息的暴露。具体如下：

1. 鲍勃生成一个-bit 随机数，并令，其中为非对称加密算法中的一个密钥。
2. 鲍勃将发送给爱丽丝。
3. 爱丽丝生成一组数，其中，其中为里的第个数，为非对称加密算法中的另一个密钥。
4. 爱丽丝生成一组数，其中，而为一个-bit 的质数来保证中数值至少相差。
5. 爱丽丝生成一组数，其中 。
6. 爱丽丝将发回给鲍勃。
7. 鲍勃计算，并将其与比较，如果，则显然，反之有。

聪明的知友们，现在理解 Yao's Millionaires' Problem 了吗？