资料：

1. 主要参考 – MPC综述电子书：Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation[J]. Foundations and Trends® in Privacy and Security, 2018, 2(2-3): 70-246.
2. Goldreich, O., S. Micali, and A. Wigderson. 1987. “How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority”. In: 19th Annual ACM Symposium on Theory of Computing. Ed. by A. Aho. ACM Press. 218–229.
3. Ben-Or, M., S. Goldwasser, and A. Wigderson. 1988. “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)”. In: 20th Annual ACM Symposium on Theory of Computing. ACM Press. 1–10.
4. Beaver, D. 1992. “Efficient Multiparty Protocols Using Circuit Randomization”. In: Advances in Cryptology – CRYPTO’91. Ed. by J. Feigenbaum. Vol. 576. Lecture Notes in Computer Science*. Springer, Heidelberg. 420–432.
5. Shamir秘密共享方案：https://blog.csdn.net/weixin_44885334/article/details/124640944

文章目录

• GMW Protocol（1987）
• • 2PC
  • • • SS scheme
      • NOT Gate
      • XOR Gate
      • AND Gate
  • MPC
  • • • SS scheme
      • NOT Gate
      • XOR Gate
      • AND Gate
• BGW Protocol（1988）
• • Shamir SS scheme
  • Addition Gate
  • Multiplication-by-constant Gate
  • Multiplication Gate
• Beaver triple（1992）

我们用MPC来指代$n\ge 3$的参与者，我们用2PC来表示$n=2$的情况。

1. 某些 MPC 方案是需要大多数诚实的，因此$n=2$时不存在解。
2. 对于 2PC 的 Yao’s GC，推广到 MPC 是不容易的，因为电路生成者与任意的电路计算者串通，就可以得到中间结果的一些方程。需要一些新技术来推广GC。

可以利用有同态性质的秘密共享方案，基于GMW范式（1.Share, 2.Eval, 3.Recover）来搭建MPC协议。由于如下方案使用的 SS 协议都不是 VSS，因此搭建的 MPC 都是抵抗半诚实敌手的，无法阻止恶意敌手的破坏。

GMW Protocol（1987）

GMW方案是基于可加的秘密共享（additive shares）的MPC方案，它可以处理$n\ge 2$的所有情况。它可以工作在布尔电路（Boolean circuit）和算术电路（Arithmetic circuit）上，这里仅介绍布尔电路的协议。

2PC

SS scheme

P1 P_1P1​拥有隐私输入 x ∈ { 0 , 1 }n x \in \{0,1\}^nx∈{0,1}n， P2 P_2P2​拥有隐私输入 y ∈ { 0 , 1 }n y \in \{0,1\}^ny∈{0,1}n

P1 P_1P1​对于第$i$个输入比特 xi∈ { 0 , 1 }x_i \in \{0,1\}xi​∈{0,1}，

1. 生成随机比特 r i ∈ R{0,1}r_i \in_R \{0,1\} ri​∈R​{0,1}，
2. 将 r ir_i ri​发送给 P 2P_2 P2​，自己保留 x i⊕ r ix_i \oplus r_i xi​⊕ri​

类似的， P2 P_2P2​共享$y$的各个比特。

秘密重构：两方广播各自的 ”share” s1, s2∈ { 0 , 1 }s^1,s^2 \in \{0,1\}s1,s2∈{0,1}，计算 s = s1⊕ s2 s=s^1 \oplus s^2s=s1⊕s2

NOT Gate

对于门$G$的输入线 wi w_iwi​上的秘密 si s_isi​， P1 P_1P1​持有 si1 s_i^1si1​， P2 P_2P2​持有 si2 s_i^2si2​，易知
s i= s i 1⊕ s i 2s_i = s_i^1 \oplus s_i^2 si​=si1​⊕si2​
让 P1 P_1P1​翻转自己的share， sj1= si1⊕ 1s_j^1 = s_i^1 \oplus 1sj1​=si1​⊕1，而 P2 P_2P2​的share保持不变，那么输出线 wj w_jwj​上的share满足：
s j= s j 1⊕ s j 2= s i⊕1s_j = s_j^1 \oplus s_j^2 = s_i \oplus 1 sj​=sj1​⊕sj2​=si​⊕1
这就是非门。

