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$ 协议,

协议执行的过程中,满足以下性质:

  • 发送者不知道接受者要那个
  • 接受者只能成功获取需要的那个值

这张图就很灵性

https://www.bcskill.com/usr/uploads/2021/01/889740383.png


姚氏百万富翁问题 这个问题的解提供了一种 将两个信息隐藏在不同 “维度” 但只有我才能通过我们共同生成的信息中知晓问题的答案的模型

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

实际计算中表会生成四个数据

https://pic2.zhimg.com/80/v2-708979c338cccc36f0bcaaae82f6645d_1440w.jpg

Alice用这些密钥加密真值表,并将该表打乱后发送给Bob,比如Alice的输入是0,那就发$k_0$,输入是1就发 $k_1$

同时把和Bob有关的key都发给Bob

Bob根据收到的 key 对上述加密表 根据输入选择一行解密并提取出相应的kz

Bob将kz发给Alice,Alice通过对比得知计算结果是0还是1