安全多方计算之二：一文搞懂百万富翁问题

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

姚期智，1946年12月24日出生于中国上海，由于计算理论及其在密码学和量子计算中的应用方面的贡献获2000年图灵奖。2004年，当选为中国科学院外籍院士。同年，57岁的姚期智辞去普林斯顿大学终身教职，加盟清华大学高等研究中心，担任全职教授。2016年放弃美国国籍成为中国公民，正式转为中国科学院院士，加入中国科学院信息技术科学部，现任清华大学交叉信息研究院院长。

1. 解决方案

假设两个百万富翁A AA和B BB的财产在1 11到10 1010之间，A AA为4 44，B BB为9 99。

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

• A AA将盒子上锁，并按1 11到10 1010的顺序发交给B BB。
  
• B BB选择自己财产的数字对应的箱子，即第9 99个盒子，然后交个A AA。
  
• 由A AA打开盒子，共同判定结果：蓝球，因此B BB更富有。
  

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

2. 协议描述

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

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

• step1：A AA和B BB共同协商一种公钥加密体制(E EE为加密算法，D DD为解密算法)。
  
• step2：A AA随机选择一个大随机数x xx,用B的公钥加密得E ( x ) E(x)E(x)，然后将E ( x ) − i E(x)-iE(x)−i发送给B BB。
  
• step3：B BB首先计算N NN个数y u = D ( E ( x ) − i + u ) , u = 1 , 2 , . . . , N y_u=D(E(x)-i+u),u=1,2,...,Nyu=D(E(x)−i+u),u=1,2,...,N然后随机选择大素数p pp，再计算N NN个数z u ≡ y u   m o d   p , u = 1 , 2 , … , N z_u \equiv y_u \bmod p,u=1,2,…,Nzu≡yumodp,u=1,2,…,N接着验证对于所有的0 ≤ a ≠ b ≤ N − 1 0 \le a \neq b \le N-10≤a=b≤N−1是否都满足∥ z a − z b ∣ ≥ 2 \|z_a-z_b|≥2∥za−zb∣≥2，若不满足，则重新选择大素数p pp重新验证。最后，B BB将p pp及以下的N NN个数串发送给A AA:z 1 , z 2 , . . . , z j , z j + 1 + 1 , z j + 2 + 1 , … , z N + 1 z_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：设A AA收到N NN个数串的第i ii个数z i ≡ x   m o d   p z_i \equiv x \bmod pzi≡xmodp，则结论是i ≤ j i \le ji≤j；否i ≥ j i \ge ji≥j。
  
• step5：A AA 将结果告诉 B BB。
  

3. 协议说明

(1) 由于z i ≡ y i   m o d   p ≡ D ( E ( x ) − i + i ) ≡ x   m o d   p z_i \equiv y_i \bmod p \equiv D(E(x)-i+i)\equiv x \bmod pzi≡yimodp≡D(E(x)−i+i)≡xmodp，因此

当且仅当i ≤ j i\le ji≤j时,数列z 1 , z 2 , . . . , z j , z j + 1 + 1 , z j + 2 + 1 , … , z N + 1 z_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中才存在数z i ≡ x   m o d   p z_i \equiv x \bmod pzi≡xmodp；否则该数列中任何数模p pp都不与x xx同余，此时i > j i > ji>j。该步骤是协议的核心步骤，通过构造数列，实现了i ii与j jj大小的判断，类似于放置黑球与蓝球。

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

(2)要求z n z_nzn中的任何两个数z a , z b z_a,z_bza,zb满足∥ z a − z b ∣ ≥ 2 \|z_a-z_b|≥2∥za−zb∣≥2是为了保证B BB发送给A AA的N NN个数的数列z 1 , z 2 , . . . , z j , z j + 1 + 1 , z j + 2 + 1 , … , z N + 1 z_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中任意两个数不同,一般称这样的数列为“好数列”。因为若数列中存在两个数z m = z n ， m < n z_m=z_n，m<nzm=zn，m<n，则A AA可以判断出B BB的秘密数大致范围为m ≤ j < n m\le j<nm≤j<n。

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

