For ABY Note: Sharing Conversions

关于论文ABY的阅读笔记。The Conversion Method between Arithmetic, Binary and Yao Sharing –算术共享、布尔共享和混淆电路共享的相互转换

在2015年Daniel Demmler等人在NDSS上发表了ABY，设计了一个共享、布尔共享和混淆电路共享的相互转换的协议。在机器学习的运算中，需要经常在算术（乘法和加法）和二进制（非线性激活函数、最大池化、平均值等）运算之间来回变换。而安全多方计算中的算术共享（Arithmetic Sharing）、布尔共享（Boolean Sharing）、和姚共享（Yao’s Sharing）对于不同算子，如加乘法和比较等各有优势。如何设计更高效的算法、平衡不同技术之间的优势，发挥最好的性能，是文章主要讨论的。

位分解$[\![ x]\!]^{\mathsf{A}} \rightarrow [\![ \vec{x}]\!]^{\mathsf{B}}$

算术共享$x \in \mathbb{Z}_{2^k}$ 转换为比特秘密共享向量 $x[1], \cdots, x[k] \in \{ 0,1 \}$ 使得 $ x = \sum^k_{i=1}2^{i-1}x[i] $。每方把$[\![ x]\!]^\mathsf{A} = (x_1, x_2, x_3)$输入到布尔电路中求和。为了减少通信轮次和复杂度，$[\![ x]\!]^\mathsf{A} = (x_1, x_2, x_3)$转换成$[\![ x_1]\!]^\mathsf{B} := (x_1, 0, 0), [\![ x_2]\!]^\mathsf{B} := (0, x_2, 0), [\![ x_3]\!]^\mathsf{B} := (0, 0, x_3)$。这步无需交互，但是可能通过线性组合可能会泄露信息从而带来安全隐患。 不过由于后续的随机化和$ x_1, x_2, x_3 $的分布，可证明它的安全性。执行三方安全计算二进制秘密共享可以利用$2k$轮计算$\mathsf{RCFA}(\mathsf{RCFA}(x_1,x_2),x_3)$行纹进位全加器 (ripple-carry full adder) 电路实现。为了避免多次通信轮数，采用超前进位加法器(Parallel Prefix Adder, PPA)，利用分治算法(Divide and Conquer Algorithm)计算两个输入的总和，需要$\log k$轮通信和$k\log k$个门。这使得在半诚实和恶意模型下两个加法电路的消耗接近单个PPA的成本，通信轮次和通信复杂度降低一半。同样，利用$k$个全加器(Full Adder) $\mathsf{FA}(x_i[i], x_2[i],x_3[i-1]) \rightarrow (c[i], s[i])$，这里$i \in {0, \cdots, k-1}$，将$x_1 + x_2 + x_3 $ 的计算简化为$2c+s$，其中$c[i], s[i]$ 表示比特串$c$和$s$的第i位。注意，一般由计算两个比特的加法和一个进位链接起一个全加器，这里用全加器的组成把运算单元由3个变成2个，即$(x_1, x_2, x_3)\rightarrow (c,s)$，同时只需一轮通信交互，而不是$k$轮。最终结果可以用一个并行前缀加法器(Parallel Prefix Adder)计算$2[\![ c ]\!]^\mathsf{B} +[\![ s ]\!]^\mathsf{B}$。同样，半诚实模型中，第2方可将$(x_1+x_2)$作为三方计算隐私输入，并得到$[\![ x ]\!]^\mathsf{B} := [\![ x_1+x_2 ]\!]^\mathsf{B} + [\![ x_3 ]\!]^\mathsf{B}$。两步操作总共增加$1+\log k$轮通信，远少于两倍的交互次数和通信量。

位提取$[\![ x ]\!]^\mathsf{A} \rightarrow [\![ x[i] ]\!]^\mathsf{B}$

