Tetrad: 面向安全训练和推理的主动安全四方计算

本文在诚实大多数假设下提出了一个环上抵抗1个恶意敌手的四方计算框架Tetrad, 所提出的两种变体Tetrad, Tetrad-R可以分别达到公平性(Fairness)和输出可达性(Guaranteed output delivery, GOD)/鲁棒性(Robustness). Tetard通过改进Trident的方案实现Fairness, 实现Fairness的乘法协议只需通信5个环元素. 而Tetrad-R实现GOD几乎是免费的, 通过改进SWIFT和Fantastic Four的方案实现GOD. 这两种变体的其他亮点有: (a)无开销的概率截断; (b)多输入乘法协议; (c)通过专用的混淆电路, 支持算术/布尔计算域之间的相互转换, 2同时用于安全训练和安全推理. 实验部分, 在LeNet, VGG16等DNN中进行了性能测试, 发现Tetrad在ML训练速度提高了6倍, 在ML推理中速度提高了5倍. Tetrad在实际部署中所需的货币成本也比Trident低6倍.

Main Contributions

1. 通过并行化来支持按需计算, 这在依赖于函数的预处理模型中通常是不可能的;
   
   
2. 首次在公平性和输出可达性的前提下实现无开销的概率截断;
   
   
3. 可以一个在线通信轮次内计算3输入和4输入的乘法, 与2输入乘法相同, 而以往的方案需要两个轮次;
   
   
4. 大多数基于MPC的PPML框架中的大部分计算都在算术世界和布尔世界中完成的, 而混淆世界仅用于在算术/布尔世界中代价高昂的非线性算子的计算(如SoftMax), 然后需要将混淆输出再转换回其他两个世界, 为了进一步优化这个过程, 本文提出了4PC混合协议框架, 可在计算域与专用的基于混淆电路的端到端转换协议, 使混淆世界的输出直接变为其他世界的输出, 从而减少所需的通信量和轮数.
   
   

1. 安全训练: 数据所有者将数据通过秘密共享外包给服务器, 由服务器进行MPC训练模型, 最后向数据所有者重构经过训练的模型.
2. 安全推理: 模型所有者在服务器之间秘密共享一个预先训练的模型, 客户端在服务器之间秘密共享其查询, 服务器通过MPC进行安全推理, 并将输出重构给客户端.

Sharing Semantics

一些符号: . 表示布尔份额, 表示混淆份额, 没有上标表示算术份额.

Primitives

• Joint-Send/jsnd: 允许将信息转发给进行验证, 当传递的信息不一致时输出. 具体做法是, 发送, 发送, 使用Hash验证的结果是否为发送的信息, 若一致则接受, 否则发出中止信号. 为均摊开销, Hash的结果可以在协议结束后将信息组合在一起发送一次来均摊通信开销.
• Joint-Send for robust protocols: 为实现鲁棒性, Tetrad同时借鉴了Fantastic Four和SWIFT的做法: 当发现信息不一致时, 会建立一个至多有两方的参与方集合, 其中必有一个参与方是被敌手腐化的, 这意味着剩下的两方都是诚实的, 因此让其中一方作为TTP()进行相关明文计算.  jsnd包含两个阶段: 发送阶段(send)和验证阶段(verify). 验证阶段只在协议结束后执行一次以均摊通信开销. 具体协议过程如下, 均摊的通信开销为比特, 2轮.
  
  

• Sharing: 协议允许生成的份额. 具体协议见图1, 当参与方发现接收到的信息不一致时, 根据公平性和鲁棒性的要求, 具体处理方式略有不同, 参与方输出以实现公平性, 参与方使用一个默认值以实现鲁棒性. 在线阶段均摊通信开销: 至多比特, 1轮.

• Joint Sharing: 协议允许联合生成的份额, 与不同的是, 在线阶段的最后部分需要调用jsnd发送给. 特别地, 若与另一方联合生成的份额, 则可以进一步优化通信, 具体来说,

• :  选取; 令; 调用jsnd发送给.
• :  选取; 令; 调用jsnd发送给.
• :  选取; 令; 调用jsnd发送给.
  
  

• Reconstruction: 协议输入, 参与方得到. 因为一个参与方缺失的份额都由其余三方持有, 三方中任意两方通过jsnd发送所需份额即可重构秘密. 具体协议过程如下, 在线阶段均摊通信开销为比特, 1轮.

• - 生成0的ASS份额(Zero sharing): 对于, 使得到, 满足. 与ABY3一样, 可以通过预分享密钥结合PRF来生成. 对, 通过预分享密钥和PRF选取随机, 份额定义为, , .

