又一个好玩的东西
Table of Contents
安全多方计算 #
很重要的老东西了，但应用范围极其广泛，作为科普学习一下蛮好的
安全的分布式计算 MPC (Secure multi-party computation)指的是用户在无需进行数据归集的情况下，完成数据协同计算，同时保护数据所有方的原始数据隐私。具体来说，有n个计算参与方，分别持有私有数据$x_1,x_2x_3,..x_i,$共同计算既定函数$f(x_1…x_n)=y$
混淆电路（Garbled Circuit) #
前提知识 #
Garbled Circuit是MPC的一种实现方式，由姚期智先生提出（那是真滴牛批），通俗的说，就是一堆人各自拥有其隐私数据，他们想把这些数据合起来算点什么，但又不想把数据交给别人，混淆电路解决的就是此类问题。
Oblivious Transfer 不经意传输 #
Oblivious Transfer，中文称为不经意传输，通常简写为OT
它指的是发送者从一个值集合中向接收者发送单个值的问题，这里发送者无法知道发送的是哪一个值，而且接收者也不能获知除了接收值之外的其它任何值。
发送者有由N个值组成的集合，接收者有 $i$ 协议执行完成,接收者只知道 $i$ 协议,且发送者不知道 $i$ 协议,
协议执行的过程中，满足以下性质：
- 发送者不知道接受者要那个
- 接受者只能成功获取需要的那个值
这张图就很灵性
姚氏百万富翁问题 这个问题的解提供了一种 将两个信息隐藏在不同 “维度” 但只有我才能通过我们共同生成的信息中知晓问题的答案的模型
MPC的中心思想，那就是彼此把数据x，y藏在自己的维度上，然后找到一个交点，就是我们需要共同计算的函数f（x，y）。Yao的姚氏百万富翁问题仅限于比较大小，即一个布尔值的计算。
当然后来一个在此基础上一个更加伟大的密码学算法被发明出来了，那就混淆电路。它把这个交点扩展到任何电脑可计算的函数，从此不管是比较大小，还是复杂到神经网络，都可以用类似的方法计算了。
应用 #
应用到计算机上的例子可以理解为我有一个 and 门 两个输入一个输出
table
| x | y | z |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
加密这些真值表将电路转换成加密电路Garbled Circuit
这里table每一个位置的每一种值都对应了一个key
假设实例table
| x | y | z |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
实际计算中表会生成四个数据
Alice用这些密钥加密真值表，并将该表打乱后发送给Bob，比如Alice的输入是0，那就发$k_0$，输入是1就发 $k_1$
同时把和Bob有关的key都发给Bob
Bob根据收到的 key 对上述加密表 根据输入选择一行解密并提取出相应的kz
Bob将kz发给Alice，Alice通过对比得知计算结果是0还是1