Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest
Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest
复制标题
DOI：
10.1145/3319535.3339811
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Jun Furukawa;Yehuda Lindell
中科院分区：
文献类型：
--
作者：
Jun Furukawa;Yehuda Lindell
安全多方计算（MPC）使一组各方能够安全地对他们的私有输入进行联合计算，而不透露除输出外的任何内容。针对半诚实对手的协议保证了安全性，只要被破坏的一方运行指定的协议，并确保在记录中没有任何泄露。相比之下，针对恶意对手的协议在可以运行任何攻击策略的任意对手存在时保证安全性。针对恶意对手的安全性通常是实践中需要的（并且总是首选的），但代价很大。在本文中，我们提出了第一个针对三分之二诚实多数的协议，该协议在恶意对手存在的情况下实现了安全性，其成本基本上与针对半诚实对手的最知名协议完全相同。我们的构造不是一般的转换，因此可能会构造更好的半诚实协议，但不支持我们的转换。然而，对于许多参与方的当前技术水平（基于Shamir共享），我们的协议在每个乘法门只调用一次最好的半诚实乘法协议（加上一些额外的本地计算，对总体成本来说可以忽略不计）。具体地说，我们协议的最佳版本要求每一方平均每个乘法门只发送2.2 /3个元素（当乘法门的数量至少是各方的数量时）。对于小字段，这比Barak等人（ACM CCS 2018）之前最好的协议快四倍，对于大字段，这比Chida等人（CRYPTO 2018）之前最好的协议快两倍。
Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.