GMW (A Generic MPC Protocol)

假设只有两个参与者 \(P_1\) 和 \(P_2\) 。 \(P_1\) 手头有两个 Input Shares \(c_1, d_1\) ， \(P_2\) 手头有两个 Input Shares \(c_2, d_2\) 。我们的目的是设计一种方案让 \(P_1\) 得到 \(b_1\) ，让 \(P_2\) 得到 \(b_2\) ，且它们要满足 \(\sum b_i = (\sum c_i )( \sum d_i)\) 。

AND Gate 的输出 \[\begin{aligned} c d & = (c_1 + c_2) (d_1 + d_2) \\ & = \underbrace{c_1 d_1}_{P_1 \text{可以本地计算}} + \underbrace{c_1 d_2 + c_2 d_1}_{P_1 \text{和} P_2 \text{交换信息才能完成计算}} + \underbrace{ c_2 d_2}_{P_2 \text{可以本地计算}} \\ \end{aligned}\]

我们不能简单地定义 \(b_1 \triangleq c_1 d_1 + c_1 d_2\) 和 \(b_2 \triangleq c_2 d_1 + c_2 d_2\) ，因为 \(P_1\) 手里并没有 \(d_2\) ，同样 \(P_2\) 手里也没有 \(d_1\) 。 如果 \(P_1\) 把 \(d_1\) 告诉 \(P_2\) ，而 \(P_2\) 把 \(d_2\) 告诉 \(P_1\) 这样可行吗？这是不行的，因为这不能保证 \(d\) 的隐私，\(P_1\) 和 \(P_2\) 通过 \(d = d_1 + d_2\) 就可知道 \(d\) 了。

下面介绍使用 1-out-of-4 OT 协议来拆分 \(c_1 d_2 + c_2 d_1\) 为两个部分之和，使得 \(P_1,P_2\) 分别可计算其它的一部分且不泄露各自的隐私。假设 \(P_1\) 作为 1-out-of-4 OT 协议的 sender， \(P_2\) 作为 1-out-of-4 OT 协议的 receiver。

首先 \(P_1\) 定义下面 4 个式子 \[\begin{aligned} S(0,0) & \triangleq (c_1 \cdot 0) + (0 \cdot d_1) \\ S(0,1) & \triangleq (c_1 \cdot 0) + (1 \cdot d_1) \\ S(1,0) & \triangleq (c_1 \cdot 1) + (0 \cdot d_1) \\ S(1,1) & \triangleq (c_1 \cdot 1) + (1 \cdot d_1) \end{aligned}\]

\(P_1\) 选择一个随机比特 \(r \in \{0, 1\}\) ， \(P_1\) 准备好 1-out-of-4 OT 协议的 4 个值 \[\begin{aligned} m_{0,0} \triangleq r + S(0,0) \\ m_{0,1} \triangleq r + S(0,1) \\ m_{1,0} \triangleq r + S(1,0) \\ m_{1,1} \triangleq r + S(1,1) \\ \end{aligned}\]

\(P_1\) 把上面 4 个值发送给 \(P_2\) 。 \(P_2\) 从中选择 \(m_{c_2,d_2}\) ，具体来说就是，如果 \(c_2=0,d_2=0\) ，则 \(P_2\) 选择 \(m_{0,0}\) ，如果 \(c_2=0,d_2=1\) ，则 \(P_2\) 选择 \(m_{0,1}\) ，如果 \(c_2=1,d_2=0\) ，则 \(P_2\) 选择 \(m_{1,0}\) ，如果 \(c_2=1,d_2=1\) ，则 \(P_2\) 选择 \(m_{1,1}\) 。

定义 \[\begin{aligned} b_1 & \triangleq c_1 d_1 + r \\ b_2 & \triangleq c_2 d_2 + m_{c_2,d_2} \end{aligned}\] \(P_1\) 计算 \(b_1\) 时只用使用他手头的 Input Shares \(c_1, d_1\) ， \(P_2\) 计算 \(b_2\) 时也只用使用他手头的 Input Shares \(c_2, d_2\) 。

下面我们来验证一下 \(b_1 + b_2 = (c_1 + c_2)(d_1 + d_2)\) 是否成立。

\[\begin{aligned} b_1 + b_2 &= c_1d_1 + r + c_2d_2 + m_{c_2,d_2} \pmod 2\\ &= c_1d_1 + r + c_2d_2 + r + S(c_2,d_2) \pmod 2\\ &= c_1d_1 + c_2d_2 + S(c_2,d_2) \pmod 2\\ \end{aligned}\]

1. 当 \(c_2=0,d_2=0\) 时，上式为 \(c_1d_1 + c_2d_2 = c_1d_1\) ，而直接计算 \((c_1 + c_2)(d_1 + d_2)\) 也是这个值。
   
2. 当 \(c_2=0,d_2=1\) 时，上式为 \(c_1d_1 + c_2d_2 + d_1 = c_1d_1 + d_1\) ，而直接计算 \((c_1 + c_2)(d_1 + d_2)\) 也是这个值；
   
