安全多方计算MPC的若干个概念

安全多方计算（MPC）与可信计算环境（TEE），联邦学习（Federated Learning）是隐私计算领域的三个重要实现方式。

参考资料：

A Pragmatic Introduction to Secure Multi-Party Computation

1. 不经意传输（OT，Oblivious Transfer）

目标如下：

Sender提供可选参数(m0, m1)，但是不知道Receiver具体选择哪个。
Receiver可以选择其中一个，但是不知道除此之外的其他参数值。例如，选择m0后，无法得知m1的值。

参考资料：

混淆电路介绍（一）不经意传输
 Oblivious Transfer (OT)

2. 混淆电路（GC，Garbled Circuit）

将计算逻辑转换成门电路，以与门为例，流程如下

A生成x为0，1对应的密钥kx0,kx1, y为0，1时对应的密钥ky0,ky1，并且计算如下真值表(z为两次对称加密值)
A将真值表打乱行顺序。假设A输入x=0，将对应的kx0和真值表发送给B。因为顺序乱，所以这样B无法从行排列中推测出kx0对应的A的输入是x=0还是x=1，即B无法得知A的输入。
假设B选择y=1,通过OT协议获取ky1（无法得知ky0），此时A也无法得知B的输入。
B通过对真值表里的z进行解密（此时B只有kx0和ky1），选择对E_kx0(E_ky1(0))进行解密，也就是最终结果0，即x=0，y=1时的结果。

x	y	z
kx0	ky0	E_kx0(E_ky0(0))
kx0	ky1	E_kx0(E_ky1(0))
kx1	ky0	E_kx1(E_ky0(0))
kx1	ky1	E_kx1(E_ky1(1))

表1: 加密真值表

秘密共享通过把秘密进行分割，并把秘密在n个参与者中分享，使得只有多于特定t个参与者合作才可以计算出或是恢复秘密，而少于t个参与者则不可以得到有关秘密。实现方式例如：

构造t-1次多项式 f(x) = s + a₁·x + … + a_t-1 · x^t-1。其中，s为分享的秘密
计算f(x1), f(x2), …, f(xn)，分别分发给参与方P1, …, Pn。此时任意至少t个P组合在一起可通过拉格朗日插值法计算f(x),也就得到秘密s。

在布尔电路上，可将异或门和与门分别看成在有限域上 F₂ 的加法和乘法。将异或用模为 2 的加法进行计算，与用模为 2 的乘法进行计算。BGW协议基于Shamir秘密分享方案实现加法/乘法特性。

参考资料：

How to Share a Secret - Adi Shamir

4. 差分隐私(DP, Differential Privacy)

中心思想：无法从结果中反推出单个输入个体的信息。
临近数据集：指的是两个数据集D1，D2只有单个记录不一致。例如，D1={1, 0, 1}, D1={1, 0, 1, 1}。数据操作是count，则count(D1)=2, count(D2)=2, 则可以反推出最后一个输入为1。主要通过两种方式添加噪声，一是根据数据敏感的数值型（服从拉普拉斯分布的随机噪声），二是离散值(指数分布)。添加的噪声分类如下：

输入噪声： f(x0, x1, …, xn, c) -> f(x0, x1, …, xn + noice, c)
参数噪声： f(x0, x1, …, xn, c) -> f(x0, x1, …, xn, c + noice)
输出噪声： f(x0, x1, …, xn, c) -> f(x0, x1, …, xn, c) + noice

1. 不经意传输（OT，Oblivious Transfer）

2. 混淆电路（GC，Garbled Circuit）

3. 秘密共享(SS, Secret-Sharing)

4. 差分隐私(DP, Differential Privacy)