百万富翁问题

• 1. 解决方案
• 2. 协议描述
• 3. 协议说明
• 4. 协议举例

两个百万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让对方及其他第三方知道自己财富的任何信息，这是由中国计算机科学家、2000年图灵奖获得者姚启智教授于1982年在论文《Protocols for secure computations》中提出的姚氏百万富翁问题，开创了密码学研究的新领域：安全多方计算(Secure Multi-party Computation)。

1. 解决方案

假设两个百万富翁AAA和BBB的财产在111到101010之间，AAA为444，BBB为999。

• AAA选择101010个相同的个盒子，按照顺序代表111到101010：
  
• AAA用自己财产的数字与盒子的数字进行比较，如果小于该数字，则放一个黑球，若大于等于则放一个蓝球。

• AAA将盒子上锁，并按111到101010的顺序发交给BBB。

• BBB选择自己财产的数字对应的箱子，即第999个盒子，然后交个AAA。

• 由AAA打开盒子，共同判定结果：蓝球，因此BBB更富有。

现实中，上述方案一般通过密码学工具实现。

2. 协议描述

姚氏百万富翁问题可形式化描述为:对两个秘密输入iii和jjj，判断函数值f(i,j)=i−j≤0f(i,j)=i-j\le 0f(i,j)=i−j≤0还是 f(i,j)=i−j≥0f(i,j)=i-j\ge 0f(i,j)=i−j≥0。

假定1≤i,j≤N1 \le i,j \le N1≤i,j≤N。为了在不让任何第三方参与的情况下比较iii和jjj的大小，又不向对方泄漏各自的数值，则可执行如下的协议:

• step1：AAA和BBB共同协商一种公钥加密体制(EEE为加密算法，DDD为解密算法)。

• step2：AAA随机选择一个大随机数xxx,用B的公钥加密得E(x)E(x)E(x)，然后将E(x)−iE(x)-iE(x)−i发送给BBB。

• step3：BBB首先计算NNN个数yu=D(E(x)−i+u),u=1,2,...,Ny_u=D(E(x)-i+u),u=1,2,...,Nyu​=D(E(x)−i+u),u=1,2,...,N然后随机选择大素数ppp，再计算NNN个数zu≡yumodp,u=1,2,…,Nz_u \equiv y_u \bmod p,u=1,2,…,Nzu​≡yu​modp,u=1,2,…,N接着验证对于所有的0≤a≠b≤N−10 \le a \neq b \le N-10≤a=b≤N−1是否都满足∥za−zb∣≥2\|z_a-z_b|≥2∥za​−zb​∣≥2，若不满足，则重新选择大素数ppp重新验证。最后，BBB将ppp及以下的NNN个数串发送给AAA:z1,z2,...,zj,zj+1+1,zj+2+1,…,zN+1z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1z1​,z2​,...,zj​,zj+1​+1,zj+2​+1,…,zN​+1.- step4：设AAA收到NNN个数串的第iii个数zi≡xmodpz_i \equiv x \bmod pzi​≡xmodp，则结论是i≤ji \le ji≤j；否i≥ji \ge ji≥j。

• step5：AAA 将结果告诉 BBB。

3. 协议说明

(1) 由于zi≡yimodp≡D(E(x)−i+i)≡xmodpz_i \equiv y_i \bmod p \equiv D(E(x)-i+i)\equiv x \bmod pzi​≡yi​modp≡D(E(x)−i+i)≡xmodp，因此
当且仅当i≤ji\le ji≤j时,数列z1,z2,...,zj,zj+1+1,zj+2+1,…,zN+1z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1z1​,z2​,...,zj​,zj+1​+1,zj+2​+1,…,zN​+1中才存在数zi≡xmodpz_i \equiv x \bmod pzi​≡xmodp；否则该数列中任何数模ppp都不与xxx同余，此时i>ji > ji>j。该步骤是协议的核心步骤，通过构造数列，实现了iii与jjj大小的判断，类似于放置黑球与蓝球。

但该协议无法判断出i=ji=ji=j的情况，是该协议的一个缺点，后续相关研究对此进行了改进。

(2)要求znz_nzn​中的任何两个数za,zbz_a,z_bza​,zb​满足∥za−zb∣≥2\|z_a-z_b|≥2∥za​−zb​∣≥2是为了保证BBB发送给AAA的NNN个数的数列z1,z2,...,zj,zj+1+1,zj+2+1,…,zN+1z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1z1​,z2​,...,zj​,zj+1​+1,zj+2​+1,…,zN​+1中任意两个数不同,一般称这样的数列为“好数列”。因为若数列中存在两个数zm=zn，m

(3)A比B先知晓了最终的结果，若AAA欺骗BBB告诉他相反的结论，则该协议是不公平的。为了增加公平性,BBB可以要求与AAA交换角色,即原来AAA执行的步骤现由BBB执行,而由BBB执行的步骤改由AAA执行。这样BBB也可以首先得出结论。

(4)协议只涉及两方的安全计算,可将上述协议推广到任意多方的安全计算协议。

4. 协议举例

设AAA和BBB两个百万富翁的财富，AAA的财富是900900900万，BBB的财富是400400400万，都不超过100010001000万。即AAA和BBB的秘密数分别为i=9i=9i=9和j=4j=4j=4，N=10N=10N=10。