$[\![ x ]\!]^\mathsf{A}$转化为二进制时，只需要$O(i)$个$\mathtt{AND}$门和$O(\log k)$轮，在并行前缀加法器中删除了所有不必要的门，逻辑电路只需$2i$个$\mathtt{AND}$门，这可以实现部分优化。

位组合$[\![ x ]\!]^\mathsf{B} \rightarrow [\![ x[i] ]\!]^\mathsf{A}$

转换一个$k$比特长的二进制秘密共享成算术共享，这实际上使用与位分解相同的电路，只是操作顺序略有颠倒。第1、2方输入随机共享$[\![-x_2 ]\!]^\mathsf{B}$，第3方输入随机共享$[\![-x_3 ]\!]^\mathsf{B}$，这是最终秘密共享的一部分，显然前者第1、2方持有，后者第2、3方持有。第1、2方拥有$\text{PRF}$的密钥$\kappa_1, \kappa_2, \kappa_3$，第3方拥有$\text{PRF}$的密钥$\kappa_2, \kappa_3$，可以生成得到$[\![ x_2 ]\!]^\mathsf{B}$。秘密共享定义为$[\![ x_2 ]\!]^\mathsf{B} := (F(\kappa_1, N), F(\kappa_2, N), F(\kappa_3, N))$，$N$是一个公共的随机数。用同样的方法，依次传递角色可以生成共享$[\![ x_3 ]\!]^\mathsf{B}$。每方先用全加器计算$\mathsf{FA}([\![ x[i] ]\!]^\mathsf{B}, [\![ -x_2[i] ]\!]^\mathsf{B}, [\![ -x_3[i] ]\!]^\mathsf{B}) \rightarrow ([\![ c[i] ]\!]^\mathsf{B}, [\![ s[i] ]\!]^\mathsf{B}), i \in \{1, \cdots, k-1 \}$，然后利用并行前缀加法器计算$[\![ x_1 ]\!]^\mathsf{B} := 2[\![ c ]\!]^\mathsf{B}+ [\![ s ]\!]^\mathsf{B}$。在半诚实模型下，可以进一步优化，第2方把$(-x_2-x_3)$作为秘密输入，利用并行前缀加法器计算$[\![ x_1 ]\!]^\mathsf{B} := [\![ x ]\!]^\mathsf{B} + [\![ -x_2-x_3 ]\!]^\mathsf{B}$。无论怎样，向第1，3方揭露$x_1$，最后的秘密共享被定义为$[\![ x_1 ]\!]^\mathsf{A} := (x_1,x_2,x_3)$，需要通信$1+\log k$轮和$k+k\log k$个门。

位插入$[\![ x ]\!]^\mathsf{B} \rightarrow [\![ x ]\!]^\mathsf{A}$

