Trident：针对隐私保护机器学习的4PC框架

Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning

• Abstract

• Introduction

• Preliminaries and Definitions

• 4PC Protocol

• Sharing Semantics

• Building Blocks

• States of 4PC Protocol

• Achieving Fairness

• Mixed Protocol Framework

• The Garbled World

• Building Blocks

• Sharing Conversions

• Privacy Preserving Machine Learning

• Sharing Truncation

• Secure Comparison

• Activation Functions

• Communication Cost

• Implementation and Benchmarking

• Secure Training

• Secure Prediction

• Conclusions

• References

今天给大家带来的是发表于NDSS'20上的文章Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning

原文链接: https://arxiv.org/pdf/1912.02631.pdf

Abstract

本文提出环上遵循离线-在线范式的具有主动安全的四方隐私保护机器学习框架Trident, 可抵抗一个恶意敌手, 同时还实现了公平性(Fairness). 与三方的ABY3相比, 本文通过在离线阶段引入一个额外诚实方, 并尽可能少地使用昂贵的电路来提升效率, 例如截断技术不影响乘法的在线开销, 离线阶段不需要任何电路, 而在线阶段则只涉及三方计算; B2A转化在通信轮次上有7倍改进, 通信复杂度有18倍改进. 本文所提出的混合计算协议支持秘密份额在Arithmetic、Boolean、Garbled World上进行高效转换, 而且具有恒定的轮复杂度, 适合安全外包计算场景. 最后本文与ABY3在64比特环上就LAN和WAN设定进行了实验对比, 发现训练阶段快187倍, 推理阶段快158倍.

Introduction

尽管MPC效率得到了提升, 但最好的MPC协议并不能直接应用于PPML, 主要原因如下:

1. 不同的MPC技术在算术、布尔、Yao世界中的效率各不相同, 单一世界可能更适合某些类型的计算, 因而在混合世界中执行协议比在单一世界中执行更高效.
2. 非线性算子的计算问题. 当进行多次定点乘法后, 定点数精度会造成溢出, 为此需要进行定点截断, 在2PC下可以使用SecureML中的本地截断, 但在3PC/4PC下存在ABY3中所描述的攻击, 此外ABY3的方法依赖于开销较大的Ripple Carry Adder来构造协议, 因此需要探索更有效的定点截断技术. 此外, 激活函数的计算问题也是影响MPC效率的一大原因.

总的来说, 本文的主要贡献如下:

1. 高效4PC协议: 提出了一个环上具有主动安全的高效四方计算协议, 遵循离线-在线范式, 在线阶段每次乘法计算仅通信3个环元素且不需要第四方参与计算. 此外, 还在不影响乘法门复杂度的前提下实现了公平性.
2. 快速混合世界计算: 本文提出的Trident框架可在算术、布尔、Garbled World之间相互转换, 协议构造侧重于在线阶段的高吞吐量, 主要通过额外的诚实的第四方来达到, 与ABY3相比更高效.
3. 高效截断: 本文提出的截断协议可与本文的乘法协议结合使用, 在线阶段无需额外开销, 且不需要像ABY3一样借助RCA来构造, 效率更高.
4. 安全比较: 本文提出的安全比较协议具有常数轮复杂度.
5. 机器学习模块: 本文提出的激活函数安全计算协议具有常数轮复杂度.
6. 实验: 在LAN和WAN下与ABY3在线性回归、逻辑回归、神经网络、卷积神经网络的训练和预测等几个方面进行了性能测试, 结果如下:

Preliminaries and Definitions

符号约定: 四方集合, 同步网络, 通过点对点安全信道连接. 抗碰撞哈希函数.

为减少通信开销生成共同随机性, 参与方通过预共享密钥设置建立PRF使用的预共享随机密钥来生成相关随机性.

4PC Protocol

Sharing Semantics

设秘密为, 计算域为布尔环和算术环. 本文涉及三种不同的Sharing:

• -sharing: 三方下的加法秘密共享(ASS), 的份额为, 满足.
• -sharing: 三方下的复制秘密共享(RSS), 的份额为, 的份额为, 的份额为, 满足.
• -sharing: 四方下的秘密共享, 存在, 使得, 其中通过-sharing共享, 则有明文形式的. 最终的份额为, 的份额为, 的份额为, 的份额为. 记为的份额.

