# 百万富翁问题 By [DavidCai.eth](https://paragraph.com/@davidcai) · 2021-12-29 --- 最近在看零知识证明，了解到了一个很有意思的问题，即《姚氏百万富翁问题》，该问题由图灵奖得主姚期智老师[提出](https://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf)。算是对开始了解零知识证明的朋友起到抛砖引玉作用的经典问题。下面展开一下问题的描述，以及姚期智老师给出的一个答案。 问题 -- 假设有两个富翁甲，乙，他们的财产数量分别为 a, b ，且 1 ≤ a, b ≤ N 。甲，乙两者想知道他们两者的财产数量谁多，但是又不能透露他们具体的财产数量。 解答 -- 乙先生产自己的一对非对称加密（如 [RSA](https://en.wikipedia.org/wiki/RSA_\(cryptosystem\))）秘钥对，即公钥 E，私钥 C 。并像 TLS 通信中一样将公钥 E 发送给甲，然后是自己保留 C 。 ### 第一步 甲再取一个大于 a 的数字 X（尽量取大），将 X 通过乙的公钥加密后得到 E(X) ，然后将 E(X) - a 发送给乙。 ### 第二步 乙取得 E(X) - a 后，由于不知道 X 的具体值，所以也更无从知晓 a 。他将进行一组计算来对 E(X) 进行枚举（对所有 a 的可能范围，即1 到 N），然后使用私钥解密，使得枚举结果中有一项为 X： * C(E(X) - a + 1) * C(E(X) - a + 2) * ... * C(E(X) - a + a) => 即 X * ... * C(E(X) - a + N) 由于 1 ≤ a, b ≤ N 的前提，所以其中必有一项为 C(E(X) - a + a) ，即 X 。 ### 第三步 乙取一个素数 P ，P 尽量比 X 小几个数量级（甲提前向乙透露 X 的数量级并不会有问题）。这时，将上述计算取得的一组结果全部与 P 取余，得： * C(E(X) - a + 1) mod P * C(E(X) - a + 2) mod P * ... * C(E(X) - a + a) mod P => 即 X mod P * ... * C(E(X) - a + N) mod P 第四步 --- 在上述取余结果计算中，前 b 项不变，后 N 项全部 +1 ，即： * C(E(X) - a + 1) mod P * C(E(X) - a + 2) mod P * ... * C(E(X) - a + b) mod P * C(E(X) - a + (b + 1)) mod P + 1 * ... * C(E(X) - a + N) mod P + 1 然后将这组结果与 P 全部发送给甲。由于第 a 项为：C(E(X) - a + a) mod P 即 X mod P，若 a < b，则第 a 项就不会被 +1 。 第五步 --- 甲取得数据后，计算 X mod P ，若 X mod P 存在于乙发送的数据中，则 a < b ，否则 a ≥ b 。由于乙传输的结果经过了取余操作，且 P 比 X 小几个数量级，所以甲无法对原式子进行 100% 正确的还原。 小结 -- 所以这个解答的关键步骤就是第三步，即取余，是进行了一次[同态加密（Homomorphic encryption）](https://en.wikipedia.org/wiki/Homomorphic_encryption)，隐藏了原数据，但保持了结果正确。若不进行取余，而是单纯的让甲通过 X 是否在乙发送的结果中来判断的话，不管 a < b 还是 a ≥ b ，由于甲是知道 X，P，a 和 N 的，甲可以将乙的结果通过公钥再次加密，然后枚举试出乙是在哪一个位置开始进行 +1 操作的。 --- *Originally published on [DavidCai.eth](https://paragraph.com/@davidcai/XukROENEqBsXoY5USvQ0)*