多方安全计算 SMC

百万富翁问题 姚期智院士在 1982 年提出了百万富翁问题 两位百万富翁互相都不希望透露自己的财富的具体数值,如何比较谁更富有? 这个问题成为了多方安全计算起点。 秘密共享 不经意传输(oblivious transfer) 1981 年 Michael O.Rabin 首次提出这个概念。 下面用不经意传输来解决百万富翁问题,两位富翁分别叫做张三和李四,他们的财富数值抽象为 [1, 10] 的整数。 找 10 个一模一样的箱子,按照 1 ~ 10 的序号贴上标签,张三先按照自己的财富值分别往里面放入苹果梨和香蕉,具体放法为: 如果序号小于自己的财富之,放入苹果 相等,则放入梨, 大于自己的财富值,放入香蕉; 张三把 10 个盒子都叫上锁,这一过程对李四不可见。 李四根据自己的财富值对相应序号的箱子的再加一把锁;然后把所有标签除去。这一过程对张三不可见。 这样张三不知道李四选择的是第几个箱子,李四也不知道箱子里装的是什么。 张三李四分别开锁,看里面是什么水果: 如果是苹果,张三比李四富有; 如果是梨,两人一样有钱 如果是香蕉,李四比张三富有 参考: 百万富翁问题的一个简单解释 用密码学玩暗军棋 – 闲聊多方计算 [1] Yao, Andrew C. “Protocols for secure computations....

October 28, 2021 · 1 min · lyincc