安全多方计算之百万富翁问题

╰半橙微兮° 2022-04-21 23:08 230阅读 0赞

# 百万富翁问题是姚期智先生在1982年提出的第一个安全双方计算问题 #

问题可以描述为：两个百万富翁街头邂逅，他们都想炫一下富，比比谁更有钱，但是出于隐私，都不想让对方知道自己到底拥有多少财富，如何在不借助第三方的情况下，让他们知道他们之间谁更有钱。

--------------------

![姚期智][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODE2NTkx_size_16_color_FFFFFF_t_70]

中国唯一图灵奖获得者，安全多方计算鼻祖。

--------------------

具体过程：

假设富翁A的财富值为a,富翁B的财富值为b

1.  A：公钥：![PK\_\{A\}][PK_A]，私钥：![SK\_\{A\}][SK_A]。用A的公钥加密财富值： ![C\_\{A\}=Enc(a)][C_A_Enc_a]  将![C\_\{A\}][C_A]与![PK\_\{A\}][PK_A]发给B
2.  B：随机选取x,y（随机大整数），用![PK\_\{A\}][PK_A]分别计算![C\_\{B1\}=Enc(a \\times x + y)][C_B1_Enc_a _times x _ y]  和 ![C\_\{B2\} = Enc(b\\times x + y)][C_B2_ _ Enc_b_times x _ y]  将![C\_\{B1\},C\_\{B2\}][C_B1_C_B2]发给A，记 ![A=a\\times x +y][A_a_times x _y],![B=b \\times x+y][B_b _times x_y]。
3.  因为paillier加密同态属性：![E(m\_\{1\},r\_\{1\}) \\times E(m\_\{2\},r\_\{2\}) = E(m\_\{1\}+m\_\{2\},r\_\{1\}+r\_\{2\})][E_m_1_r_1_ _times E_m_2_r_2_ _ E_m_1_m_2_r_1_r_2] 和 ![E(m,r)^C = E(m\\times C,r \\times C)][E_m_r_C _ E_m_times C_r _times C]
4.  所以：![C\_\{B1\} = Enc(a\\times x + y) =Enc(a)^x \\times Enc(y)][C_B1_ _ Enc_a_times x _ y_ _Enc_a_x _times Enc_y]
5.  A：利用自己的私钥![SK\_\{A\}][SK_A]解开 A与B 即得到：谁更有钱

--------------------

具体演示（点击下图进入全屏）：

![百万富翁][20181031200250817.gif]

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODE2NTkx_size_16_color_FFFFFF_t_70]: /images/20220422/7dc6bf88dc5148f68e436c7895df24c7.png
[PK_A]: https://private.codecogs.com/gif.latex?PK_%7BA%7D
[SK_A]: https://private.codecogs.com/gif.latex?SK_%7BA%7D
[C_A_Enc_a]: https://private.codecogs.com/gif.latex?C_%7BA%7D%3DEnc%28a%29
[C_A]: https://private.codecogs.com/gif.latex?C_%7BA%7D
[C_B1_Enc_a _times x _ y]: https://private.codecogs.com/gif.latex?C_%7BB1%7D%3DEnc%28a%20%5Ctimes%20x%20&plus;%20y%29
[C_B2_ _ Enc_b_times x _ y]: https://private.codecogs.com/gif.latex?C_%7BB2%7D%20%3D%20Enc%28b%5Ctimes%20x%20&plus;%20y%29
[C_B1_C_B2]: https://private.codecogs.com/gif.latex?C_%7BB1%7D%2CC_%7BB2%7D
[A_a_times x _y]: https://private.codecogs.com/gif.latex?A%3Da%5Ctimes%20x%20&plus;y
[B_b _times x_y]: https://private.codecogs.com/gif.latex?B%3Db%20%5Ctimes%20x&plus;y
[E_m_1_r_1_ _times E_m_2_r_2_ _ E_m_1_m_2_r_1_r_2]: https://private.codecogs.com/gif.latex?E%28m_%7B1%7D%2Cr_%7B1%7D%29%20%5Ctimes%20E%28m_%7B2%7D%2Cr_%7B2%7D%29%20%3D%20E%28m_%7B1%7D&plus;m_%7B2%7D%2Cr_%7B1%7D&plus;r_%7B2%7D%29
[E_m_r_C _ E_m_times C_r _times C]: https://private.codecogs.com/gif.latex?E%28m%2Cr%29%5EC%20%3D%20E%28m%5Ctimes%20C%2Cr%20%5Ctimes%20C%29
[C_B1_ _ Enc_a_times x _ y_ _Enc_a_x _times Enc_y]: https://private.codecogs.com/gif.latex?C_%7BB1%7D%20%3D%20Enc%28a%5Ctimes%20x%20&plus;%20y%29%20%3DEnc%28a%29%5Ex%20%5Ctimes%20Enc%28y%29
[20181031200250817.gif]: /images/20220422/0eb1ee132069473aba6e7614e61c4d5a.png