4. 协议举例

设A AA和B BB两个百万富翁的财富，A AA的财富是900 900900万，B BB的财富是400 400400万，都不超过1000 10001000万。即A AA和B BB的秘密数分别为i = 9 i=9i=9和j = 4 j=4j=4，N = 10 N=10N=10。

• step1：A AA和B BB选定RSA公钥算法对数据加密，其中n = 221 n=221n=221，B BB的公钥35 3535，私钥11 1111。
  
• step2：A AA随机选择整数x = 92 x=92x=92，计算E ( x ) ≡ 9 2 35   m o d   221 = 105 E(x) \equiv 92^{35} \bmod 221=105E(x)≡9235mod221=105，然后把 E ( x ) − i = 105 − 9 = 96 E(x)-i=105-9=96E(x)−i=105−9=96发送给B。
  
• step3：对u = 1 , 2 , … , 10 u=1,2,…,10u=1,2,…,10，B BB分别计算y u = 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)即y 1 = D ( 96 + 1 ) ≡ 9 7 11   m o d   221 = 193 y_1=D(96+1)\equiv 97^{11}\bmod 221=193y1=D(96+1)≡9711mod221=193y 2 = D ( 96 + 2 ) ≡ 9 8 11   m o d   221 = 106 y_2=D(96+2)\equiv 98^{11}\bmod 221=106y2=D(96+2)≡9811mod221=106y 3 = D ( 96 + 3 ) ≡ 9 9 11   m o d   221 = 44 y_3=D(96+3)\equiv 99^{11}\bmod 221=44y3=D(96+3)≡9911mod221=44y 4 = D ( 96 + 4 ) ≡ 10 0 11   m o d   221 = 94 y_4=D(96+4)\equiv 100^{11}\bmod 221=94y4=D(96+4)≡10011mod221=94y 5 = D ( 96 + 5 ) ≡ 10 1 11   m o d   221 = 186 y_5=D(96+5)\equiv 101^{11}\bmod 221=186y5=D(96+5)≡10111mod221=186y 6 = D ( 96 + 6 ) ≡ 10 2 11   m o d   221 = 136 y_6=D(96+6)\equiv 102^{11}\bmod 221=136y6=D(96+6)≡10211mod221=136y 7 = D ( 96 + 7 ) ≡ 10 3 11   m o d   221 = 103 y_7=D(96+7)\equiv 103^{11}\bmod 221=103y7=D(96+7)≡10311mod221=103y 8 = D ( 96 + 8 ) ≡ 10 4 11   m o d   221 = 195 y_8=D(96+8)\equiv 104^{11}\bmod 221=195y8=D(96+8)≡10411mod221=195y 9 = D ( 96 + 9 ) ≡ 10 5 11   m o d   221 = 92 ‾ \underline{y_9=D(96+9)\equiv 105^{11}\bmod 221=92}y9=D(96+9)≡10511mod221=92y 10 = D ( 96 + 10 ) ≡ 10 6 11   m o d   221 = 98 y_{10}=D(96+10)\equiv 106^{11}\bmod 221=98y10=D(96+10)≡10611mod221=98
  

取素数p = 109 p=109p=109，计算z u ≡ y u   m o d   p ≡ y u   m o d   109 , u = 1 , 2 , … , 10 z_u \equiv y_u \bmod p \equiv y_u\bmod 109,u=1,2,…,10zu≡yumodp≡yumod109,u=1,2,…,10得

