百万富翁问题

姚期智院士在 1982 年提出了百万富翁问题

两位百万富翁互相都不希望透露自己的财富的具体数值,如何比较谁更富有?

这个问题成为了多方安全计算起点。

秘密共享

不经意传输(oblivious transfer)

1981 年 Michael O.Rabin 首次提出这个概念。

下面用不经意传输来解决百万富翁问题,两位富翁分别叫做张三和李四,他们的财富数值抽象为 [1, 10] 的整数。

  1. 找 10 个一模一样的箱子,按照 1 ~ 10 的序号贴上标签,张三先按照自己的财富值分别往里面放入苹果梨和香蕉,具体放法为:
  • 如果序号小于自己的财富之,放入苹果
  • 相等,则放入梨,
  • 大于自己的财富值,放入香蕉;
  1. 张三把 10 个盒子都叫上锁,这一过程对李四不可见。

  2. 李四根据自己的财富值对相应序号的箱子的再加一把锁;然后把所有标签除去。这一过程对张三不可见。

  3. 这样张三不知道李四选择的是第几个箱子,李四也不知道箱子里装的是什么。

  4. 张三李四分别开锁,看里面是什么水果:

  • 如果是苹果,张三比李四富有;
  • 如果是梨,两人一样有钱
  • 如果是香蕉,李四比张三富有

参考:

百万富翁问题的一个简单解释

用密码学玩暗军棋 – 闲聊多方计算

[1] Yao, Andrew C. “Protocols for secure computations.” Foundations of Computer Science, 1982. SFCS'08. 23rd Annual Symposium on. IEEE, 1982.

混淆电路

同态加密

隐私信息检索

零知识检索