百万富翁问题

0→∞

百万富翁问题是安全多方计算的一个著名问题，由姚期智在1982年提出：

两个百万富翁想比较一下谁更富有，但是
1 不想暴露自己的确切钱数；
2 不想让第三方知道。

在网上没找到解答,所以来请教一下诸位

无心人

似乎百万富翁还不需要这么麻烦
呵呵

改成亿万富翁更好
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
目的就是找到一个破解难度很大的加密函数
$f(n)$
使得
$n_1 <= n_2$时同时有$f(n_1) <= f(n_2)$

gxqcn

最好是再加一个不对称算法，以防第三方窃听泄密。

zgg___

我想可以用这种方法。
假设两个百万富翁分别是A和B，请一个律师C做中间人。
1、A和B在一起秘密的投币产生一个两个人公认的随机数X；
2、A和B在一起秘密的投币产生一个两个人公认的随机位K；
3、假设A的资产数为A，如果K==0，A运算得到Xa=X+A，如果K==1，A运算得到Xa=X-A；
4、B也做同样的事情；
5、A和B分别将结果Xa和Xb秘密的告诉C，并且要求C将比较大小的结果公布；
6、A和B各自依据K，得到结果。
上面的协议可能有如下的问题：
1、A、B和C必须忠实的按照流程来进行；
2、C虽然不知道具体的信息，但是，A或B如果买通了C，就可以得到对方的信息；
3、C虽然不知道比较的结果，但是C参与了过程，所以知道A和B进行了某种比较。
为了解决C的问题，可以用一台两个人都信任的计算机来完成，这样将C灭口就不会触及法律了。

0→∞

恩，就是要找那样一个函数，可是这个函数什么样呢？
zgg的方法貌似不行

mathe

zgg的方法也不是不行，只是要求有点高。必须两个百万富翁都是程序员才行。还得坐在一起同时阅读源码，亲自编译出程序，然后输入有是一个问题，最后输入不回显，两人依次输入自己的数据，输入时还要小心对方偷窥

mathe

不过无心人的方法不行。
假设我们存在一个函数$n->f(n)$,其中通过整数n计算f(n)是比较方便的，而且f(n)是单调增函数，那么对于给定的
f(n),在[0,N]之间找到n不会很难，我们只要通过二分法就可以了。先计算f(N/2),通过同f(n)比较大小就可以知道N/2同n那个大，依次下去很快就可以找到n了

shshsh_0510

姚期智不是自己说“量子加密”可以解决吗。
既然姚作为例子讲出来，估计不是三言两语能讲清楚的，还是去学学量子密码吧

无心人

关键是要有序

0→∞

找到一个答案http://www.proproco.co.uk/million.html
囧
但是。。。。。读了几行就放弃了