混合 MPC：ABY 架构

参考文献：

1. Demmler D, Schneider T, Zohner M. ABY-A framework for efficient mixed-protocol secure two-party computation[C]//NDSS. 2015.
2. Kolesnikov V, Sadeghi A R, Schneider T. A systematic approach to practically efficient general two-party secure function evaluation protocols and their modular design[J]. Journal of Computer Security, 2013, 21(2): 283-315.
3. 高效 OT 协议：https://blog.csdn.net/weixin_44885334/article/details/127084970

ABY架构

ABY 含义：Arithmetic（基于SS的算术电路）, Boolean（基于SS的布尔电路）, and Yao（姚的混淆电路）

算术电路使用的 SS 是：
$$<x{>}_0^A+<x{>}_1^A\equiv x\mathrm{mod}{2}^l$$
布尔电路使用的 SS 是：
$$<x{>}_0^B\oplus <x{>}_1^B=x$$
ABY 将使用 Free XOR 技术的 Yao’s GC 的输入线标签，也视作是 shares，对于 x ∈ { 0 , 1 } x \in \{0,1\} x∈{0,1}
$$<x{>}_0^Y=k_0,<x{>}_1^Y=k_x=k_0\oplus xR$$
并且将 P&P 技术的选择比特$p_0$作为线标签$k_0$的第一比特。再固定$R$的第一比特为$1$，保证$k_0,k_1$的第一比特随机但不相同。它们满足
$$<x{>}_0^Y\oplus <x{>}_1^Y=xR$$
对于 Yao’s GC 的输入比特的 shares，可以使用 C-OT 快速分享。另外，对于布尔电路和算术电路的 Beaver Triple，都可以使用 R-OT 批量获得。

ABY 框架结合三种 2PC 的优势，让 shares 在它们之间相互转换，从而提高 2PC 的效率。

转换

Y2B

对于秘密值 x ∈ { 0 , 1 } x \in \{0,1\} x∈{0,1}，Yao’s GC 的 shares 为
$$<x{>}_0^Y=k_0,<x{>}_1^Y=k_x=k_0\oplus xR$$
其中$R[0]=1$，因此它们的选择比特满足：
$$<x{>}_0^Y[0]\oplus <x{>}_1^Y[0]=x$$
所以，转换方法就是：
$$<x{>}_i^B=Y2B(<x{>}_i^Y)=<x{>}_i^Y[0]$$

这是 free 的，只需要一丁点的本地计算。

B2Y

对于秘密值 x ∈ { 0 , 1 } x \in \{0,1\} x∈{0,1}，布尔电路的 shares 为
< x > 0 B = r ∈ R { 0 , 1 } ,   < x > 1 B = x ⊕ r _0^B = r \in_R \{0,1\},\, _1^B = x \oplus r <x>0B​=r∈R​{0,1},<x>1B​=x⊕r
它们满足
$$<x{>}_0^B\oplus <x{>}_1^B=x$$

• $P_0$是 Yao’s GC 的生成者，它持有随机的线标签$k_0$和全局随机数$R$，以及$<x{>}_0^B=r$
• $P_1$是计算方，它持有$<x{>}_1^B$

