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

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

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

具体流程： 假设富翁A的财富为a, 富翁B的财富为b

1. A生成公私钥对$(P{K}_A,S{K}_A)$。 A用公钥$P{K}_A$加密自己的财富值：$C_A=Enc(a)$，将$C_A$与公钥$P{K}_A$发送给B.
2. B随机选择下$x，y$(随机大整数)， 用A的公钥$P{K}_A$分别计算$C_{B1}=Enc(b\ast x+y)$ 和 $C_{B2}=Enc(a\ast x+y)$, 将$C_{B1}，C_{B2}$发给A, 记作$A=a\ast x+y,B=b\ast x+y$。
3. 因为Paillier加密同态属性：$E(m_1,r_1)\ast E(m_2,r_2)=E(m_1+m_2,r_1+r_2)$ 和 $E(m,r{)}^C=E(m\ast C,r\ast C)$， 所以$C_{B2}=Enc(a\ast x+y)=Enc(a{)}^x\ast Enc(y)$
4. A利用自己的私钥$S{K}_A$解开A 与 B即可得到谁更有钱。