隐语小课｜两方安全计算 ABY2.0 高效的 2PC 协议
“隐语” 是开源的可信隐私计算框架，内置 MPC、TEE、同态等多种密态计算虚拟设备供灵活选择，提供丰富的联邦学习算法和差分隐私机制。
代码开源：
一、介绍
ABY2.0 定义了新的 sharing，扩展两输入乘法门到多输入乘法门，且其 online 阶段通信量与输入个数无关。在此基础上，构造了各种高效的原语，如内积、矩阵乘、比较、最大 / 小池化、相等判断等。
ABY2.0 与 ABY 均是在半诚实模型下的两方安全计算框架，分为 setup 和 online 阶段，ABY2.0 相比 ABY 提高了 online 阶段的效率。
二、更高效的 2PC
ABY2.0 与 ABY 的区别在于 Arithmetic Share 和 Boolean Share，而 Yao Share 并无区别。
Boolean Share 的技术与 Arithmetic Share 一致，只是环
和
的区别，本文只介绍 Arithmetic Share。
1、Sharing Semantics
：对于
，有
，
持有
：对于
，有
，
，
可结合下图理解：
ABY 用的是 []-sharing，ABY2.0 用的是 <>-sharing。
并且，<> 可以本地转换为 []，比如使
[] 转换为 <> 需要通信，是通过之后讲述的 Sharing Protocol 来实现的。
论文中某些计算就是通过把 <> 转换为 [] 后，采用之前的方法计算，而后直接或者变相把 [ ] 转换为 < >。
2、Sharing Protocol
Setup 阶段：
生成随机数
共同生成随机数
，因此，
知道值
。
Online 阶段：
3、Reconstruction Protocol
Online 阶段：
4、Additional Protocol
Online 阶段：
5、Multiplication Protocol
setupMULT 协议用来生成乘法三元组，即根据
生成
，并且满足
，有基于 OT 和 HE 两种方式，细节见论文。
6、High level overview of Multiplication Gate
上面左图中是 ABY 中的 MULT，对输入 [a]、[b] 使用随机数 mask 后，调用 Reconstruction 协议恢复出
然后求结果 [c]。
上面右图中是 ABY2.0 中的 MULT，
变为已知，本地计算即可求出 [c]，调用 Reconstruction 协议恢复出
，从而求出 <c>。
新 MULT 明显的优点是通信量减半，缺点是乘法三元组需要根据具体的电路结构提前生成好，而不能再随便取一个乘法三元组来计算了。
7、Multi-Input Multiplication Protocol
公式的推导如下图：
Setup 阶段：需要生成四个 [ ]-sharing，其中的 setupMULT3 与 setupMULT 类似。与 MULT 相比较，生成的 sharing 个数从 1 变为了 4。
Online 阶段：优点是 Constant Communication。
Setup 阶段：需要生成 11 个 [ ]-sharing，已经有点夸张了。
Online 阶段：优点依然是 Constant Communication。
由 MULT3 和 MULT4 可看出，对于多输入乘法，Online 阶段的通信量始终是 Constant，只是 Setup 阶段的预计算量会呈指数增长
。
三、更高效的 ABY Share 转换
在大多数转换协议中，ABY 需要在 online 阶段调用 OT 操作，而 ABY2.0 只需在 setup 阶段调用 OT 操作，因此提高了效率。转换协议细节见论文，此处略去。
更高效的基本操作
在前述协议的基础上，文中构建了多个高效的基本操作。高效的原因有两点：
新形的 sharing 允许合并一些计算与通信
使用 Multi-input MULT/AND Gate 可以减少电路层数
简要介绍如下：
1、Scalar Product
与单个 MULT 类似，内积其实是执行了多个 MULT，并且合并
使得只需一次通信即可。
2、Matrix Multiplication
Setup：使用 setupMULT 生成矩阵相乘时两两元素的乘法三元组，在此基础上构造出结果矩阵的 []-shares。
Online：对于 p*q 矩阵与 q*r 矩阵的乘法，结果矩阵的维度是 p*r，通信量是 O (pr)，相比之前协议的 O (pqr) 有了很大的提升。
3、Depth-Optimized Circuits
通过使用多输入门可以减少电路层数。
上图中的 8-bit PPA 加法器，通过使用 MULT3/MULT4，从 3 层电路变为了 2 层电路。64-bit 电路、求最高位电路与此类似。
4、Comparison
为求
，先计算
，转换
，再把
通过 Share Protocol 转换为
，然后就可以使用 Depth-optimized Circuits 中的求最高位电路。
5、Truncation
<>-sharing 转换为 []-sharing，使用论文 SecureML 中的本地截断方法，然后再转回 < >-sharing。
6、MAX2/MIN2
使用了 Comparison。
7、MAX3/MIN3
使用了 Comparison。
8、Non-linear Activation Functions
ReLU 使用了上述的 MAX: ReLU (v) = max (0, v)
Sigmoid 用了分段函数：
9、Maxpool and Minpool
使用了 MAX3/MIN3 构造三叉树，来减少树的层数。
10、Equality Testing
对两操作数先求异或，再对所有位执行与操作。
使用了 AND4 gate（AND4 即为
下的 MULT4）来减少树的层数。
四、性能
文中测试了 LR 与 NN 的性能，与 SecureML 做了对比，性能有大幅提高，如下图：
五、与 Cheetah 对比
总之，ABY2.0 与 Cheetah 都是高效的半诚实两方协议，实现技术不同，目标也不同，有点类似于 CPU 与 GPU 的对比。
六、总结
ABY2.0 具有以下优缺点，其预计算过程需事先知道要计算的函数，这是使用时需要注意的地方。
优点：
Constant online cost of 2 ring elements for N-input MUL/AND Gates
Better mixed protocol conversions
Set of efficient building blocks
缺点：
Function-dependent preprocessing
More complicated preprocessing
七、参考文献
ABY2.0
https://www.usenix.org/system/files/sec21summer_patra.pdf
ABY2.0_slides
https://www.usenix.org/system/files/sec21_slides_patra.pdf
Cheetah
https://www.usenix.org/system/files/sec22-huang-zhicong.pdf
隐语社区：
隐语官网：https://www.secretflow.org.cn
👇欢迎关注：
公众号：隐语的小剧场
B 站：隐语 secretflow
邮箱：secretflow-contact@service.alipay.com
关注微信公众号：隐语的小剧场 2022-08-01 加入
隐语SecretFlow是蚂蚁自主研发的隐私计算开源框架，内置MPC、TEE、同态等多种密态计算虚拟设备供灵活选择。同时我们专注于隐私计算领域任何前沿技术、最新动态、行业资讯，隐语期待您的加入！
评论