• Multiplication : 给定, 生成, 其中, 有明文的. 原理与ABY3中的RSS乘法一致, 结合zero sharing即可计算, 而resharing则通过调用jsnd来实现. 协议过程如下:

Achieving Fairness

Achieving Robustness

• Fairness: 为了实现公平重构协议, 参与方首先需要进行一次aliveness check. 然后按照如下方法重构. 首先, 发送和给. 若混淆方从处收到了一致的, 满足存在, 使得, 且, 则使用计算, 并发送给与其协作的混淆方. 否则混淆方接受从协作混淆方收到的作为输出. 由此混淆方对输出的进一步传播可以确保所有各方都保持一致. 如果混淆方接收到输出, 则对进行的重构. 为此, 所有接收输出的混淆方将解码信息发给, 选择多数值来重构.
  
  
• GOD: 为实现鲁棒性, 与公平协议的主要不同如下: 首先, 需要使用鲁棒的jsnd. 其次, 在输入共享协议中, 只有混淆方有, 腐化的可能不会向提供正确的密钥(作为承诺的打开信息发送). 为了确保达到鲁棒性, 如果未能从收到正确的密钥, 则让发送不一致比特给所有参与方. 所有参与方交换该不一致比特, 并接受其中的多数值. 若所有参与方都确认了存在不一致, 则确定中存在腐化方, 令作为TTP进行剩下的计算. 为了确保鲁棒重构, 采用以下方法: 观察到只要是诚实的, 公平的重构就提供了鲁棒性. 如果没有混淆方获得公平协议中输出, 则可以确认是腐化方, 在这种情况下, 各方选取作为TTP进行相关计算并重构输出实现鲁棒性.

2GC Variant

• 输入阶段: 给定函数输入的秘密份额形式, 布尔值, 其中和, 作为混淆计算的新输入, 为这些值生成形式的混淆份额. 的语义确保在每个混淆实例中有两个混淆方持有. 面向份额的密钥要么调用jsnd正确地发送给了评估方, 要么检测出不一致. 这种密钥交付实质上为这三个值的每一个生成了-sharing, 从而让GC评估. 因此, 输入阶段的目标是对于要通过GC评估的函数的每个输入建立组合份额. 下面先讨论-sharing的语义, 然后说明生成-sharing的步骤.
  
  
• 混淆份额语义: 秘密在中是-shared, 若拥有, 拥有, 拥有. 这里, 对, , 是中的混淆方已知的信息, 代表最后一比特为1的全局偏移量且电路中的每根导线都相同. 被称为-shared (compound shared), 若来自的每个值, 都通过上述-shared定义. 记.
  
  
• 生成和: 下图中的协议可以生成, 在每个混淆实例中两个混淆方持有, 处理方式如下: 考虑第一个混淆实例, 评估方为, 混淆方持有. 中的混淆方生成代表导线上的密钥, 遵循free-XOR技术. 调用jsnd发送给. 第二个混淆的实例类似处理, 最后中的混淆方生成, 持有. 如此, 拥有的定义为, , .

  为了生成, 给定, 需要生成. 为此, 可以对每个调用.

Evaluation phase

Output phase

Optimizations

Security

• Fairness: 首先确认所有参与方都仍在参与协议, 若是, 则按图19中的协议进行公平重构计算, 但主要的不同是: 对于向评估方的重构, 所有三个混淆方发送各自解码信息给评估方. 评估方选择出现最多的值进行重构; 对于向混淆方的重构, 评估方发送输出密钥的最低位及其哈希值给混淆方, 由于至少存在一个评估方是诚实的, 因此混淆方将保持一致.
  
  
• GOD: 与Fairness最主要的不同是, 使用了鲁棒的jsnd原语来保证当检测到恶意行为时识别出一个诚实方进行相关计算并向所有参与方输出计算结果.

2GC与1GC的开销对比:

Conversions involving Garbled World

• Case I: Boolean-Garbled-Boolean. GC的输入为, 参与方调用生成. 此外, 参与方采样茫化函数输出, 生成和. 混淆方混淆计算的电路, 发送GC及其解码信息给评估方. 如此也对评估方进行类似的步骤. 经过GC评估和输出解码后, 评估方可以得到, 并调用生成. 最后参与方计算.
  
  
• Case II: Boolean-Garbled-Arithmetic. 与Case I类似, 除了电路计算的是. 的布尔份额替换为算术份额, 最后计算.
  
  
• Case III & IV: Arithmetic-Garbled-Arithmetic, Arithmetic-Garbled-Boolean. 要计算的函数修改为, 其中输入被替换为, , 和. 输入的份额可由生成, 其余计算步骤同Case I和Case II, 取决于输出的份额形式.