虽然共享算子之间的转换可以任意组合使用，但设计一个自定义协议直接计算$[\![ a ]\!]^\mathsf{A}[\![ b ]\!]^\mathsf{B} = [\![ ab ]\!]^\mathsf{A}$这些组合效率会更高。在逻辑回归和神经网络的训练过程中，激活函数一般是非线性的活着时近似线性的，需要重复上述操作计算线性分段函数或多项式分段函数。这些操作用一个算术共享$a \in \mathbb{Z}_{2^k}$乘以二进制比特共享$[\![ b ]\!]^\mathsf{B}$，并输出一个算术共享$[\![ c ]\!]^\mathsf{A} := [\![ ab ]\!]^\mathsf{A}$。构建这个协议的困难在于，假设在$\mathbb{Z}_2$共享$b \in \{0, 1\}$，即$b=b_1 \oplus b_2 \oplus b_3$，输出结果是在$\mathbb{Z}_{2^k}$上的$c = c_1 + c_2 + c_3 \bmod 2^k$。在半诚实模型下的三方不经意传输(OT)协议，和两方$(1,2)-\text{OT}$一样，也由发送发和接收方组成。另外增加一个不接受任何输出但知道接收方比特选择的辅助方。用函数的方式定义是，有发送方、接收方和辅助方，$((m_0, m_1), c, c) \mapsto (\bot, m_c, \bot)$。ABY3给出了一个信息论安全的方案。发送方和辅助方随机抽样两个串$w_0, w_1 \rightarrow \{0, 1\}^k$，并且两方都知道这两个值。发送方盲化信息$m_0 \oplus w_0, m_1 \oplus w_1$，并把它们发送给接收方。辅助方知道接收方需要的信息$m_c$。辅助方向接收方发送$w_c$，接受方可以恢复出$m_c$，这个过程产生三次交互。
$\qquad$ 此计算一般分两种形式，是十进制公开值或者十进制秘密共享乘二进制共享。对于前者需计算$a[\![ b ]\!]^\mathsf{B} = [\![ ab ]\!]^\mathsf{A}$，$a \in \mathbb{Z}^{2^k}$是一个公开值，$b \in {0, 1 }$是第1方拥有需要共享的比特。第3方发送者取随机数$r \leftarrow \mathbb{Z}^{2^k}$并定义两个消息$m_i := (i \oplus b_1 \oplus b_3)a-r, \text{for}\; i \in \{ 0, 1\}$。第2方接收者输入$b_2$并获得消息$m_{b_2} = (b_2 \oplus b_1 \oplus b_3)a-r = ba-r$。第1方辅助方也知道$b_2$，可以执行上述的三方$\text{OT}$协议。各方利用在本地生成重零共享(Replicated Zero Sharing)$(s_1, s_2, s_3)$去计算$[\![ c ]\!] = [\![ ab ]\!] = (s_1+r, ab-r+s_2, s_3)$。为了实现有效的$(2,3)-$门限共享，第2方把$c_2 = ab-r+s_2$发送给第1方。上述过程产生两轮通信。或者，把第3方作为发送方，多执行一次三方$\text{OT}$协议，把$(i+b_2+b_3)a-r+s_3, \text{for}\ i \in \{0, 1\}$发送给第1方，第1方就在第一轮通信中输入$b_2$得到消息$c_2$。这总共产生$6k$个比特和一轮通信。后者计算$[\![ a ]\!]^\mathsf{A}[\![ b ]\!]^\mathsf{B} = [\![ ab ]\!]^\mathsf{A}$。这种情况并行执行两次$a[\![ b ]\!]^\mathsf{B} = [\![ ab ]\!]^\mathsf{A}$。这种方式$a$不需要公开，第1方就在第一轮通信中输入$b_2$得到消息$c_2$方可以秘密选择$a$，因此表达式可以写成$[\![ a ]\!][\![ b ]\!]^\mathsf{B} = a_1[\![ b ]\!]^\mathsf{B} + (a_2 + a_3)[\![ b ]\!]^\mathsf{B}$。第一轮第1方是发送方，第二轮第3方是发送方，每一轮每方通信大小是$4k$比特。
$\qquad$ 由于第1方可以任意选取$a$的值作为$\text{OT}$的输入，上述半诚实模型不能抵抗恶意攻击。但是为了避免这个情况，需要在$b$的比特串中进行位插入操作。先计算$[\![ b ]\!]^\mathsf{B} \rightarrow [\![ b ]\!]^\mathsf{A}$，然后计算$a[\![ b ]\!]^\mathsf{A} = [\![ ab ]\!]^\mathsf{A}$。每一方可以在本地计算$[\![ b_1 ]\!]^\mathsf{A}, [\![ b_2 ]\!]^\mathsf{A}, [\![ b_3 ]\!]^\mathsf{A}$，这里$[\![ b ]\!]^\mathsf{B} = (b_1, b_2, b_3)$。可以通过模拟算术电路这些值的$\text{XOR}$，先计算$[\![ b_1 \oplus b_2 ]\!]^\mathsf{A} = [\![ d ]\!]^\mathsf{A} := [\![ b_1 ]\!]^\mathsf{A} + [\![ b_2 ]\!]^\mathsf{A} - 2[\![ b_1 ]\!]^\mathsf{A}[\![ b_2 ]\!]^\mathsf{A}$，再计算$[\![ b ]\!]^\mathsf{A} := [\![ d \oplus b_3 ]\!]^\mathsf{A}$。这种变换在两轮通信中发送$2k$比特。每方在本地用$a$乘以$b$的秘密共享，计算得到$[\![ ab ]\!]^\mathsf{A} := a[\![ b ]\!]^\mathsf{A}$。与前面的位分解相比，这种方法将减少通信轮数和通信复杂度到$O(\log k)$。另一种情况，可以重复操作位插入把$[\![ b ]\!]^\mathsf{B}$转换到$[\![ b ]\!]^\mathsf{A}$，然后用乘法协议计算$[\![ a ]\!]^\mathsf{A}[\![ b ]\!]^\mathsf{B} = [\![ ab ]\!]^\mathsf{A}$