XOR Gate

对于门$G$的输入线 wi, wj w_i,w_jwi​,wj​和输出线 wl w_lwl​， P1 P_1P1​持有 si1, sj1 s_i^1,s_j^1si1​,sj1​， P2 P_2P2​持有 si2, sj2 s_i^2,s_j^2si2​,sj2​，易知
s i= s i 1⊕ s i 2s j= s j 1⊕ s j 2s_i = s_i^1 \oplus s_i^2\\ s_j = s_j^1 \oplus s_j^2 si​=si1​⊕si2​sj​=sj1​⊕sj2​
让 P1 P_1P1​将自己的share相加，即 sl1= si1⊕ sj1 s_l^1 = s_i^1 \oplus s_j^1sl1​=si1​⊕sj1​， P2 P_2P2​同理， sl2= si2⊕ sj2 s_l^2 = s_i^2 \oplus s_j^2sl2​=si2​⊕sj2​，那么
s l= s l 1⊕ s l 2= s i⊕ s js_l = s_l^1 \oplus s_l^2 = s_i \oplus s_j sl​=sl1​⊕sl2​=si​⊕sj​
这就是异或门。

AND Gate

对于门$G$的输入线 wi, wj w_i,w_jwi​,wj​和输出线 wl w_lwl​， P1 P_1P1​持有 si1, sj1 s_i^1,s_j^1si1​,sj1​， P2 P_2P2​持有 si2, sj2 s_i^2,s_j^2si2​,sj2​

为了计算 si∧ sj s_i \wedge s_jsi​∧sj​， P1 P_1P1​和 P2 P_2P2​执行 1-out-of-4 OT协议：

1. P1 P_1P1​设置如下函数
   S:= Ss i 1, s j 1 ( s i 2, s j 2)=( s i 1⊕ s i 2)∧( s j 1⊕ s j 2)= s i∧ s jS := S_{s_i^1,s_j^1}(s_i^2,s_j^2) = (s_i^1 \oplus s_i^2) \wedge (s_j^1 \oplus s_j^2) = s_i \wedge s_j S:=Ssi1​,sj1​​(si2​,sj2​)=(si1​⊕si2​)∧(sj1​⊕sj2​)=si​∧sj​

2. P1 P_1P1​生成随机掩码（random mask bit） r ∈R{ 0 , 1 }r \in_R \{0,1\}r∈R​{0,1}，然后计算表格
   T G= ( r⊕S(0,0)r⊕S(0,1)r⊕S(1,0)r⊕S(1,1))T_G = \left( \begin{matrix} r \oplus S(0,0)\\ r \oplus S(0,1)\\ r \oplus S(1,0)\\ r \oplus S(1,1)\\ \end{matrix} \right) TG​=⎝ ⎛​r⊕S(0,0)r⊕S(0,1)r⊕S(1,0)r⊕S(1,1)​⎠ ⎞​

3. P1 P_1P1​与 P2 P_2P2​执行OT协议， P2 P_2P2​输入 si2, sj2 s_i^2,s_j^2si2​,sj2​挑选出其中一行
   s l 2= T G( s i 2, s j 2)=r⊕S( s i 2, s j 2)s_l^2 = T_G(s_i^2,s_j^2) = r \oplus S(s_i^2,s_j^2) sl2​=TG​(si2​,sj2​)=r⊕S(si2​,sj2​)

4. P1 P_1P1​设置 sl1= rs_l^1 = rsl1​=r，容易验证，
   s l= s l 1⊕ s l 2= Ss i 1, s j 1 ( s i 2, s j 2)= s i∧ s js_l = s_l^1 \oplus s_l^2 = S_{s_i^1,s_j^1}(s_i^2,s_j^2) = s_i \wedge s_j sl​=sl1​⊕sl2​=Ssi1​,sj1​​(si2​,sj2​)=si​∧sj​