不同秘密共享下各参与方份额总结如下:

以上秘密共享方案都满足线性性, 因此计算线性算子不需要交互.

Building Blocks

• 秘密分发协议: 允许分发他拥有的秘密, 使得参与方得到. 离线阶段不需要通信, 在线阶段需要1轮, 比特均摊通信量. 具体协议过程如下:

• 秘密分发协议: 特别地, 可在离线阶段分发他的秘密, 生成. 需要1轮通信, 比特均摊通信量. 具体协议过程如下:

• 秘密重构协议: 给定, 中的参与方重构. 每个参与方从另一方接收所缺失的份额并从第三方接收该缺失份额的哈希值以验证一致性. 在线阶段需要1轮, 比特均摊通信量. 具体协议过程如下:

States of 4PC Protocol

4PC协议可分为输入共享(Input Sharing)、求值(Evaluation)、输出重构(Output Reconstruction)三个阶段. 输入共享阶段主要是通过秘密分发协议来执行, 输出重构阶段主要是通过秘密重构协议来执行, 下面主要介绍求值阶段, 因为加法门可以本地计算, 因此这里仅介绍计算乘法门的协议, 即给定, 安全计算, 其中.

离线阶段的主要任务是让生成的RSS份额. 首先本地计算, 然后通过resharing交换份额得到. 在交换的份额之前, 为防止泄漏, 参与方需要在份额上加入Zero sharing的份额. 此外, 辅助其他参与方验证收到的份额的正确性. 在线阶段的目标是计算, 因为

可以本地计算的份额, 然后交换份额重构. 由于-sharing的特性, 每个缺失的份额都可被两方计算, 因此各参与方通过让一方发送缺失的份额, 另一方发送与之对应的哈希值, 以可验证的方式重构出. 一个关键的优化点是, 每个乘法门交换哈希值可以推迟到输出重构阶段合并进行, 所有相对应的值并在一起再计算哈希值, 从而可将整体通信量减少为3个环元素. 完整的乘法计算协议如下, 离线阶段需要1轮, 比特均摊通信量, 在线阶段需要1轮, 比特均摊通信量.

Achieving Fairness

公平性要求所有参与方要么都得到输出, 要么都中止协议. 因此实现公平性需要确保所有参与方在输出重构阶段都是alive的, 同时还需要阻止敌手发起选择中止攻击(selective abort attack), 即敌手让某些诚实参与方中止协议. 若乘法门验证通过, 设定比特, 否则设定, 然后发送给. 若发现某个参与方发送了abort, 则向所有参与方发送abort, 从而确保所有参与方aliveness. 剩余的参与方然后交换他们来自的回复(continue/abort), 根据其中的多数来决定继续还是中止. 因为仅有一个恶意方, 因此所有参与方将在同一状态下, 从而防止敌手发起选择中止攻击. 若参与方决定继续, 则他们交换缺失的份额. 基于至多只有一个恶意方的事实和秘密共享方案的构造, 收到次数最多的缺失份额将在诚实参与方中保持一致性. 完整的公平重构协议如下, 在线阶段需要4轮, 比特均摊通信量.

Mixed Protocol Framework

混合协议框架主要考虑三个世界: Arithmetic world (A)、Boolean world (B)、Garbled world (G).

The Garbled World