• step1：AAA和BBB选定RSA公钥算法对数据加密，其中n=221n=221n=221，BBB的公钥353535，私钥111111。

• step2：AAA随机选择整数x=92x=92x=92，计算E(x)≡9235mod221=105E(x) \equiv 92^{35} \bmod 221=105E(x)≡9235mod221=105，然后把 E(x)−i=105−9=96E(x)-i=105-9=96E(x)−i=105−9=96发送给B。

• step3：对u=1,2,…,10u=1,2,…,10u=1,2,…,10，BBB分别计算yu=D(E(x)−i+u)=D(96+u)y_u=D(E(x)-i+u)=D(96+u)yu​=D(E(x)−i+u)=D(96+u)即y1=D(96+1)≡9711mod221=193y_1=D(96+1)\equiv 97^{11}\bmod 221=193y1​=D(96+1)≡9711mod221=193y2=D(96+2)≡9811mod221=106y_2=D(96+2)\equiv 98^{11}\bmod 221=106y2​=D(96+2)≡9811mod221=106y3=D(96+3)≡9911mod221=44y_3=D(96+3)\equiv 99^{11}\bmod 221=44y3​=D(96+3)≡9911mod221=44y4=D(96+4)≡10011mod221=94y_4=D(96+4)\equiv 100^{11}\bmod 221=94y4​=D(96+4)≡10011mod221=94y5=D(96+5)≡10111mod221=186y_5=D(96+5)\equiv 101^{11}\bmod 221=186y5​=D(96+5)≡10111mod221=186y6=D(96+6)≡10211mod221=136y_6=D(96+6)\equiv 102^{11}\bmod 221=136y6​=D(96+6)≡10211mod221=136y7=D(96+7)≡10311mod221=103y_7=D(96+7)\equiv 103^{11}\bmod 221=103y7​=D(96+7)≡10311mod221=103y8=D(96+8)≡10411mod221=195y_8=D(96+8)\equiv 104^{11}\bmod 221=195y8​=D(96+8)≡10411mod221=195y9=D(96+9)≡10511mod221=92‾\underline{y_9=D(96+9)\equiv 105^{11}\bmod 221=92}y9​=D(96+9)≡10511mod221=92​y10=D(96+10)≡10611mod221=98y_{10}=D(96+10)\equiv 106^{11}\bmod 221=98y10​=D(96+10)≡10611mod221=98

取素数p=109p=109p=109，计算zu≡yumodp≡yumod109,u=1,2,…,10z_u \equiv y_u \bmod p \equiv y_u\bmod 109,u=1,2,…,10zu​≡yu​modp≡yu​mod109,u=1,2,…,10得
z1≡y1mod109≡193mod109=84z_1\equiv y_1 \bmod 109\equiv 193\bmod 109=84z1​≡y1​mod109≡193mod109=84z2≡y2mod109≡106mod109=106z_2\equiv y_2 \bmod 109\equiv 106\bmod 109=106z2​≡y2​mod109≡106mod109=106z3≡y3mod109≡44mod109=44z_3\equiv y_3 \bmod 109\equiv 44\bmod 109=44z3​≡y3​mod109≡44mod109=44z4≡y4mod109≡94mod109=94z_4\equiv y_4 \bmod 109\equiv 94\bmod 109=94z4​≡y4​mod109≡94mod109=94z5≡y5mod109≡186mod109=77z_5\equiv y_5 \bmod 109\equiv 186\bmod 109=77z5​≡y5​mod109≡186mod109=77z6≡y6mod109≡136mod109=27z_6\equiv y_6 \bmod 109\equiv 136\bmod 109=27z6​≡y6​mod109≡136mod109=27z7≡y7mod109≡103mod109=103z_7\equiv y_7 \bmod 109\equiv 103\bmod 109=103z7​≡y7​mod109≡103mod109=103z8≡y8mod109≡195mod109=86z_8\equiv y_8 \bmod 109\equiv 195\bmod 109=86z8​≡y8​mod109≡195mod109=86z9≡y9mod109≡92mod109=92‾\underline{z_9\equiv y_9 \bmod 109\equiv 92\bmod 109=92}z9​≡y9​mod109≡92mod109=92​z10≡y10mod109≡98mod109=98z_{10}\equiv y_{10} \bmod 109\equiv 98\bmod 109=98z10​≡y10​mod109≡98mod109=98

BBB对数列进行验证，并将p=109p=109p=109及以下数列发送给AAAz1=84,z2=106,z3=44,z4=94,z5+1=78,z6+1=28,z7+1=104,z8+1=87,z9+1=93‾,z10+1=99z_1 = 84,z_2=106,z_3=44,z_4= 94,z_5+1= 78,z_6+1=28,z_7+1=104,z_8+1=87,\underline{z_9+1=93},z_{10}+1=99z1​=84,z2​=106,z3​=44,z4​=94,z5​+1=78,z6​+1=28,z7​+1=104,z8​+1=87,z9​+1=93​,z10​+1=99

• step4：AAA检查该数列中的第999个数是939393，由于93≠92mod10993 \neq 92\bmod 10993=92mod109，因此i>ji>ji>j，即AAA比BBB更富有。

• step5：AAA 将结果告诉 BBB。