对于其他的 2-to-1 Gate，修改$S$的定义即可。当然，$\{NOT,XOR,AND\}$是布尔完备的，其他门不必额外构造。

MPC

SS scheme

假设有$n$个参与者， Pi P_iPi​拥有隐私输入比特 xi∈ { 0 , 1 }x_i \in \{0,1\}xi​∈{0,1}，

1. 生成$n-1$个随机比特∀j≠i,  r j ∈ R{0,1}\forall j \neq i,\, r_j \in_R \{0,1\} ∀j=i,rj​∈R​{0,1}，
2. 将 s j= r js^j = r_j sj=rj​发送给 P jP_j Pj​， P iP_i Pi​自己保留 s i= x i⊕( ⨁ j≠ir j)s^i = x_i \oplus (\bigoplus_{j \neq i} r_j) si=xi​⊕(⨁j=i​rj​)

类似的， Pj P_jPj​共享的隐私输入的各个比特。

秘密重构：多方广播各自的 ”share” s1, s2, ⋯  , sn∈ { 0 , 1 }s^1,s^2,\cdots,s^n \in \{0,1\}s1,s2,⋯,sn∈{0,1}，计算 s = s1⊕ s2⊕ ⋯ ⊕ sn s=s^1 \oplus s^2 \oplus \cdots \oplus s^ns=s1⊕s2⊕⋯⊕sn

NOT Gate

让 P1 P_1P1​翻转自己的share，而 P2, ⋯  , Pn P_2,\cdots,P_nP2​,⋯,Pn​的share保持不变，那么输出线上的share满足：
s ′=( s 1⊕1)⊕ s 2⊕⋯⊕ s n=s⊕1s’ = (s^1 \oplus 1) \oplus s^2 \oplus \cdots \oplus s^n = s \oplus 1 s′=(s1⊕1)⊕s2⊕⋯⊕sn=s⊕1
这就是非门。

XOR Gate

对于门$G$的输入线 wi, wj w_i,w_jwi​,wj​和输出线 wl w_lwl​， Pk P_kPk​持有 sik, sjk s_i^k,s_j^ksik​,sjk​，易知
s i= s i 1⊕ s i 2s j= s j 1⊕ s j 2s_i = s_i^1 \oplus s_i^2\\ s_j = s_j^1 \oplus s_j^2 si​=si1​⊕si2​sj​=sj1​⊕sj2​
让 ∀ k ,  Pk \forall k,\,P_k∀k,Pk​将自己的share相加，即 slk= sik⊕ sjk s_l^k = s_i^k \oplus s_j^kslk​=sik​⊕sjk​，那么
s l=( s i 1⊕ s j 1)⊕⋯⊕( s i n⊕ s j n)= s i⊕ s js_l = (s_i^1 \oplus s_j^1) \oplus \cdots \oplus (s_i^n \oplus s_j^n) = s_i \oplus s_j sl​=(si1​⊕sj1​)⊕⋯⊕(sin​⊕sjn​)=si​⊕sj​
这就是异或门。

AND Gate

对于门$G$的输入线 wi, wj w_i,w_jwi​,wj​和输出线 wl w_lwl​， Pk P_kPk​持有 sik, sjk s_i^k,s_j^ksik​,sjk​

