A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority
A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority
复制标题
DOI：
10.1145/3133956.3133999
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Yehuda Lindell;Ariel Nof
中科院分区：
文献类型：
--
作者：
Yehuda Lindell;Ariel Nof
安全多方计算协议使一组各方能够计算其输入的函数，而无需透露除输出之外的任何内容。在存在对抗行为的情况下必须保留协议的安全属性。所考虑的两种经典对手模型是半诚实的（对手遵循协议规范，但试图通过检查协议记录来了解超出允许的内容）和恶意的（对手可能遵循任何任意的攻击策略）。半诚实对手的协议通常效率更高，但在许多情况下，安全保证不够强大。在本文中，我们提出了一种新的有效方法，用于将一大类在半诚实对手存在下安全的协议“编译”为在恶意对手存在下安全的协议。我们的方法假设诚实多数（即 t<n/2，其中 t 是损坏方的数量，n 是总体参与方的数量），并且适用于许多基于秘密共享的半诚实协议。为了实现高效率，我们的协议是安全的，可以中止，并且没有实现公平性，这意味着对手可能会收到输出，而诚实的一方则不会。我们提供了编译器的许多实例，并获得了对少量和大量参与方都非常有效的协议变体。我们实施了我们的协议变体并进行了广泛的实验以将它们相互进行比较。我们的结果表明，即使在存在恶意对手的情况下也能保证安全，诚实多数的安全计算也是可行的。例如，我们安全地计算具有 1,000,000 个乘法门的深度 20 的大型算术电路，对于 3 方，大约需要 0.5 秒；对于 50 方，大约需要 29 秒；对于 90 方，大约需要 1 分钟。
Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough. In this paper, we present a new efficient method for "compiling" a large class of protocols that are secure in the presence of semi-honest adversaries into protocols that are secure in the presence of malicious adversaries. Our method assumes an honest majority (i.e., that t<n/2 where t is the number of corrupted parties and n is the number of parties overall), and is applicable to many semi-honest protocols based on secret-sharing. In order to achieve high efficiency, our protocol is secure with abort and does not achieve fairness, meaning that the adversary may receive output while the honest parties do not. We present a number of instantiations of our compiler, and obtain protocol variants that are very efficient for both a small and large number of parties. We implemented our protocol variants and ran extensive experiments to compare them with each other. Our results show that secure computation with an honest majority can be practical, even with security in the presence of malicious adversaries. For example, we securely compute a large arithmetic circuit of depth 20 with 1,000,000 multiplication gates, in approximately 0.5 seconds with three parties, and approximately 29 seconds with 50 parties, and just under 1 minute with 90 parties.