ABY2.0：更低的通信开销

参考文献：

1. [ABY] Demmler D, Schneider T, Zohner M. ABY-A framework for efficient mixed-protocol secure two-party computation[C]//NDSS. 2015.
2. [ABY3] Mohassel P, Rindal P. ABY3: A mixed protocol framework for machine learning[C]//Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. 2018: 35-52.
3. [ABY2.0] Patra A, Schneider T, Suresh A, et al. {ABY2. 0}: Improved {Mixed-Protocol} Secure {Two-Party} Computation[C]//30th USENIX Security Symposium (USENIX Security 21). 2021: 2165-2182.
4. [Beaver91] D. Beaver. Effificient multiparty protocols using circuit randomization. In CRYPTO, 1991.
5. [ALSM13] Asharov G, Lindell Y, Schneider T, et al. More efficient oblivious transfer and extensions for faster secure computation[C]//Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 2013: 535-548.
6. [RSS19] Rathee D, Schneider T, Shukla K K. Improved multiplication triple generation over rings via RLWE-based AHE[C]//International Conference on Cryptology and Network Security. Cham: Springer International Publishing, 2019: 347-359.

混合 MPC

首先汇总下以 Arithmetic - Boolean - Yao 为名的三种混合协议：

• 著名的 ABY 是第一个混合多种 MPC 协议的安全多方计算协议。不过由于 Yao’s GC 的限制，它仅仅是个半诚实安全的 2PC 协议。
• 之后的 ABY3 是一种恶意安全的 3PC 协议。它使用了 Yao’s GC 的三方扩展，两个 Garbler，一个 Evaluator。由于三方协议计算 AND 门不需要 Beaver Triple，因此计算速度比 ABY 快很多。
• 而 ABY2.0 则是对 ABY 的通信性能做了改进，它也是半诚实安全的 2PC 协议。

它们的基本流程都是：

1. 利用 Sharing protocol，将输入值分享给各方
2. 利用 SS 的 Linear Homomorphic 性质，以及 Multiplication protocol，计算给定的函数（期间做 A-B-Y 之间的 shares 转换）
3. 使用 Reconstruction protocol，从 shares 恢复出输出值

乘法协议

使用 Beaver Triple 计算乘法门，给定元组 $({\delta }_a,{\delta }_b,{\delta }_{ab}={\delta }_a{\delta }_b)$，满足关系
$$\begin{array}{rl}ab& =(a+{\delta }_a-{\delta }_a)(b+{\delta }_b-{\delta }_b)\\ & =(a+{\delta }_a)(b+{\delta }_b)-(a+{\delta }_a){\delta }_b-(b+{\delta }_b){\delta }_a+{\delta }_{ab}\end{array}$$

简记 ${\Delta }_a=a+{\delta }_a,{\Delta }_b=b+{\delta }_b$。参与方 P i , i ∈ { 0 , 1 } P_i,i\in \{0,1\} Pi​,i∈{0,1} 持有 $([a{]}_i,[{\delta }_a{]}_i),([b{]}_i,[{\delta }_b{]}_i),[{\delta }_{ab}{]}_i$ 这些 shares，为了计算 $c=ab$ 的 shares，使用 Beaver 乘法协议：

1. $P_i$ 计算 $[{\Delta }_a{]}_i=[a{]}_i+[{\delta }_a{]}_i$ 以及 $[{\Delta }_b{]}_i=[b{]}_i+[{\delta }_b{]}_i$
2. $P_i$ 互相发送 $[{\Delta }_a{]}_i$ 和 $[{\Delta }_b{]}_i$ 给对方（四个元素）
3. $P_i$ 重构出 ${\Delta }_a=[{\Delta }_a{]}_0+[{\Delta }_a{]}_1$ 和 ${\Delta }_a=[{\Delta }_a{]}_0+[{\Delta }_a{]}_1$
4. $P_i$ 计算 $[c{]}_i=i\cdot {\Delta }_a{\Delta }_b-{\Delta }_a[{\delta }_b{]}_i-{\Delta }_b[{\delta }_a{]}_i+[{\delta }_{ab}{]}_i$
5. $P_i$ 持有了 $[c{]}_i$，容易验证 $[c{]}_0+[c{]}_1=ab=c$

ABY2.0 观察到 ${\Delta }_a,{\Delta }_b$ 最终是明文信息，因此修改 shares 的格式，从原本的 $([a{]}_i,[{\delta }_a{]}_i)$ 变为了 $({\Delta }_a,[{\delta }_a{]}_i)$。容易验证：
$$\begin{gathered} a={\Delta }_a-[{\delta }_a{]}_0-[{\delta }_a{]}_1 \\ {c}_1\cdot ({\Delta }_a,[{\delta }_a{]}_i)+c_2\cdot ({\Delta }_b,[{\delta }_b{]}_i)=({\Delta }_{c_{1}a+c_{2}b},[{\delta }_{c_{1}a+c_{2}b}{]}_i) \end{gathered}$$

