客户端辅助的轮高效安全两方计算协议及其应用

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

• Abstract

• Preliminaries

• Core Tools for Round-Efficient Protocols

• -fan-in MULT/AND via -Beaver Triple Extension

• More Techniques for Reducing Communication Rounds

• Communication-Efficient Protocols

• Equality Check Protocol

• Overflow Detection Protocol

• Less-Than Comparison Protocol

• Boolean-to-Arithmetic Conversion Protocol and Extensions

• The Maximum Value Extraction Protocol and Extensions

• Perfermance Evaluation

• Performance of Basic Gates

• Performance of Our Protocols

• Application: Privacy-Preserving (Exact) Edit Distance

• Conclusions

• References

  
  

基于秘密共享的多方计算协议(SS-MPC)可以很容易实现高吞吐量, 但通常通信轮次较大, 是WAN高延迟网络环境的主要性能瓶颈, 故减少SS-MPC协议的通信轮次是提升MPC效率的关键所在, 换而言之, 应让MPC的电路尽可能地浅. 为此, 本文主要专注于减少通信轮次, 利用Beaver三元组扩展(Beaver triple extension, BTE)构造了半诚实安全的通信高效的两方计算协议, 可对多扇入门(mult-fan-in gates)进行高效计算, 并给出了一些应用. 例如, 对于比较协议, 只需通信3轮, 比之前相同设定下的工作通信量也减少了38.4%, 总在线执行时间减少了56.1%, 虽然计算开销比以往工作要高, 但本文表明在WAN下这对整体在线性能影响很小.

• 秘密共享方案: 上的两方加法秘密共享-additive secret sharing, .
  
  
• 安全模型: 两方半诚实安全模型

  
  

• 客户端辅助(client-aided)模型, 设客户端不与任何计算方共谋, 主要负责生成并分发Beaver三元组以提升离线阶段的效率.

-fan-in MULT/AND via -Beaver Triple Extension

1. 客户端利用上述协议生成并分发-BTE和给两方.
   
   
2. 对于, 计算并发送给.
   
   
3. 对于, 计算.
   
   
4. 计算并输出, 计算并输出.
   
   

可以看到上述协议只需1轮通信, 且不依赖于, 适合WAN设定, 但缺点是内存消耗和计算开销与成指数级别增长, 因此本文在实际应用中取. 当使用扇入MULT/AND门()时, 需要轮通信来计算扇入MULT/AND.

More Techniques for Reducing Communication Rounds

• One Weights At Most One: 设和分别持有的份额布尔份额和, 若的汉明重量至多为1, 则两方可以通过本地计算其份额比特的来得到的份额. 因为若, 则计算的和计算的之中至少有一个为1, 从而两者份额比特的结果为1.
  
  
• Arithmetic Blinding: 设两个客户端也是计算参与方, 则当它们执行计算时已知秘密本身, 与客户端辅助2PC计算的情况不同, 此时和随机将其各自持有的秘密和分割为和, 然后发送给, 发送给. 若和在之前已经分别得到了和, 则和可通过标准乘法协议来计算, 过程如下:
  
  

1. (预计算阶段)将发给, 将发给;
   
   
2. (在线阶段)本地计算并发给, 本地计算并发给.
   
   
3. 对, 本地计算. 可以看到在线阶段的通信量相比客户端不为计算方的情况减少了一半.
   
   

• Trivial Sharing: 考虑输入方不为计算方的设定, 则此时与标准的客户端辅助2PC相同. 这种情况下可以使用份额本身作为计算的秘密值, 另一方的份额看成. 这可以结合BTE进一步优化2PC计算协议的通信轮次.

Equality Check Protocol

Overflow Detection Protocol

1. 通过将最左边的1后面的比特全部置为1, 得到.
   
   
2. 计算.

有了, 则可根据输出所对应明文的汉明重量至多为1的特点来构造算术溢出检测协议, 该协议输出, 其中当且仅当.

[1]的做法: 检查中是否存在1, 若存在则看1的位置与的是否相同. 使用本文的两轮, 这种做法仍需要通信3轮, 额外的一轮是需要计算.

本文的做法如下:

可以看到上述协议通过使用, 步骤2和步骤6各需1轮通信, 因此总通信轮次为2. 类似地,

• 若份额空间为, 则需要的门来构造两轮;
• 若份额空间为, 则需要的门来构造两轮.

