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

百万富翁问题—安全多方计算
是由图灵奖获得者姚期智提出的。

有A、B两个富翁，A资产i亿元，B资产j亿元，i、j均在0-10范围内，在互不让对方知道自己资产的情况下，比较A和B的资产谁多谁少。
那么如何去比较呢？
这里放十个箱子：

如果A有i亿元，那么A将第i个箱子之前的所有箱子里都放个纸条，写着0；从第i个箱子开始，写1，一直写到最后一个箱子。写完后将十个箱子全部锁上。由于B没有钥匙，所以打不开箱子，因此看不到纸条，不知道A的资产。

于是B将自己资产对应的那个箱子拿出来给A，然后B将剩下的箱子全部销毁，于是A也不知道B给他的是第几个箱子，但是能打开这个箱子。
如果箱子里纸条是0，则A的资产>B的资产；
如果箱子里纸条是1，则A的资产<=B的资产。

以上就是百万富翁问题，那么如何用密码学来解决这个问题呢？

上述问题中的锁代表公钥，钥匙代表私钥。

具体方案：
1、B无私钥，只有公钥。
1-B先选一个大数X，然后用公钥对X加密-> E(X)=k；

2-B计算k-j+1=m，然后B将m发送给A，虽然在m中包含了B的资产j，但是A不知道k，所以无法获取具体值。

2、A有公私钥。
1-计算k-j+1, k-j+2, k-j+3……k-j+10。在这之中，必有一个数据是k-j+j，即k。

2-解密这十个值，得出解密结果：Yu=D(k-j+u) —y1,y2,y3……yj……y10
这个yj即D(k)，即B选择的大数X。但是A不知道哪个是j，所以还是无法知晓B的资产。

3-求模
Zu=Yu mod p, p为质数
得出z1…zj…z10

4-A要将自己的资产i融入zu数列
那么如何融入？：
保持z1,z2…zi不变，让zi+1,zi+2…z10加1，然后将Z数列传给B。

3、B检验
若X mod p =Zj，说明Zj没有经过加1的步骤，即Zj在Zi之前，j<=i
若X mod p不等于Zj，说明Zj加1了，Zj在Zi之后，j>i

这里j与i的等号与最初提的百万富翁例子中的等号不同，因为这里是前i为0，i+1至10为1，之前例子是前i-1为0，i至10为1.

以上就是如何用密码学实现百万富翁问题，这也就是安全多方计算。在实际应用中，一定不是10这个范围，是一个无法推导出的范围。