因此定义 $⟨a{⟩}_i:=({\Delta }_a,[{\delta }_a{]}_i)$ 是新的 shares 格式，它依然是线性同态的。它对应的 Sharing Protocol 为，$P_i$ 随机采样 $[{\delta }_a{]}_0,[{\delta }_a{]}_1$，计算 ${\Delta }_a=a+[{\delta }_a{]}_0+[{\delta }_a{]}_1$，自己持有 $⟨a{⟩}_i=({\Delta }_a,[{\delta }_a{]}_i)$，将 $⟨a{⟩}_{1-i}=({\Delta }_a,[{\delta }_a{]}_{1-i})$ 发送给对方。

参与方 P i , i ∈ { 0 , 1 } P_i,i\in \{0,1\} Pi​,i∈{0,1} 持有 $({\Delta }_a,[{\delta }_a{]}_i),({\Delta }_b,[{\delta }_b{]}_i),[{\delta }_{ab}{]}_i$ 这些 shares，为了计算 $c=ab$ 的 shares，使用 ABY2.0 乘法协议：

1. $P_i$ 独立生成随机数 $[{\delta }_c{]}_i$（作为 Sharing 协议的一部分）
2. $P_i$ 计算 $[{\Delta }_c{]}_i=i\cdot {\Delta }_a{\Delta }_b-{\Delta }_a[{\delta }_b{]}_i-{\Delta }_b[{\delta }_a{]}_i+[{\delta }_{ab}{]}_i+[{\delta }_c{]}_i$
3. $P_i$ 互相发送 $[{\Delta }_c{]}_i$ 给对方（两个元素）
4. $P_i$ 重构出 ${\Delta }_c=[{\Delta }_c{]}_0+[{\Delta }_c{]}_1$
5. $P_i$ 持有了 $⟨c{⟩}_i=({\Delta }_c,[{\delta }_c{]}_i)$，容易验证 ${\Delta }_c-[{\delta }_c{]}_0-[{\delta }_c{]}_1=ab=c$

Beaver 和 ABY2.0 对比如下：

上述的乘法协议在算术电路和布尔电路中都奏效，假设消息空间是 ${\mathbb{Z}}_{2^l}$，那么在 Online 阶段，ABY2.0 乘法门的通信开销仅为 $2l$ 比特，对比 Beaver 的开销为 $4l$ 比特。

对于 Setup 阶段，ABY2.0 的开销没变，因为它依然要生成 Beaver Triple。这可以通过 C-OT 或者 AHE 实现。

• 由于 ${\delta }_{ab}=([{\delta }_a{]}_0+[{\delta }_a{]}_1)([{\delta }_b{]}_0+[{\delta }_b{]}_1)$ 可以拆分出四项加和，其中两项 $[{\delta }_a{]}_i[{\delta }_b{]}_i$ 可以本地计算，因此我们只需实现交叉项 $[{\delta }_a{]}_i[{\delta }_b{]}_{1-i}$ 的 shares 计算。
• C-OT based [ALSM13]，
  1. $P_i$ 作为发送方，定义相关函数 $f_j(x)=x+2^j[{\delta }_a{]}_i$，输入 $(m_{j,0}=r_j,m_{j,1}=f(r_j))$，
  2. $P_{1-i}$ 作为接收方，根据 $[{\delta }_b{]}_{1-i}$ 的第 $j$ 比特 $b_j$ 做出选择， 获得 $m_{j,b_j}$
  3. $P_i$ 持有 $[d{]}_i=-{\sum }_j{r}_j$，$P_{1-i}$ 持有 $[d{]}_{1-i}={\sum }_j{m}_{j,b_j}$，容易验证 $[d{]}_i+[d{]}_{1-i}=[{\delta }_a{]}_i[{\delta }_b{]}_{1-i}$
• AHE based [RSS19]，
  1. $P_0$ 生成公钥 $pk$，将 $[{\delta }_a{]}_0,[{\delta }_b{]}_0$ 加密后发送给 $P_1$
  2. $P_1$ 生成随机数 $r$，同态计算线性函数 $v=[{\delta }_a{]}_0[{\delta }_b{]}_1+[{\delta }_a{]}_1[{\delta }_b{]}_0-r$
  3. $P_1$ 发送密文 $E(v)$，$P_0$ 解密得到 $v$
  4. $P_0$ 持有 $[d{]}_0=v$，$P_1$ 持有 $[d{]}_1=r$，容易验证 $[d{]}_0+[d{]}_1=[{\delta }_a{]}_0[{\delta }_b{]}_1+[{\delta }_a{]}_1[{\delta }_b{]}_0$

ABY 转换

ABY2.0 同时使用了 $[a{]}_i$ 和 $⟨a{⟩}_i$ 两种格式的 SS，因此 A-B-Y 之间的转换与 ABY 略有不同。不过基本思路是一样的，这里不再详细描述。

除了 Y2B，其他的转换 ABY2.0 的通信量更小。除了 A2B，其他的转换 ABY2.0 的通信轮数仅为 $1$。不过 ABY2.0 的初始化阶段通信开销会更大。