z 1 ≡ y 1   m o d   109 ≡ 193   m o d   109 = 84 z_1\equiv y_1 \bmod 109\equiv 193\bmod 109=84z1≡y1mod109≡193mod109=84z 2 ≡ y 2   m o d   109 ≡ 106   m o d   109 = 106 z_2\equiv y_2 \bmod 109\equiv 106\bmod 109=106z2≡y2mod109≡106mod109=106z 3 ≡ y 3   m o d   109 ≡ 44   m o d   109 = 44 z_3\equiv y_3 \bmod 109\equiv 44\bmod 109=44z3≡y3mod109≡44mod109=44z 4 ≡ y 4   m o d   109 ≡ 94   m o d   109 = 94 z_4\equiv y_4 \bmod 109\equiv 94\bmod 109=94z4≡y4mod109≡94mod109=94z 5 ≡ y 5   m o d   109 ≡ 186   m o d   109 = 77 z_5\equiv y_5 \bmod 109\equiv 186\bmod 109=77z5≡y5mod109≡186mod109=77z 6 ≡ y 6   m o d   109 ≡ 136   m o d   109 = 27 z_6\equiv y_6 \bmod 109\equiv 136\bmod 109=27z6≡y6mod109≡136mod109=27z 7 ≡ y 7   m o d   109 ≡ 103   m o d   109 = 103 z_7\equiv y_7 \bmod 109\equiv 103\bmod 109=103z7≡y7mod109≡103mod109=103z 8 ≡ y 8   m o d   109 ≡ 195   m o d   109 = 86 z_8\equiv y_8 \bmod 109\equiv 195\bmod 109=86z8≡y8mod109≡195mod109=86z 9 ≡ y 9   m o d   109 ≡ 92   m o d   109 = 92 ‾ \underline{z_9\equiv y_9 \bmod 109\equiv 92\bmod 109=92}z9≡y9mod109≡92mod109=92z 10 ≡ y 10   m o d   109 ≡ 98   m o d   109 = 98 z_{10}\equiv y_{10} \bmod 109\equiv 98\bmod 109=98z10≡y10mod109≡98mod109=98

B BB对数列进行验证，并将p = 109 p=109p=109及以下数列发送给A AAz 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 , z 9 + 1 = 93 ‾ , z 10 + 1 = 99 z_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：A AA检查该数列中的第9 99个数是93 9393，由于93 ≠ 92   m o d   109 93 \neq 92\bmod 10993=92mod109，因此i > j i>ji>j，即A AA比B BB更富有。
  
• step5：A AA 将结果告诉 B BB。
  

5. 协议扩展

（1）社会主义百万富翁问题

社会主义百万富翁问题是百万富翁问题的引申，描述如下：Alice有数值a aa，Bob有数值b bb，不泄漏各自任何信息的情况下得到a = b a=ba=b或a ≠ b a\neq ba=b。

（2）向量相等判定

Alice有向量A = ( a 1 , a 2 , . . . , a n ) A=(a_1,a_2,...,a_n)A=(a1,a2,...,an)，Bob有向量B = （ b 1 , b 2 , . . . , b n ) B=（b_1,b_2,...,b_n)B=（b1,b2,...,bn)，不泄漏各自任何信息的情况下得到A = B A=BA=B或A ≠ B A \neq BA=B。

（3）安全数据排序

• 安全多方单数据排序：n nn个参与方P 1 , P 2 , . . . , P n P_1,P_2,...,P_nP1,P2,...,Pn，每个持有秘密数据x i （ i = 1 , 2 , . . . , n ） x_i（i=1,2,...,n）xi（i=1,2,...,n），在P i P_iPi不泄露x i x_ixi任何信息给其他参与者的情况下，得到x i x_ixi在这些数据中的排序位置y i y_iyi。
• 安全多方多数据排序：n nn个参与方P 1 , P 2 , . . . , P n P_1,P_2,...,P_nP1,P2,...,Pn，每个持有秘密数据集X i （ i = 1 , 2 , . . . , n ) X_i（i=1,2,...,n)Xi（i=1,2,...,n)，将n nn个数据集合的并集X = X 1 ∪ X 2 , . . . , X n X=X_1\cup X_2,...,X_nX=X1∪X2,...,Xn中所有的数据按照小到大的顺序安全地排成一个序列，排序结束后，P i P_iPi能够知道X i X_iXi中的每个数在并集X XX的排序位置。