百万富翁问题

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 囧 但是。。。。。读了几行就放弃了