联合Yao输入

比特$x$的Yao共享(也叫Garbled Circuit, GC)过程如下，第1方(评估器)持有$k^x_{\mathsf{x}}$，另外两方拥有$k^0_{\mathsf{x}} \in \{0, 1 \}^\kappa$和一个全局随机数$\Delta \in \{ 0, 1 \}^\kappa$使得$k^1_{\mathsf{X}} := k^0_{\mathsf{x}} \oplus \Delta$。GC的转换的一个好吃是双方都知道彼此的输入，比如，第1、2方均知道比特$x$并想得到输出共享$[\![ x ]\!]^\mathsf{Y}$。半诚实模型中，显而易见第2方可以在本地生成$[\![ x ]\!]^\mathsf{Y}$并把它发送给第1方，第1方用它评估GC。在恶意模型中，则需要第1方在不知道$\Delta$下验证$[\![ x ]\!]^\mathsf{Y}$的编码$x$。 第2方生产一个承若(Commitments)哈希值并发给第3方，第2、3方用这同一个随机值生成$\mathsf{Comm}(k^0_{\mathsf{x}}), \mathsf{Comm}(k^0_{\mathsf{x}})$(在第3方眼中这是一个随机数)发送给第1方，并允许第1方检查它的正确性。第1方验证双方相同的承若$\mathsf{Comm}(k^x_{\mathsf{x}})$并解开承若$k^x_{\mathsf{x}}$。这次交互包括两个承诺和一个解除承诺，每次输入比特最多通信一轮。若要共享多个比特(bits)，限制承若的上限是$2\lambda$ ($n \gg \lambda,\; \lambda$是一个统计的安全参数)。 在公布秘密之前，第1方需要接受无承若的标签$k^{x_1}_{\mathsf{x_1} }, \cdots, k^{x_n}_{\mathsf{x_n} }$，并计算这些标签中$\lambda$ 个$(\mathbb{Z}_2)^\lambda$上的随机线性组合 $k^{c_1}_{\mathsf{c_1} }, \cdots, k^{c_\lambda}_{\mathsf{c_\lambda} }$的参数($\mathbb{Z}_2$ 上)。第2、3方接受第1方线性组合并计算$k^0_{\mathsf{x_1} }, \cdots, k^0_{\mathsf{x_n} }$的$\lambda$个组合，从而获得$k^0_{\mathsf{c_1} }, \cdots, k^0_{\mathsf{c_\lambda} }$。 和之前的操作一样，第2、3方发送$\mathsf{Comm}(k^0_{\mathsf{c_i}}), \mathsf{Comm}(k^1_{\mathsf{c_1}}=k^0_{\mathsf{c_i}} \oplus \Delta) \;$ $\text{for} \; i \in \{1, \cdots, \lambda \}$给第1方，其中一方可以用承若的哈嘻值代替。如果第1方验证两个承若集合是相同的，就解开承若$\mathsf{Comm}(k^{c_i}_{\mathsf{c_i}})$，对所有的$i$恢复出$k^{c_i}_{\mathsf{c_i}}$。 第1方收到一个错误的标签，这个测试通过的概率是$2^{-\lambda}$。另一种情况是第2、3方均知道$x$，他们生成$[\![ x ]\!]^\mathsf{Y}$可能不需要通信。利用三方秘密共享之间的随机操作，每方在本地取样$k^x_{\mathsf{x}} \leftarrow \{0, 1 \}^\kappa$，第2、3方定义$k^0_{\mathsf{x}} := k^x_{\mathsf{x}} \oplus (x\Delta)$。

