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

时间 2019-12-11 标签安全多方计算百万富翁问题

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

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

中国惟一图灵奖得到者，安全多方计算鼻祖。加密

具体过程：code

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

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 即获得：谁更有钱

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