百万富翁问题

[DavidCai1111]

最近在看零知识证明，了解到了一个很有意思的问题，即《姚氏百万富翁问题》，该问题由图灵奖得主姚期智老师提出。算是对开始解零知识证明的朋友起到抛砖引玉作用的经典问题。下面展开一下问题的描述，以及姚期智老师给出的一个答案。

问题

假设有两个富翁甲，乙，他们的财产数量分别为 a, b ，且 1 ≤ a, b ≤ N 。甲，乙两者想知道他们两者的财产数量谁多，但是又不能透露他们具体的财产数量。

解答

乙先生产自己的一对非对称加密（如 RSA）秘钥对，即公钥 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），隐藏了原数据，但保持了结果正确。若不进行取余，而是单纯的让甲通过 X 是否在乙发送的结果中来判断的话，不管 a < b 还是 a ≥ b ，由于甲是知道 X，P，a 和 N 的，甲可以将乙的结果通过公钥再次加密，然后枚举试出乙是在哪一个位置开始进行 +1 操作的。