# 正文

GMW 协议最早是在论文 How to play any mental game 中由 Goldreich, Micali 和 Wigderson 提出。这是一个可以在算术电路和布尔电路中实现的安全计算协议，也可以比较容易地拓展到多方安全计算的领域。

在 2PC 的场景下，我们假设存在两个安全计算的参与方$P_1,P_2$，他们各自持有一个秘密输入$x,y$。一个需要计算的函数$\mathcal{F}(x,y)$，对应了一个布尔电路$\mathcal C$。

首先，参与方$P_1$ 对于自己秘密$x\in\{0,1\}^n$ 中的每一个比特$x_i$，都选择一个随机比特掩码$r_i\in_R\{0,1\}$，计算$x_i\oplus r_i$ 作为自己的新秘密比特，接下来，参与方$P_1$ 将自己的掩码比特$r_i,i\in\{1,2,...,n\}$ 发送给参与方$P_2$。

同样的，$P_2$ 也进行了类似的操作，选取随机比特掩码$r'$ 对自己的秘密$y$ 进行异或并将结果作为新的秘密，同时将选取的随机比特掩码发送给参与方$P_1$。

经过了上面这样的过程，两个参与方$P_1,P_2$ 相当于和对方进行了秘密共享 —— 只有同时得到参与方$P_1$ 的秘密份额$x_i\oplus r_i$ 和参与方拥有的秘密份额$r_i$ 才能够还原秘密比特$x_i$。

接下来，双方共同计算布尔电路$\mathcal C$。

对于电路中某个门电路的输入，在先前的混淆电路中，双方是通过乱码表来实现计算。我们假设一个门电路的输入导线$w_i,w_j$ 由双方分别持有，导线对应的取值可以是 0 或 1，那么这里就需要构造一个乱码表，并且通过标识置换和不经意传输协议由一方告知另外一方足够的数据以进行计算。

在 GMW 中采用的是一种不同的方式。我们可以假设 GMW 协议需要计算的布尔电路中使用了 XOR，NOT 和 AND 三种门电路。

先看非门，这个简单。

NOT 门对于输入导线的取值$w_i\in\{0,1\}$，输出的结果会是$\overline{w_i}$。

因为双方实现了秘密共享，也就是说一个原本的秘密$w_i$ 被分割为了$s_i^1,s_i^2$ 分别由$P_1,P_2$ 持有（当然前面只对输入秘密进行了分享，没有对中间过程的导线进行操作，不过先暂且当作已经做过了吧）。这样子的话，我们可以看一下这个等式：

$$\begin{aligned} &w_i=s_i^1\oplus s_i^2\\[2ex] &w_k=\overline{w_i}=\overline{s_i^1\oplus s_i^2}=\overline{s_i^1}\oplus \overline{s_i^2} \end{aligned}$$

也就是说，如果我们需要计算一个非门的输出结果，只需要参与双方各自把自己持有的秘密值取反就行了。

接下来是异或门。

同样的对于异或门的两个输入秘密$w_i$ 和$w_j$，我们将它们分别分割成两个秘密份额即$w_i=s_i^1\oplus s_i^2$ 和$w_j=s_j^1\oplus s_j^2$。

异或门需要计算的结果就是$w_k=w_i\oplus w_j=(s_i^1\oplus s_i^2)\oplus(s_j^1\oplus s_j^2)=(s_i^1\oplus s_j^1)\oplus(s_i^2\oplus s_j^2)$。也就是说，参与协议的两方可以各自计算自己两个秘密份额的异或值，得到的结果相当于异或门输出结果的一个份额。

比较复杂的部分在于与门的实现。

我们可以从$P_1$ 所持有的数据来看，$P_1$ 有的秘密份额是输入导线$w_i$ 的份额$s_i^1$ 和输入导线$w_j$ 的份额$s_j^1$。那么$P_1$ 就可以猜测$P_2$ 所持有的秘密份额分别是多少，也就是有四种可能： 00, 01, 10, 11 。这样子，$P_0$ 可以事先计算出这四种可能的结果$S$，即：

$$S=S_{s_i^1,s_j^1}(s_i^2,s_j^2)=(s_i^1\oplus s_i^2)\land(s_j^1\oplus s_j^2)$$

其中$s_i^2,s_j^2$ 是$P_2$ 可能持有的秘密份额。

理论上这里$P_1$ 和$P_2$ 直接通过一个 4 选 1-OT 协议就可以让$P_2$ 知道实际的秘密份额，但是这样便会暴露$P_1$ 的秘密份额（而且$P_1$ 还不知道结果），因此我们需要一个更复杂的方法。

$P_1$ 这时候选择一个随机数$r$，计算$S\oplus r$，一共得到四个结果，也就是：

$$\begin{aligned} S_{s_i^1,s_j^1}(0,0)\oplus r\\[2ex] S_{s_i^1,s_j^1}(0,1)\oplus r\\[2ex] S_{s_i^1,s_j^1}(1,0)\oplus r\\[2ex] S_{s_i^1,s_j^1}(1,1)\oplus r \end{aligned}$$

这样，双方通过一个 4 选 1-OT 协议，$P_2$ 就能够得到秘密份额$S_{s_i^1,s_j^1}(s_i^2,s_j^2)\oplus r$，而$P_1$ 的秘密份额就是$r$，双方也无法去了解对方的份额是多少（$P_1$ 不能知道 OT 选了到底哪一个）。

实际上或门的实现也可以采用类似的方法。

在计算的最后，双方可以向对方披露自己计算的结果的秘密份额，这样就可以还原出计算的结果。

# 参考

[1] David Evans; Vladimir Kolesnikov; Mike Rosulek, A Pragmatic Introduction to Secure Multi-Party Computation , now, 2018.