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

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

姚期智

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

具体过程：

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

A：公钥： $PK_{A}$ ，私钥： $SK_{A}$ 。用A的公钥加密财富值： $C_{A}=Enc(a)$ 将 $C_{A}$ 与 $PK_{A}$ 发给B
B：随机选取x,y（随机大整数），用 $PK_{A}$ 分别计算 $C_{B1}=Enc(a \times x + y)$ 和 $C_{B2} = Enc(b\times x + y)$ 将 $C_{B1},C_{B2}$ 发给A，记 $A=a\times x +y$ , $B=b \times x+y$ 。
因为paillier加密同态属性： $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)$
所以： $C_{B1} = Enc(a\times x + y) =Enc(a)^x \times Enc(y)$
A：利用自己的私钥 $SK_{A}$ 解开 A与B 即得到：谁更有钱

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

百万富翁

更多精彩内容