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}}\)。