此外, 可以构造只需通信1轮的协议, 设是表示条件是否成立的比特值, 若成立则取值为1. 令, 并设和是满足的参数, 则1轮的协议过程如下:

1. 对于, 记, 其中, ;
   
   
2. 对于每个,

• 设定, ;
• 设定, .
• 对, 令.
  
  

• 设定, 其中表示的第个比特.
• 设定.
• 令.
  
  

• 设定, , , ;
• 设定, , , .
• 对, 令.
  
  

• 对于每个, 计算;
• 对于每个, 计算;
• 对于每个, 计算;
  
  

可以看到上述协议只有步骤5需要1轮通信, 但计算开销和通信量开销都很大.

Less-Than Comparison Protocol

给定, Less-Than比较协议计算, 其中当且仅当$x<y$. 对$i\in\{0,1\}$,="" 协议过程如下:<="" p="">

1. 对于, 分别计算

• ,
• ,
• .
  
  

如上协议需要3轮通信.

Boolean-to-Arithmetic Conversion Protocol and Extensions

B2A转换协议计算, 其中. 由于这种情况下两方已知的其中一个份额, 故可以通过一个算术茫化三元组来完成转换, 其中算术茫化三元组满足, 得到, 得到.

协议过程如下:

可以看到计算方只需1轮通信. 可以利用同样的思想来构造如下协议:

• : . 过程如下:

  只需1轮通信, 记以上计算为. 可用于构造查表协议(结合)以及计算神经网络中的函数.

1. 设定.
2. 设定, , 设定, .
3. 计算和.
4. 计算.

The Maximum Value Extraction Protocol and Extensions

最大值抽取协议计算, 其中是向量中分量的最大值. 简单起见, 假设向量中有三个分量, 相应的计算协议记为, 若直接两两比较来求解, 利用本文提出的3轮协议和1轮协议, 所得协议的总通信轮次为. 主要原因是不能并行. 为此, 本文的做法是首先用比较所有元素的大小关系, 然后利用提取最大值, 如此只需4轮通信. 协议过程如下:

类似的思路可以构造最小值提取协议. 此外, 适当修改算法5中的相应步骤, 可以得到计算最值所在索引的协议, 修改方式如下:

1. 将算法5第3步中计算的替换为;
2. 将算法5第4步修改为计算, 这一步中是公开的, 因此不需要通信.

所需通信轮次为3.

对于时计算的情形, 可以用类似的思路来构造轮高效的计算协议, 但需注意如下两点:

Performance of Basic Gates

下图是不同下计算的开销, 可以看到随着的增大, 预处理所需时间也随之指数级膨胀. 此外, 当批次较小时, WAN的延迟主导了在线运行时间. 因此本文方案适合具有低延迟的WAN场景下的相对小的批次的2PC计算, 例如批次.

Performance of Our Protocols

Application: Privacy-Preserving (Exact) Edit Distance

本文还研究了求解隐私基因编辑精确距离方面的应用. 对于两个长度为的基因串和, 对于动态规划矩阵, 定义每个元素为

其中当且仅当, 否则. 可通过2轮的和1轮的来计算. 为减少总在线执行时间, 可以进行如下优化:

1. 为减少总通信轮次, 并行计算并提前存储, 从而避免每次填充矩阵时计算, 如此只需3轮通信.
2. 矩阵的对角线元素相互独立, 可以对每个并行计算, , , 来减少通信轮次.

应用以上两个技巧, 计算长度为的基因串的精确编辑距离所需的通信轮次为.

实验结果如下, 可以看到在线总执行时间由通信延迟所主导. 在WAN环境中, 基于GC的方法可能比基于SS的方法快得多, 但如果想要计算多个基因串之间的编辑距离, 例如客户端有1个基因串, 想计算它与服务器上的1000个基因串之间的编辑距离, 则SS-MPC比GC要快得多。

本文通过-BTE来减少基于SS的MPC协议的通信轮次以适应WAN环境, 核心技术是基于Beaver三元组扩展, 但是, 协议所需的计算成本和内存成本与呈指数增长, 因此不适合大批次计算和高延迟网络, 需要在实际应用中对其进行限制.

References

[1] Bogdanov, D., Niitsoo, M., Toft, T., Willemson, J.: High-performance secure multiparty computation for data mining applications. Int. J. Inf. Sec. 11(6), 403–418 (2012).