运行 OT 协议，$P_0$输入$(k_0\oplus rR,k_0\oplus (1-r)R)$，$P_1$输入$<x{>}_1^B$，并获得
o u t = { k 0 ⊕ ( r ⊕ 0 ) R , < x > 1 B = 0 k 0 ⊕ ( r ⊕ 1 ) R , < x > 1 B = 1 out = \left\{

\right. out={k0​⊕(r⊕0)R,k0​⊕(r⊕1)R,​​<x>1B​=0<x>1B​=1​
即
$$out=k_0\oplus (<x{>}_0^B\oplus <x{>}_1^B)R=k_x$$
因此$P_1$获得了 Yao’s GC 的 share，
$$<x{>}_1^Y=out=k_x$$
而$P_0$简单地设置$<x{>}_0^Y=k_0$

A2Y

对于秘密值 x ∈ { 0 , 1 } l x \in \{0,1\}^l x∈{0,1}l，算术电路的 shares 为
< x > 0 A = r ∈ R { 0 , 1 } l ,   < x > 1 A = x − r _0^A = r \in_R \{0,1\}^l,\, _1^A = x - r <x>0A​=r∈R​{0,1}l,<x>1A​=x−r

构造布尔加法电路，其功能为
$$x=<x{>}_0^A+<x{>}_1^A$$
让$P_0$构建对应的混淆版本，

1. 输入：$P_0$输入$<x{>}_0^A$的$l$比特，$P_1$输入$<x{>}_1^A$的$l$比特
2. 输出：电路输出$x\in {\mathbb{Z}}_{2^l}$的$l$比特的混淆值$<x{>}^Y$

那么，对于每个$1\le i\le l$，$P_0$持有$<x_i{>}_0^Y=k_0^i$，$P_1$持有$<x_i{>}_1^Y=k_x^i$

A2B

方案一

类似 A2Y，构建布尔加法电路，功能是计算
$$x=<x{>}_0^A+<x{>}_1^A$$
使用基于 SS 的布尔电路，

1. $P_0$将$<x{>}_0^A\in {\mathbb{Z}}_{2^l}$的每一比特都共享出去，$<<x{>}_0^A[i]{>}^B$
2. $P_1$将$<x{>}_1^A\in {\mathbb{Z}}_{2^l}$的每一比特都共享出去，$<<x{>}_1^A[i]{>}^B$
3. 然后计算出结果$<x{>}^B$

方案二

可以复用其他的转换函数，
$$<x{>}^B=A2B(<x{>}^A)=Y2B\circ A2Y(<x{>}^A)$$
因为 Y2B 是 free 的，并且 A2Y 基于 Yao’s GC，它的计算效率远高于基于 SS 的布尔电路，所以方案二速度更快。

B2A

对于$l$比特的秘密值 x ∈ { 0 , 1 } l x \in \{0,1\}^l x∈{0,1}l，布尔电路的 shares 满足
$$<x_i{>}_0^B\oplus <x_i{>}_1^B=x_i$$

于是
$$x=\sum _{i=0}^{l-1}{2}^i{x}_i=\sum _{i=0}^{l-1}{2}^i\cdot (<x_i{>}_0^B\oplus <x_i{>}_1^B)$$
可以用 OT 协议完成转换：

1. $P_0$作为发送者，选择随机数$r_i\in {\mathbb{Z}}_{2^l}$，输入$(s_0^i,s_1^i)$
   s 1 i = 2 i ⋅ < x i > 0 B − r i s 0 i = 2 i ⋅ ( 1 − < x i > 0 B ) − r i

   s1i=2i⋅<xi>0B−ris0i=2i⋅(1−<xi>0B)−ri" role="presentation">si1si0=2i⋅<xi>B0−ri=2i⋅(1−<xi>B0)−ri$$\begin{array}{rl}{s}_1^i& =2^i\cdot <x_i{>}_0^B-r_i\\ s_0^i& =2^i\cdot (1-<x_i{>}_0^B)-r_i\end{array}$$
   s1i​s0i​​=2i⋅<xi​>0B​−ri​=2i⋅(1−<xi​>0B​)−ri​​

2. $P_1$作为接收者，输入$<x_i{>}_1^B$，获得
   o u t i = { 2 i ⋅ ( < x i > 0 B ⊕ 0 ) − r i , < x > 1 B = 0 2 i ⋅ ( < x i > 0 B ⊕ 1 ) − r i , < x > 1 B = 1 out_i = \left\{

   2i⋅(<xi>0B⊕0)−ri,<x>1B=02i⋅(<xi>0B⊕1)−ri,<x>1B=1" role="presentation">2i⋅(<xi>B0⊕0)−ri,2i⋅(<xi>B0⊕1)−ri,<x>B1=0<x>B1=1$$\begin{array}{rlr}{2}^i\cdot (<x_i{>}_0^B\oplus 0)-r_i,& & <x{>}_1^B=0\\ 2^i\cdot (<x_i{>}_0^B\oplus 1)-r_i,& & <x{>}_1^B=1\end{array}$$
   \right. outi​={2i⋅(<xi​>0B​⊕0)−ri​,2i⋅(<xi​>0B​⊕1)−ri​,​​<x>1B​=0<x>1B​=1​
   即
   $$ou{t}_i=2^i\cdot {(}_0^B{\oplus }_1^B)-r_i=2^i{x}_i-r_i$$

3. $P_0$设置
   $$<x{>}_0^A=\sum _{i=0}^{l-1}{r}_i$$
   $P_1$设置
   $$<x{>}_1^A=\sum _{i=0}^{l-1}ou{t}_i=x-<x{>}_0^A$$
   容易验证$<x{>}_0^A+<x{>}_1^A=x\in {\mathbb{Z}}_{2^l}$

Y2A

方案一

对于$l$比特的秘密值 x ∈ { 0 , 1 } l x \in \{0,1\}^l x∈{0,1}l，Yao’s GC 中的$P_1$作为计算方，持有它的混淆值$k_{x_i}^i,\forall 1\le i\le l$，而$P_0$作为生成方持有对应的$k_0^i$以及$R$

1. 令$P_0$选择一个随机掩码（random mask）$r{\in }_R{\mathbb{Z}}_{2^l}$

2. $P_0$根据$k_0^i$以及$R$，构造一个布尔减法电路的混淆版本，功能为
   $$X=x-r$$
   电路发送给$P_1$，同时发送$r$对应的$l+\sigma$个混淆值

3. $P_1$已经持有了$x$对应的混淆值$k_x^i$，不必执行 OT 协议。在混淆电路上计算，设置$<x{>}_1^A=X=x-r$

4. $P_0$简单地设置$<x{>}_0^A=r$

方案二

可以复用其他的转换函数，
$$<x{>}^A=Y2A(<x{>}^Y)=B2A\circ Y2B(<x{>}^Y)$$
因为 Y2B 是 free 的，并且 B2A 主要使用 OT 协议，在计算和通信上的开销比构造和计算 Yao’s GC 小得多，所以方案二速度更快。

效果

预处理阶段（构造电路，执行 OT 协议）：

在线阶段（电路运算）：