对于混淆世界, 将3PC的MRZ协议(CCS'15)扩展到4PC. 在4PC下, 作为混淆方, 作为求值方. 作为优化, 可以只分享他的输入给, 而不是所有方. 对于交叉检验, 发送混淆电路给, 同时发送与之相对应的哈希值给. 同时方案整合了Free-XOR、half-gate、fixed-key AES garbling技术. 本文提供了单比特的协议, 可以通过并行次来支持比特的值.

• 秘密共享语义: 对于比特, 被定义为, , 和, 其中是计算安全参数, 是由通过预分享随机性生成的最后一比特(最低位)为1的全局偏移量, 且是所有-sharing中共有的. 容易证明, . 简单起见, 当时, 用表示的每个比特的份额的集合.

• 输入共享: 输入共享协议使得生成. 在协议中, 需要确保得到正确的. 为此, 需要让混淆方向承诺混淆电路的密钥, 然后通过交叉验证所收到的承诺来验证正确性. 具体过程如下:

若, 则采样随机比特, 计算, 分别发送给. 然后参与方分别执行和, 分别得到和. 然后参与方通过free-XOR技术本地计算. 此时承诺的密钥不需要置换, 因为已知和. 作为优化, 的计算可以转移到离线阶段.

• 输出重构: 若, 则发送他们份额的最后一比特给, 然后验证所收到的值是否相同. 若是其中一个混淆方, 则发送它的份额为. 由于底层混淆电路的可靠性(authenticity), 腐化的不能发送错误的份额给. 若面向有多个重构, 则可以发送它份额的最后一比特连同所有相应份额的哈希值.

• 基本算子: 设通过-sharing秘密共享, 持有份额. 令表示输出.

• XOR: 参与方本地计算;
• AND: 离线阶段, 采样随机, 计算, 然后构造AND门的混淆表. 发送混淆表给, 同时发送表的哈希值给. 在线阶段, 对电路进行求值, 得到. 对, 设定.

Building Blocks

• 可验证的算术/布尔份额: 协议允许以可验证的方式生成. 简单来说, 执行, 同时发送给辅助验证. 具体过程如下图7, 离线阶段不需要交互, 在线阶段需1轮, 至多比特均摊通信量. 若都已知, 则可令和, 从而让参与方不需要交互即可生成.

• 可验证的Garbled Sharing: 协议允许以可验证的方式生成. 当都是混淆方时, 其中一方可以发送密钥, 同时另一方发送相对应的哈希值以检测一致性. 若, 则依序发送密钥的承诺给. 此外, 发送实际密钥的解承诺给. 具体协议过程如下图, 离线阶段不需要交互, 在线阶段需要1轮, 均摊通信量为比特.

• 点积计算协议: 给定长度为的向量, 计算. 协议的构造思路与乘法协议类似, 为了让通信开销独立于向量长度, 对于, 在线阶段不逐个重构, 参与方本地将所有乘积结果累加在一起然后只通信一次, 从而减少倍的通信开销. 具体协议过程如下, 离线阶段需要1轮, 均摊通信量为比特, 在线阶段需要1轮, 均摊通信量为比特.

Sharing Conversions

• Garbled to Boolean Sharing (G2B): 离线阶段, 首先使用预共享随机性生成随机值, 然后分别生成. 此外, 他们还通信计算两比特XOR的混淆电路及其解码信息给. 在线阶段, 进行求值得到, 并发送结果及其相应密钥的哈希值给. 混淆电路的可靠性保证了腐化的不能发送错误的比特, 因为它无法猜中与之对应的密钥. 具体转换过程如下:

• Garbled to Arithmetic Sharing (G2A): 与G2B类似, 主要的不同之处在于将混淆电路的XOR变为两个比特数的加减法电路计算. 具体转换过程如下:

• Boolean to Garbled Sharing (B2G): 由于在布尔世界中, 比特, 若参与方可得到和, 则可以通过free-XOR技术本地计算. 具体转换过程如下:

• Arithmetic to Garbled Sharing (A2G): 类似于B2G, , 参与方调用可验证地生成和的混淆份额. 在线阶段, 参与方对混淆减法电路进行求值得到的份额. 具体转换过程如下:

• Arithmetic to Boolean Sharing (A2B): 类似于A2G, 主要的不同之处是参与方生成和的布尔份额, 并对比布尔减法电路进行求值计算的布尔份额. 具体转换过程如下:

• Bit to Arithmetic Sharing (Bit2A): 计算. 设分别表示在环上的比特. 根据, 在离线阶段生成. 为了确保份额的正确性, 检验是否满足等式, 其中表示比特在环上的对应值. 通过验证后, 参与方本地转换为. 在在线阶段, 参与方计算和的秘密份额乘积, 然后本地计算. 需要注意的是当执行时, , 所以计算乘法时不需要的份额. 具体转换过程如下:

• Boolean to Arithmetic Sharing (B2A): 利用事实, 其中代表环上的值的第比特. 可利用关系, 其中分别表示环上的比特和.

  B2A的离线阶段与Bit2A类似, 具体转换过程如下:

• Bit Injection (BitInj): 计算. 在环上, 令, . 类似地, 令,,,, 则.

  在离线阶段, 生成和, 其中表示环上的比特. 检验的方法与相同, 检验的方法是计算. 在线阶段, 参与方通过执行本地计算, 最后参与方本地累加份额得到. 具体转换过程如下:

不同转换协议的通信轮次和通信量与ABY3之间的对比如下, 其中表示2输入减法混淆电路, 表示2输入减法混淆电路及其解码信息, 类似地定义, .

Privacy Preserving Machine Learning

使用上的有符号补码(signed two's compliment)来表示运算中涉及的十进制数, 其中最高位(MSB)是符号位, 最后位表示小数部分.

Sharing Truncation

与ABY3的概率截断方法类似: 首先生成随机截断对, 其中是的截断值, 则的截断值可以通过首先恢复再截断为, 最后加上得到, 即. 不同之处在于本文没有使用任何布尔电路, 从而将离线阶段轮复杂度改进为常数轮. 首先参与方非交互地生成, 使得得到. 然后生成, 利用关系(带余除法)来验证所生成的份额正确性, 其中表示的最后比特. 具体份额截断协议如下:

正确性: 协议的离线阶段, 若腐化生成了错误的份额, 则中止.

证明: 只需证明, 其中, . 注意到, 所以有

Secure Comparison

给定的算术共享份额, 计算的布尔共享份额. 在定点表示形式下, 最简单的方式是计算最高位. 为此可以通过构造比特抽取协议来完成. 本文中的比特抽取协议与ABY3类似. 离线阶段生成的布尔份额, 在在线阶段生成的布尔份额. 然后参与方使用ABY3的优化的Parallel Prefix Adder (PPA)进行求值计算得到最高位的布尔份额.

Activation Functions

• ReLU: , 其中比特. 因此参与方首先调用得到, 本地计算. 最后调用计算.
• Sigmoid: 使用SecureML中的分段近似函数来计算Sigmoid函数. 此时, 其中, . 类似于计算ReLU的方法进行求解, 但需要额外调用一次, 和.
• Softmax: 使用SecureML中提出的变体来近似: . 除法则通过A2G和除法混淆电路来计算.

Communication Cost

以上机器学习相关的协议通信轮次和通信量与ABY3之间的对比如下:

Implementation and Benchmarking

实验部分主要与ABY3的方案进行了比较, 实验内容为线性回归、逻辑回归、神经网络和卷积神经网络.

Secure Training

性能基准是LAN下计算每秒钟的迭代次数, WAN下计算每分钟的迭代次数.

• 线性回归: LAN/WAN设定下与ABY3对比如下

• 逻辑回归: LAN/WAN设定下与ABY3的对比如下

• 神经网络: LAN/WAN设定下与ABY3的对比如下

Secure Prediction

以在线阶段的时延(Latency)作为基准, 结果如下:

LAN下在线吞吐量(每秒钟预测次数)和WAN下在线吞吐量(每分钟预测次数)与ABY3在不同数据集下的对比如下:

Conclusions

Trident是一个遵循离线-在线范式的四方机器学习框架, 可抵抗1个恶意敌手. 与ABY3相比, Trident在离线阶段引入一个额外的计算方, 在构造协议时尽可能少地应用昂贵的电路, 在线阶段则主要是三方计算. 所提出的方案支持不同世界的份额之间相互转化, 同时还实现了Fairness. 非线性算子的安全计算协议在线阶段通信轮次均为常数轮. 从实验结果综合来看, Trident与ABY3相比具有明显的优势.

References

[1] P. Mohassel and P. Rindal, “ABY3: A Mixed Protocol Framework for Machine Learning,” in ACM CCS, 2018.

译者简介：

魏伟明, 应用数学硕士, 目前在广州大学数学与信息科学学院攻读博士学位, 主要研究方向为: 安全多方计算在隐私保护机器学习领域中的应用. 知乎: @云中雨雾.

往期内容：

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群