容易看出，
sl = s i∧ s j=( s i 1⊕⋯⊕ s i n)∧( s j 1⊕⋯⊕ s j n) = ( ⨁ k = 1nsik∧ sjk)⊕ ( ⨁ k1≠ k2 si k 1∧ sj k 2)\begin{aligned} s_l &= s_i \wedge s_j = (s_i^1 \oplus \cdots \oplus s_i^n) \wedge (s_j^1 \oplus \cdots \oplus s_j^n)\\ &= \left( \bigoplus_{k=1}^n s_i^k \wedge s_j^k \right) \oplus \left( \bigoplus_{k_1 \neq k_2} s_i^{k_1} \wedge s_j^{k_2} \right) \end{aligned} sl​​=si​∧sj​=(si1​⊕⋯⊕sin​)∧(sj1​⊕⋯⊕sjn​)=(k=1⨁n​sik​∧sjk​)⊕⎝ ⎛​k1​=k2​⨁​sik1​​∧sjk2​​⎠ ⎞​​
对于前半部分， Pk P_kPk​可以本地计算
s l,1k= s i k∧ s j ks_{l,1}^k = s_i^k \wedge s_j^k sl,1k​=sik​∧sjk​
对于后半部分，每一对 P k 1, P k 2 P_{k_1},P_{k_2}Pk1​​,Pk2​​利用 2PC-GMW 里的 AND Gate，使用OT协议计算出
s l,2 k 1, k 2 ⊕ s l,2 k 2, k 1 = s i k1 ∧ s j k2 s_{l,2}^{k_1,k_2} \oplus s_{l,2}^{k_2,k_1} = s_i^{k_1} \wedge s_j^{k_2} sl,2k1​,k2​​⊕sl,2k2​,k1​​=sik1​​∧sjk2​​
其中 s l , 2 k1, k2s_{l,2}^{k_1,k_2}sl,2k1​,k2​​被 P k 1 P_{k_1}Pk1​​持有， s l , 2 k2, k1s_{l,2}^{k_2,k_1}sl,2k2​,k1​​被 P k 2 P_{k_2}Pk2​​持有。

最后， Pk P_kPk​将自己所有的share本地相加，
s l k= s l,1k⊕ ( ⨁ k′≠ ks l , 2 k , k′ )s_l^k = s_{l,1}^k \oplus \left( \bigoplus_{k’ \neq k} s_{l,2}^{k,k’} \right) slk​=sl,1k​⊕⎝ ⎛​k′=k⨁​sl,2k,k′​⎠ ⎞​
容易验证，
sl = ⨁ k s l k= ⨁ k [ s l , 1k⊕ ( ⨁k ′≠ks l,2k, k ′ )] = ( ⨁ k = 1ns l , 1k)⊕ ( ⨁ k1≠ k2 ( s l,2 k 1, k 2 ⊕ s l,2 k 2, k 1 )) = s i∧ s j\begin{aligned} s_l &= \bigoplus_k s_l^k = \bigoplus_k \left[ s_{l,1}^k \oplus \left( \bigoplus_{k’ \neq k} s_{l,2}^{k,k’} \right) \right] \\ &= \left( \bigoplus_{k=1}^n s_{l,1}^k \right) \oplus \left( \bigoplus_{k_1 \neq k_2} \left(s_{l,2}^{k_1,k_2} \oplus s_{l,2}^{k_2,k_1}\right) \right) \\ &= s_i \wedge s_j \end{aligned} sl​​=k⨁​slk​=k⨁​⎣ ⎡​sl,1k​⊕⎝ ⎛​k′=k⨁​sl,2k,k′​⎠ ⎞​⎦ ⎤​=(k=1⨁n​sl,1k​)⊕⎝ ⎛​k1​=k2​⨁​(sl,2k1​,k2​​⊕sl,2k2​,k1​​)⎠ ⎞​=si​∧sj​​
这就完成了与门的计算。

对于$n\ge 3$，MPC-GMW 调用了 A2n A_2^nA2n​次 2PC-GMW 的 AND Gate，也就是使用了 A2n A_2^nA2n​次 OT 协议。对于$n=2$，只需调用$1$次而非 A22= 2A^2_2=2A22​=2次。

BGW Protocol（1988）

本协议工作在算术电路上，算术运算的域为$\mathbb{F}$，要求大多数诚实（honest majority），也就是$n\ge 3$

Shamir SS scheme

对于秘密值$v\in \mathbb{F}$，构造一个$t-1$次的随机多项式$p(x)\in \mathbb{F}[x]$，使得$p(0)=\alpha$
p(x):=v+ ∑ i=1t−1a i⋅ x ip(x):= v + \sum_{i=1}^{t-1} a_i \cdot x^i p(x):=v+i=1∑t−1​ai​⋅xi
然后将$\forall i=1,\cdots ,n,p(i)$作为$v$的share分配给 Pi P_iPi​，记做$[v]$；确切地说， [ v ] = ( xi, yi= p ( xi) )[v] = (x_i,y_i=p(x_i))[v]=(xi​,yi​=p(xi​))

