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

今天给大家带来的是发表于Financial Cryptography and Data Security 2020 (FC'20)的文章Communication-Efficient (Client-Aided) Secure Two-Party Protocols and Its Application.

原文链接: 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

1

Abstract

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

2

Preliminaries

• 秘密共享方案: 上的两方加法秘密共享-additive secret sharing, .
• 安全模型: 两方半诚实安全模型
• 客户端辅助(client-aided)模型, 设客户端不与任何计算方共谋, 主要负责生成并分发Beaver三元组以提升离线阶段的效率.

3

Core Tools for Round-Efficient Protocols

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

令是正整数, , 其中. 记. 定义客户端辅助协议来生成-BTE的方法如下:

1.对于, 客户端从中随机选取和, 设. 对于满足的每个, 通过设定, 客户端随机选取, 并设定.

2. 客户端发送所有的给和所有的给.

对于, 令为给定第个秘密输入值的份额, 则多扇入MULT/AND门的计算协议的计算方式如下:

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计算协议的通信轮次.

4

Communication-Efficient Protocols

下面只考虑上的情况, 类似地可以实现相同通信轮次的上和上的情况.

Equality Check Protocol

给定和, 相等检测协议计算, 其中当且仅当. 协议的主要设计思路是首先计算, 然后计算的所有比特的OR是否为0. 直接使用来计算是不现实的, 本文中使用, 如此协议只需通信轮. 一般而言, 当秘密份额空间为, 并使用的时, 所需的通信轮次为. 协议构造如下:

Overflow Detection Protocol

为了构造算术溢出检测协议, 首先需要构造最高位非零比特抽取协议, 即, 查找的第一个1所在位置,  输出布尔份额向量. 例如, 则.

为了秘密计算中第一个1的位置, 引入prefix-运算, 步骤如下:

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

例如: , 则, 于是有.

通过, 即使并行也需要通信4轮, 若改为, 使用多扇入prefix-运算则只需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. 计算.

: . 过程与类似, 通过使用和来构造1轮通信的计算协议, 记为. 可用于构造三数最值索引计算协议/.

: . 过程类似, 通过使用和来构造1轮通信的计算协议, 记为. 可用于构造最值计算协议.

The Maximum Value Extraction Protocol and Extensions

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

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

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

所需通信轮次为3.

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

1. 在中需要并行执行协议次, 而两两比较的方法只需执行次, 因此, 本文方案的计算开销和通信量开销与成指数关系.

2. 对于较大的, 不能直接使用或, 若用构造的类似协议来计算, 则计算开销将非常巨大. 为此, 可以将算法5中的第3步分解为其他协议, 例如和, 如此需要更多的通信轮次来计算.

5

Perfermance Evaluation

WAN设定: 10MB/s(=80000bits/ms)带宽, 40ms RRT延迟.

Performance of Basic Gates

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

Performance of Our Protocols

协议实现方面, 主要考察了, 和与[1]的对比. 结果如下, 可以看到在线总执行时间主导因素为WAN的延迟. 对于批次的情况下, 本文的协议比基准线更快, 主要原因是本文需要的通信轮次更少, 但由于计算开销太大, 本文方案不适合批次较大的情形.

Application: Privacy-Preserving (Exact) Edit Distance

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

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

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

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

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

6

Conclusions

本文通过-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).

END

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

往期推荐

欢迎投稿邮箱：[e-mail]参与更多讨论，请添加小编微信加入交流群