百万富翁问题— DavidCai.eth

最近在看零知识证明，了解到了一个很有意思的问题，即《姚氏百万富翁问题》，该问题由图灵奖得主姚期智老师提出。

算是对开始了解零知识证明的朋友起到 ... DavidCai.ethdavidcai.eth百万富翁问题0x5670December29th,2021最近在看零知识证明，了解到了一个很有意思的问题，即《姚氏百万富翁问题》，该问题由图灵奖得主姚期智老师提出。

算是对开始了解零知识证明的朋友起到抛砖引玉作用的经典问题。

下面展开一下问题的描述，以及姚期智老师给出的一个答案。

问题 假设有两个富翁甲，乙，他们的财产数量分别为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)modP C(E(X)-a+2)modP ... C(E(X)-a+a)modP=>即XmodP ... C(E(X)-a+N)modP 第四步 在上述取余结果计算中，前b项不变，后N项全部+1，即： C(E(X)-a+1)modP C(E(X)-a+2)modP ... C(E(X)-a+b)modP C(E(X)-a+(b+1))modP+1 ... C(E(X)-a+N)modP+1 然后将这组结果与P全部发送给甲。

由于第a项为：C(E(X)-a+a)modP即XmodP，若a