Yao2Binary, $[ \![ x ]\!]^{\mathsf{Y}} \rightarrow [ \![ x ]\!]^{\mathsf{B}}$

ABY文章称，密钥相当于一组序列比特，它的LSB(最低有效位)形成$x$的两方共享，即$x \oplus p_{\mathsf{x}} = k^x_{\mathsf{x}}[0]$，这里$p_{\mathsf{x}} = k^0_{\mathsf{x}}[0]$。 第3方知道$p_{\mathsf{x}}$ 即是持有 $k^0_{\mathsf{x}}[0]$。第1，2方本地计算另外一个随机比特$r$，第1方发送$k^x_{\mathsf{x}}[0] \oplus r = x \oplus p_{\mathsf{x}} \oplus r$给第3方。这就生成了三方复制共享$[ \![ x ]\!]^{\mathsf{B}} = (x \oplus p_{\mathsf{x}} \oplus r, r, p_{\mathsf{x}})$，在这一次交互中，只产生一个比特的通信。恶意模型中，第3方验证第1方发送过来的比特位$x \oplus b \oplus r$，用以确保第1方使用了$b = p_{\mathsf{x}}$。第1、2方取样$k^r_{\mathsf{r}} \leftarrow \{0, 1 \}^\kappa$，第2方发送$k^0_{\mathsf{r}} := k^r_{\mathsf{r}} \oplus (r \Delta)$给第1方。 第2、3方均发送承若$C_0 = \mathsf{Comm}(k^{p_\mathsf{x}}_\mathsf{y}),\;$ $C_1 = \mathsf{Comm}(k^{p_\mathsf{x}}_\mathsf{y})$ 给第1方，这里$k^0_{\mathsf{y}} := k^0_{\mathsf{x}} \oplus k^0_{\mathsf{r}}$。 第1方发送$k^{x \oplus r}_{\mathsf{y}} := k^x_{\mathsf{x}} \oplus k^r_{\mathsf{r}}$给第3方，并且由第3方验证这个值是否在集合$\{ k^0_{\mathsf{y}}, k^1_{\mathsf{y}} \}$中。第1方验证承诺$C_{p_{\mathsf{x}} \oplus x \oplus r }$并解开承若$k^{x \oplus r}_{\mathsf{y}}$，还验证第2、3方发送过来的$C_0,C_1$是否相同。显然$p_\mathsf{x} \oplus x = k^x_\mathsf{x}[0]$，每方都可以计算三方共享$[\![ x ]\!]^\mathsf{B} = (x \oplus p_\mathsf{x}) \oplus r, r, p_\mathsf{x}$。 第3方为$k^{x \oplus r}_\mathsf{y}[0] \oplus p_\mathsf{r}$计算$x \oplus p_\mathsf{x} \oplus r$。这个转换经历两次通信，最后秘密共享分块$[\![x ]\!]^\mathsf{B}$的计算需要一轮通信。因此，第一轮之后可以使用秘密分块$[\![x ]\!]^\mathsf{B}$，只要不泄露随机数。如果验证失败，各方中止协议。

Binary2Yao $[\![ x ]\!]^{\mathsf{B}} \rightarrow [ \![ x ]\!]^{\mathsf{Y}}$