为了重建秘密，$n$个参与者中任意$t$个人合作，利用拉格朗日插值公式
λ i:= ∏ j=1,j≠it− x j( x i− x j ) −1 \lambda_i := \prod_{j=1,j \neq i}^t -x_j(x_i – x_j)^{-1} λi​:=j=1,j=i∏t​−xj​(xi​−xj​)−1
v← ∑ i=1t y i⋅ λ i∈ Z qv \leftarrow \sum_{i=1}^t y_i \cdot \lambda_i \in Z_q v←i=1∑t​yi​⋅λi​∈Zq​

这里的 λi \lambda_iλi​叫做Lagrange coefficients，只与 xi x_ixi​有关，是公开的，可以预计算。于是秘密$v$就是share yi y_iyi​的线性组合。

Addition Gate

假设门$G$的两条输入线是$\alpha ,\beta$，一条输出线是$\gamma$

每一个参与者都持有输入线上的秘密的 shares [ vα] , [ vβ][v_\alpha],[v_\beta][vα​],[vβ​]，于是 Pi P_iPi​可以本地计算share的加法：
[ v γ]=[ v α]+[ v β]= p α( x i)+ p β( x i)[v_\gamma] = [v_\alpha] + [v_\beta] = p_\alpha(x_i)+p_\beta(x_i) [vγ​]=[vα​]+[vβ​]=pα​(xi​)+pβ​(xi​)
容易验证，
∑ i=1t[ v γ ] i⋅ λ i = ∑ i=1t([ v α ] i+[ v β ] i) λ i = ∑ i=1t[ v α ] i λ i+ ∑ i=1t[ v β ] i λ i = v α+ v β\begin{aligned} \sum_{i=1}^t [v_\gamma]_i \cdot \lambda_i &= \sum_{i=1}^t ([v_\alpha]_i + [v_\beta]_i) \lambda_i \\ &= \sum_{i=1}^t [v_\alpha]_i \lambda_i + \sum_{i=1}^t [v_\beta]_i \lambda_i\\ &= v_\alpha + v_\beta \end{aligned} i=1∑t​[vγ​]i​⋅λi​​=i=1∑t​([vα​]i​+[vβ​]i​)λi​=i=1∑t​[vα​]i​λi​+i=1∑t​[vβ​]i​λi​=vα​+vβ​​
因此， [ vγ] = [ vα+ vβ][v_\gamma] = [v_\alpha + v_\beta][vγ​]=[vα​+vβ​]，这就完成了加法门。

Multiplication-by-constant Gate

假设门$G$的一条输入线是$\alpha$，一条输出线是$\gamma$

每一个参与者都持有输入线上的秘密的 shares [ vα][v_\alpha][vα​]，于是 Pi P_iPi​可以本地计算share的数乘：

[ v γ]=c⋅[ v α]=c⋅ p α( x i)[v_\gamma] = c \cdot [v_\alpha] = c \cdot p_\alpha(x_i) [vγ​]=c⋅[vα​]=c⋅pα​(xi​)

容易验证，
∑ i=1t[ v γ ] i⋅ λ i = ∑ i=1t(c⋅[ v α ] i) λ i =c⋅ ∑ i=1t[ v α ] i λ i =c⋅ v α\begin{aligned} \sum_{i=1}^t [v_\gamma]_i \cdot \lambda_i &= \sum_{i=1}^t (c \cdot [v_\alpha]_i) \lambda_i \\ &= c \cdot \sum_{i=1}^t [v_\alpha]_i \lambda_i\\ &= c \cdot v_\alpha \end{aligned} i=1∑t​[vγ​]i​⋅λi​​=i=1∑t​(c⋅[vα​]i​)λi​=c⋅i=1∑t​[vα​]i​λi​=c⋅vα​​
因此， [ vγ] = [ c ⋅ vα][v_\gamma] = [c \cdot v_\alpha][vγ​]=[c⋅vα​]，这就完成了数乘门。