3. 当 \(c_2=1,d_2=0\) 时，上式为 \(c_1d_1 + c_2d_2 + c_1 = c_1d_1 + c_1\) ，而直接计算 \((c_1 + c_2)(d_1 + d_2)\) 也是这个值；
   
4. 当 \(c_2=1,d_2=1\) 时，上式为 \(c_1d_1 + c_2d_2 + c_1 + d_1 = c_1d_1 + 1 + c_1 + d_1\) ，而直接计算 \((c_1 + c_2)(d_1 + d_2)\) 也是这个值；
   

从而 \(b_1 + b_2 = (c_1 + c_2)(d_1 + d_2)\) 总是成立。

\(P_1\) 和 \(P_2\) 计算 \(b_1,b_2\) 的过程可总结为图 5 所示，其中左子图是利用 1-out-of-4 OT 拆分 \(c_1 d_2 + c_2 d_1\) 为两个部分（ \(r\) 和 \(m_{c_2,d_2}\) ）之和。

前面介绍的是 Two-Party 的情况，容易扩展为 N-Party 的通用情况。下面以 4 个 Party 为例介绍一下 N-Party 时的思路。

假设有 4 个参与者 \(P_1,P_2,P_3,P_4\) 。经过第 1 步（即 Input-sharing Phase）后， \(P_1\) 手头有两个 Input Shares \(c_1, d_1\) ， \(P_2\) 手头有两个 Input Shares \(c_2, d_2\) ， \(P_3\) 手头有两个 Input Shares \(c_3, d_3\) ， \(P_4\) 手头有两个 Input Shares \(c_4, d_4\) 。我们的目的是设计一种方案让 \(P_1,P_2,P_3,P_4\) 分别得到 \(b_1,b_2,b_3,b_4\) ，且它们要满足 \(\sum b_i = (\sum c_i )(\sum d_i)\) 。

\[\begin{aligned} cd =& (c_1 + c_2 + c_3 + c_4)(d_1 + d_2 + d_3 + d_4) \\ =& c_1 d_1 + {\color{red}{c_1 d_2}} + {\color{blue}{c_1 d_3}} + {\color{green}{c_1 d_4}}\\ & {\color{red}{c_2 d_1}} + c_2 d_2 + {\color{magenta}{c_2 d_3}} + {\color{brown}{c_2 d_4}}\\ & {\color{blue}{c_3 d_1}} + {\color{magenta}{c_3 d_2}} + c_3 d_3 + {\color{purple}{c_3 d_4}}\\ & {\color{green}{c_4 d_1}} + {\color{brown}{c_4 d_2}} + {\color{purple}{c_4 d_3}} + c_4 d_4\\ \end{aligned}\]

其中 \(c_1 d_1\) 可由 \(P_1\) 本地计算， \(c_2 d_2\) 可由 \(P_2\) 本地计算， \(c_3 d_3\) 可由 \(P_3\) 本地计算， \(c_4 d_4\) 可由 \(P_4\) 本地计算。

任意两个参与者 \(P_i,P_j\) 之间进行 1-out-of-4 OT 协议交换信息（和上一节介绍的相同）。 比如红色部分 \(c_1 d_2 + c_2 d_1\) 由 \(P_1,P_2\) 进行一次 1-out-of-4 OT 协议可拆分为两个部分之和， \(P_1,P_2\) 各取一部分（如 \(r^{P_1,P_2}, m^{P_1,P_2}_{c_2,d_2}\) ）；蓝色部分 \(c_1 d_3 + c_3 d_1\) 由 \(P_1,P_3\) 进行一次 1-out-of-4 OT 协议可拆分为两个部分之和， \(P_1,P_3\) 各取一部分（如 \(r^{P_1,P_3}, m^{P_1,P_3}_{c_3,d_3}\) ）；绿色部分 \(c_1 d_4 + c_4 d_1\) 由 \(P_1,P_4\) 进行一次 1-out-of-4 OT 协议可拆分为两个部分之和， \(P_1,P_4\) 各取一部分（如 \(r^{P_1,P_4}, m^{P_1,P_4}_{c_4,d_4}\) ）；其它类似。4 个参与者执行一个 AND Gate 一共要进行 6 次 1-out-of-4 OT 协议。

这样， \(P_1,P_2,P_3,P_4\) 的 Output Share 可分别定义为 \[\begin{aligned} b_1 & \triangleq c_1 d_1 + r^{P_1,P_2} + r^{P_1,P_3} + r^{P_1,P_4} \pmod 2\\ b_2 & \triangleq m^{P_1,P_2}_{c_2,d_2} + c_2 d_2 + r^{P_2,P_3} + r^{P_2,P_4} \pmod 2\\ b_3 & \triangleq m^{P_1,P_3}_{c_3,d_3} + m^{P_2,P_3}_{c_3,d_3} + c_3 d_3 + r^{P_3,P_4}\pmod 2\\ b_4 & \triangleq m^{P_1,P_4}_{c_4,d_4} + m^{P_2,P_4}_{c_4,d_4} + m^{P_3,P_4}_{c_4,d_4} + c_4 d_4 \pmod 2 \end{aligned}\]

这些 Output Share 加起来会为 \(cd\) 。

当参与者个数为其它数时，情况也类似，不再介绍。