Other Conversions

• Arithmetic to Boolean (A2B): . 因为, 可计算, 可计算. 因此, , 其中可在预处理阶段生成, 可在在线阶段通过参与方执行生成. 完整的A2B协议过程如下:

• Boolean to Arithmetic (B2A): . 利用如下关系式

  其中, 分别表示环上的比特的算术值. 计算中需要借助协议, 完整的B2A协议过程如下:
  
  

• Bit to Arithmetic (Bit2A): 给定比特的布尔份额, 计算其算术份额. 设表示在算术环的值, 则对于, . 令, . 为计算, 可让一对参与方执行生成对应于和的算术份额, 然后调用一次, 输入来计算.
  可以通过Trident和SWIFT中的方法进一步权衡预处理阶段的通信和计算开销. 计算原理如下:
  具体协议过程如下, 预处理阶段需要比特通信量, 在线阶段需要比特通信量, 1轮.

Dot Product

Multi-input Multiplication

Secure Comparison

• ABY3中通信量优化的Parallel prefix adder (PPA);
• ABY2.0中通信轮次优化的比特抽取电路.

Bit Injection

Oblivious Selection

Piece-wise Polynomial

与ABY3类似, 非线性的激活函数计算可通过分段多项式近似计算, 而分段多项式计算可看成是由一系列常数公开多项式和c1，...，cm 组成的,使得：

则有, 其中, , 对于, 若, 则, 否则. 因此可以通过安全比较协议和来计算. 在线阶段若对每个调用, 则需要调用次, 可以首先计算的加法份额, 然后调用一次从而独立于来优化通信. 具体协议过程如下, 预处理阶段需要比特通信量, 在线阶段需要比特通信量, 1轮.

ArgMin / ArgMax

给定长度为的向量的-sharing, 计算最小元素所在的索引, 输出长度为的one-hot比特向量的-shared, 其中最小元素所在索引置为1, 其余为0. 本文中使用的是Damgård等人在S&P'19提出的基于二叉树的方法通过分组比较和递归的方式来计算中的最小元素, 并同时更新. 首先将的每个比特都初始化为1. 通过将的元素进行分组, 逐对进行安全比较得出最小值所在位置, 并更新另一个位置的值为0. 如此递归最后只有整个向量中的最小值所在位置仍为1, 其余为0. 类似的思想可以用于求最大值所在的索引. 完整的协议过程如下:

实验部分只针对实现公平性的方案, 不考虑鲁棒性, 因为后者使用了鲁棒的联合发送原语(jsnd)且预处理阶段最后进行一次性验证, 相比前者, 后者开销更小.

ML Training

ML Inference

References

[1] M. Byali, H. Chaudhari, A. Patra, and A. Suresh, “FLASH: Fast and robust framework for privacy-preserving machine learning,” PoPETs, vol. 2020, no. 2, pp. 459–480, Apr. 2020.

[2] H. Chaudhari, R. Rachuri, and A. Suresh, “Trident: Efficient 4PC framework for privacy preserving machine learning,” in NDSS 2020. The Internet Society, Feb. 2020.

[3] P. Mohassel and P. Rindal, “ABY3: A mixed protocol framework for machine learning,” in ACM CCS 2018, D. Lie, M. Mannan, M. Backes, and X. Wang, Eds. ACM Press, Oct. 2018, pp. 35–52.

[4] S. Wagh, D. Gupta, and N. Chandran, “SecureNN: 3-party secure computation for neural network training,” PoPETs, vol. 2019, no. 3, pp. 26–49, Jul. 2019.

[5] N. Koti, M. Pancholi, A. Patra, and A. Suresh, “SWIFT: Super-fast and Robust Privacy-Preserving Machine Learning,” in USENIX Security’21, 2021.

[6] I.Damga ̊rd,D.Escudero,T.K.Frederiksen,M.Keller,P.Scholl,and N. Volgushev, “New primitives for actively-secure MPC over rings with applications to private machine learning,” in 2019 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2019, pp. 1102–1120.

[7] A. Patra, T. Schneider, A. Suresh, and H. Yalame, “ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation,” in USENIX Security’21, 2021.

[8] A. Dalskov, D. Escudero, and M. Keller, “Fantastic Four: Honest-Majority Four-Party Secure Computation With Malicious Security,” in USENIX Security’21, 2021.