百万富翁问题
两个百万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让对方及其他第三方知道自己财富的任何信息，这是由中国计算机科学家、2000年图灵奖获得者姚启智教授于1982年在论文《Protocols for secure computations》中提出的姚氏百万富翁问题，开创了密码学研究的新领域：安全多方计算(Secure Multi-party Computation)。
姚期智，1946年12月24日出生于中国上海，由于计算理论及其在密码学和量子计算中的应用方面的贡献获2000年图灵奖。2004年，当选为中国科学院外籍院士。同年，57岁的姚期智辞去普林斯顿大学终身教职，加盟清华大学高等研究中心，担任全职教授。2016年放弃美国国籍成为中国公民，正式转为中国科学院院士，加入中国科学院信息技术科学部，现任清华大学交叉信息研究院院长。
1. 解决方案
假设两个百万富翁
A
A
A和
B
B
B的财产在
1
1
1到
10
10
10之间，
A
A
A为
4
4
4，
B
B
B为
9
9
9。
A A A选择 10 10 10个相同的个盒子，按照顺序代表 1 1 1到 10 10 10：A A A用自己财产的数字与盒子的数字进行比较，如果小于该数字，则放一个黑球，若大于等于则放一个蓝球。
A A A将盒子上锁，并按 1 1 1到 10 10 10的顺序发交给 B B B。B B B选择自己财产的数字对应的箱子，即第 9 9 9个盒子，然后交个 A A A。- 由 A A A打开盒子，共同判定结果：蓝球，因此 B B B更富有。
现实中，上述方案一般通过密码学工具实现。
2. 协议描述
姚氏百万富翁问题可形式化描述为:对两个秘密输入
i
i
i和
j
j
j，判断函数值
f
(
i
,
j
)
=
i
−
j
≤
0
f(i,j)=i-j\le 0
f(i,j)=i−j≤0还是
f
(
i
,
j
)
=
i
−
j
≥
0
f(i,j)=i-j\ge 0
f(i,j)=i−j≥0。
假定
1
≤
i
,
j
≤
N
1 \le i,j \le N
1≤i,j≤N。为了在不让任何第三方参与的情况下比较
i
i
i和
j
j
j的大小，又不向对方泄漏各自的数值，则可执行如下的协议:
- step1： A A A和 B B B共同协商一种公钥加密体制( E E E为加密算法， D D D为解密算法)。
- step2： A A A随机选择一个大随机数 x x x,用B的公钥加密得 E ( x ) E(x) E(x)，然后将 E ( x ) − i E(x)-i E(x)−i发送给 B B B。
- step3： B B B首先计算 N N N个数 y u = D ( E ( x ) − i + u ) , u = 1 , 2 , . . . , N y_u=D(E(x)-i+u),u=1,2,...,N yu=D(E(x)−i+u),u=1,2,...,N然后随机选择大素数 p p p，再计算 N N N个数 z u ≡ y u m o d p , u = 1 , 2 , … , N z_u \equiv y_u \bmod p,u=1,2,…,N zu≡yumodp,u=1,2,…,N接着验证对于所有的 0 ≤ a ≠ b ≤ N − 1 0 \le a \neq b \le N-1 0≤a=b≤N−1是否都满足 ∥ z a − z b ∣ ≥ 2 |z_a-z_b|≥2 ∥za−zb∣≥2，若不满足，则重新选择大素数 p p p重新验证。最后， B B B将 p p p及以下的 N N N个数串发送给 A A A: 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+1 z1,z2,...,zj,zj+1+1,zj+2+1,…,zN+1.- step4：设 A A A收到 N N N个数串的第 i i i个数 z i ≡ x m o d p z_i \equiv x \bmod p zi≡xmodp，则结论是 i ≤ j i \le j i≤j；否 i ≥ j i \ge j i≥j。
- step5： A A A 将结果告诉 B B B。
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 p
zi≡yimodp≡D(E(x)−i+i)≡xmodp，因此
当且仅当
i
≤
j
i\le j
i≤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+1
z1,z2,...,zj,zj+1+1,zj+2+1,…,zN+1中才存在数
z
i
≡
x
m
o
d
p
z_i \equiv x \bmod p
zi≡xmodp；否则该数列中任何数模
p
p
p都不与
x
x
x同余，此时
i
>
j
i > j
i>j。该步骤是协议的核心步骤，通过构造数列，实现了
i
i
i与
j
j
j大小的判断，类似于放置黑球与蓝球。
**但该协议无法判断出
i
=
j
i=j
i=j的情况，是该协议的一个缺点，后续相关研究对此进行了改进**。
(2)要求
z
n
z_n
zn中的任何两个数
z
a
,
z
b
z_a,z_b
za,zb满足
∥
z
a
−
z
b
∣
≥
2
\|z_a-z_b|≥2
∥za−zb∣≥2是为了保证
B
B
B发送给
A
A
A的
N
N
N个数的数列
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+1
z1,z2,...,zj,zj+1+1,zj+2+1,…,zN+1中任意两个数不同,一般称这样的数列为“好数列”。因为若数列中存在两个数
z
m
=
z
n
，
m
<
n
z_m=z_n，m<n
zm=zn，m<n，则
A
A
A可以判断出
B
B
B的秘密数大致范围为
m
≤
j
<
n
m\le j<n
m≤j<n。
（3）
A
A
A比
B
B
B先知晓了最终的结果，若
A
A
A欺骗
B
B
B告诉他相反的结论，则该协议是不公平的。为增加公平性,
B
B
B可以要求与
A
A
A交换角色，即原来
A
A
A执行的步骤现由
B
B
B执行，而由
B
B
B执行的步骤改由
A
A
A执行。这样
B
B
B也可以首先得出结论。
4. 协议举例
设
A
A
A和
B
B
B两个百万富翁的财富，
A
A
A的财富是
900
900
900万，
B
B
B的财富是
400
400
400万，都不超过
1000
1000
1000万。即
A
A
A和
B
B
B的秘密数分别为
i
=
9
i=9
i=9和
j
=
4
j=4
j=4，
N
=
10
N=10
N=10。
- step1： A A A和 B B B选定RSA公钥算法对数据加密，其中 n = 221 n=221 n=221， B B B的公钥 35 35 35，私钥 11 11 11。
- step2： A A A随机选择整数 x = 92 x=92 x=92，计算 E ( x ) ≡ 9 2 35 m o d 221 = 105 E(x) \equiv 92^{35} \bmod 221=105 E(x)≡9235mod221=105，然后把 E ( x ) − i = 105 − 9 = 96 E(x)-i=105-9=96 E(x)−i=105−9=96发送给B。
- step3：对 u = 1 , 2 , … , 10 u=1,2,…,10 u=1,2,…,10， B B B分别计算 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=193 y1=D(96+1)≡9711mod221=193 y 2 = D ( 96 + 2 ) ≡ 9 8 11 m o d 221 = 106 y_2=D(96+2)\equiv 98^{11}\bmod 221=106 y2=D(96+2)≡9811mod221=106 y 3 = D ( 96 + 3 ) ≡ 9 9 11 m o d 221 = 44 y_3=D(96+3)\equiv 99^{11}\bmod 221=44 y3=D(96+3)≡9911mod221=44 y 4 = D ( 96 + 4 ) ≡ 10 0 11 m o d 221 = 94 y_4=D(96+4)\equiv 100^{11}\bmod 221=94 y4=D(96+4)≡10011mod221=94 y 5 = D ( 96 + 5 ) ≡ 10 1 11 m o d 221 = 186 y_5=D(96+5)\equiv 101^{11}\bmod 221=186 y5=D(96+5)≡10111mod221=186 y 6 = D ( 96 + 6 ) ≡ 10 2 11 m o d 221 = 136 y_6=D(96+6)\equiv 102^{11}\bmod 221=136 y6=D(96+6)≡10211mod221=136 y 7 = D ( 96 + 7 ) ≡ 10 3 11 m o d 221 = 103 y_7=D(96+7)\equiv 103^{11}\bmod 221=103 y7=D(96+7)≡10311mod221=103 y 8 = D ( 96 + 8 ) ≡ 10 4 11 m o d 221 = 195 y_8=D(96+8)\equiv 104^{11}\bmod 221=195 y8=D(96+8)≡10411mod221=195 y 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=92 y 10 = D ( 96 + 10 ) ≡ 10 6 11 m o d 221 = 98 y_{10}=D(96+10)\equiv 106^{11}\bmod 221=98 y10=D(96+10)≡10611mod221=98
取素数
p
=
109
p=109
p=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,…,10
zu≡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=84
z1≡y1mod109≡193mod109=84
z
2
≡
y
2
m
o
d
109
≡
106
m
o
d
109
=
106
z_2\equiv y_2 \bmod 109\equiv 106\bmod 109=106
z2≡y2mod109≡106mod109=106
z
3
≡
y
3
m
o
d
109
≡
44
m
o
d
109
=
44
z_3\equiv y_3 \bmod 109\equiv 44\bmod 109=44
z3≡y3mod109≡44mod109=44
z
4
≡
y
4
m
o
d
109
≡
94
m
o
d
109
=
94
z_4\equiv y_4 \bmod 109\equiv 94\bmod 109=94
z4≡y4mod109≡94mod109=94
z
5
≡
y
5
m
o
d
109
≡
186
m
o
d
109
=
77
z_5\equiv y_5 \bmod 109\equiv 186\bmod 109=77
z5≡y5mod109≡186mod109=77
z
6
≡
y
6
m
o
d
109
≡
136
m
o
d
109
=
27
z_6\equiv y_6 \bmod 109\equiv 136\bmod 109=27
z6≡y6mod109≡136mod109=27
z
7
≡
y
7
m
o
d
109
≡
103
m
o
d
109
=
103
z_7\equiv y_7 \bmod 109\equiv 103\bmod 109=103
z7≡y7mod109≡103mod109=103
z
8
≡
y
8
m
o
d
109
≡
195
m
o
d
109
=
86
z_8\equiv y_8 \bmod 109\equiv 195\bmod 109=86
z8≡y8mod109≡195mod109=86
z
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=92
z
10
≡
y
10
m
o
d
109
≡
98
m
o
d
109
=
98
z_{10}\equiv y_{10} \bmod 109\equiv 98\bmod 109=98
z10≡y10mod109≡98mod109=98
B
B
B对数列进行验证，并将
p
=
109
p=109
p=109及以下数列发送给
A
A
A
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
,
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=99
z1=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 A A检查该数列中的第 9 9 9个数是 93 93 93，由于 93 ≠ 92 m o d 109 93 \neq 92\bmod 109 93=92mod109，因此 i > j i>j i>j，即 A A A比 B B B更富有。
- step5： A A A 将结果告诉 B B B。
5. 协议扩展
（1）社会主义百万富翁问题
社会主义百万富翁问题是百万富翁问题的引申，描述如下：Alice有数值
a
a
a，Bob有数值
b
b
b，不泄漏各自任何信息的情况下得到
a
=
b
a=b
a=b或
a
≠
b
a\neq b
a=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=B
A=B或
A
≠
B
A \neq B
A=B。
（3）安全数据排序
- 安全多方单数据排序： n n n个参与方 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1,P2,...,Pn，每个持有秘密数据 x i （ i = 1 , 2 , . . . , n ） x_i（i=1,2,...,n） xi（i=1,2,...,n），在 P i P_i Pi不泄露 x i x_i xi任何信息给其他参与者的情况下，得到 x i x_i xi在这些数据中的排序位置 y i y_i yi。
- 安全多方多数据排序： n n n个参与方 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1,P2,...,Pn，每个持有秘密数据集 X i （ i = 1 , 2 , . . . , n ) X_i（i=1,2,...,n) Xi（i=1,2,...,n)，将 n n n个数据集合的并集 X = X 1 ∪ X 2 , . . . , X n X=X_1\cup X_2,...,X_n X=X1∪X2,...,Xn中所有的数据按照小到大的顺序安全地排成一个序列，排序结束后， P i P_i Pi能够知道 X i X_i Xi中的每个数在并集 X X X的排序位置。
本文转载自: https://blog.csdn.net/apr15/article/details/128348229
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。