Multiplication Gate

假设门$G$的两条输入线是$\alpha ,\beta$，一条输出线是$\gamma$

每一个参与者都持有输入线上的秘密的 shares [ vα] , [ vβ][v_\alpha],[v_\beta][vα​],[vβ​]，于是 Pi P_iPi​可以本地计算share的乘法：
[ v γ]=[ v α]⋅[ v β]= p α( x i)⋅ p β( x i)[v_\gamma] = [v_\alpha] \cdot [v_\beta] = p_\alpha(x_i) \cdot p_\beta(x_i) [vγ​]=[vα​]⋅[vβ​]=pα​(xi​)⋅pβ​(xi​)
根据离散傅里叶变换的性质，上述的 [ vγ][v_\gamma][vγ​]是多项式乘积 q ( x ) : = pα( x ) pβ( x )q(x):=p_\alpha(x)p_\beta(x)q(x):=pα​(x)pβ​(x)在点 xi x_ixi​处的值。为了重构至多$2t-2$次的$q(x)$，原则上需要$2t-1$个shares，有
∑ i=12t−1 [ v γ ] i⋅ λ i= v α⋅ v β=q(0)\begin{aligned} \sum_{i=1}^{2t-1} [v_\gamma]_i \cdot \lambda_i = v_\alpha \cdot v_\beta = q(0) \end{aligned} i=1∑2t−1​[vγ​]i​⋅λi​=vα​⋅vβ​=q(0)​
当然，我们要的仅仅是$q(0)$而非$q(x)$。为了保持秘密分享的 $t-$threshold，可以重新选择一个多项式$Q(x)$，使得$Q(0)=q(0)$，这就是 degree-reduction step：

1. 每个 Pi P_iPi​都生成自己的 share [ vγ]i= q ( xi)[v_\gamma]_i = q(x_i)[vγ​]i​=q(xi​)的 threshold-t sharing [ q ( xi) ][q(x_i)][q(xi​)]，发送给其他的参与者（也就是对 share 再进行 secret sharing）

2. 每个 Pi P_iPi​都利用拉格朗日插值公式，本地计算新的 share：
   [q(0) ] i= ∑ j=12t−1 [q( x j) ] i⋅ λ j[q(0)]_i = \sum_{j=1}^{2t-1} [q(x_j)]_i \cdot \lambda_j [q(0)]i​=j=1∑2t−1​[q(xj​)]i​⋅λj​
   可以验证，
   ∑ i=1t[q(0) ] i⋅ Λ i = ∑ i=1t ( ∑ j = 1 2 t − 1[ q ( xj) ]i⋅ λj)⋅ Λ i = ∑ j=12t−1( ∑ i = 1t[ q ( xj) ]i⋅ Λi)⋅ λ j = ∑ j=12t−1 q( x j)⋅ λ j =q(0)=Q(0)\begin{aligned} \sum_{i=1}^t [q(0)]_i \cdot \Lambda_i &= \sum_{i=1}^t \left( \sum_{j=1}^{2t-1} [q(x_j)]_i \cdot \lambda_j \right) \cdot \Lambda_i\\ &= \sum_{j=1}^{2t-1} \left( \sum_{i=1}^t [q(x_j)]_i \cdot \Lambda_i \right) \cdot \lambda_j\\ &= \sum_{j=1}^{2t-1} q(x_j) \cdot \lambda_j\\ &= q(0) = Q(0) \end{aligned} i=1∑t​[q(0)]i​⋅Λi​​=i=1∑t​(j=1∑2t−1​[q(xj​)]i​⋅λj​)⋅Λi​=j=1∑2t−1​(i=1∑t​[q(xj​)]i​⋅Λi​)⋅λj​=j=1∑2t−1​q(xj​)⋅λj​=q(0)=Q(0)​
   这里 Λi \Lambda_iΛi​是$Q(x)$的拉格朗日系数，而 λj \lambda_jλj​是$q(x)$的。