令$[\![ x ]\!]^{\mathsf{B}} = (x_1, x_2, x_3)$，每方使用联合Yao输入共享$[\![ x_1 ]\!]^{\mathsf{B}}, [\![ x_2 ]\!]^{\mathsf{B}}, [\![ x_3 ]\!]^{\mathsf{B}}$。 最终的共享可以用乱码电路来计算这三个值的XOR，即$[\![ x ]\!]^{\mathsf{Y}} := [\![ x_1 ]\!]^{\mathsf{Y}} \oplus [\![ x_2 ]\!]^{\mathsf{Y}} \oplus [\![ x_3 ]\!]^{\mathsf{Y}}$。利用$\text{free-XOR}$，使得各方之间无需任何通信，可以由第1方在本地计算。 半城市模型中，第2方知道$x_2$和 $x_3$，可以在本地计算$x_2 \oplus x_3$，并将$[\![ x_2 \oplus x_3 ]\!]^{\mathsf{Y}}$发送给第1方，第1方可以在本地计算$[\![ x ]\!]^{\mathsf{Y}} := [\![ x_1 ]\!]^{\mathsf{Y}} \oplus [\![ x_2 \oplus x_3 ]\!]^{\mathsf{Y}}$。
Yao共享转算术共享$[\![ x ]\!]^{\mathsf{Y}} \rightarrow [ \![ x ]\!]^{\mathsf{A}}$

把$x \in \mathbb{Z}_{2^k}$从Yao共享转成算术共享，首先需要把把Yao共享转换成二进制共享，然后执行位组合或位插入(单比特)协议。由于输入的是Yao共享形式，为CRFA加法电路(文章未说明)选择三方计算的Garbled Circuit。 第1、2方取样$x_2 \leftarrow \mathbb{Z}_{2^k}$，第2、3方取样$x_3 \leftarrow \mathbb{Z}_{2^k}$，然后用上述方法进行联合输入。然后使用GC计算$[\![ x_1 ]\!]^{\mathsf{Y}} := [\![ x ]\!]^{\mathsf{Y}} - [\![ x_2 ]\!]^{\mathsf{Y}} - [\![ x_3 ]\!]^{\mathsf{Y}}$，并发送共享给第1、3方。$[\![ x_1 ]\!]^{\mathsf{A}} := (x_1, x_2, x_3)$形成了$x$新的算术共享。这需要通信$k$个联合输入比特(只有$x_2$)和$2k$混淆门。半诚实模型中，第3方在本地计算$x_2+x_3$ 并将它作为输入计算$[\![ x_1 ]\!]^{\mathsf{Y}} := [\![ x ]\!]^{\mathsf{Y}} - [\![ x_2 + x_3 ]\!]^{\mathsf{Y}}$，因此，乱码电路的成本降低了一半。
算术共享转Yao共享$[\![ x ]\!]^{\mathsf{A}} \rightarrow [ \![ x ]\!]^{\mathsf{Y}}$

每方联合输入$[\![ x_1 ]\!]^{\mathsf{A}} = (x_1, x_2, x_3)$的共享并生成$[ \![ x_1 ]\!]^{\mathsf{Y}}, [ \![ x_2 ]\!]^{\mathsf{Y}}, [ \![ x_3 ]\!]^{\mathsf{Y}}$。然后用一个GC来生成$[ \![ x ]\!]^{\mathsf{Y}} := [ \![ x_1 ]\!]^{\mathsf{Y}} + [ \![ x_2 ]\!]^{\mathsf{Y}} + [ \![ x_3 ]\!]^{\mathsf{Y}}$。半诚实模型中，第2方本地计算$ x_2+x_3 $，并发送给第1方，第1方便用其计算 $[ \![ x_2 + x_3 ]\!]^{\mathsf{Y}}$，最终计算共享$[ \![ x ]\!]^{\mathsf{Y}} := [ \![ x_1 ]\!]^{\mathsf{Y}} + [ \![ x_2 + x_3 ]\!]^{\mathsf{Y}}$。