The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency
The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency
复制标题
DOI：
10.1109/focs46700.2020.00121
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Benny Applebaum;Eliran Kachlon;A. Patra
中科院分区：
文献类型：
--
作者：
Benny Applebaum;Eliran Kachlon;A. Patra
在1988年的STOC中，Ben-Or，Goldwasser和Wigderson（BGW）在密码学和分布式计算领域建立了一个重要的里程碑，通过展示每个功能都可以在存在控制多达$n/3$方的活跃（又名拜占庭）匆忙对手的情况下以完美的（信息理论和无错误）安全性进行计算。研究了BGW模型下一般安全多方计算的轮复杂度。我们的主要结果表明，每一个功能可以实现只有四轮的互动，有些功能不能在三轮计算。这完全解决了完美的主动安全的最佳弹性MPC的复杂性，解决了长期的研究。我们的下限是基于一种新的轮减少技术，使我们能够提升现有的三轮下限可验证的秘密共享的四轮下限一般MPC。为了证明上界，我们开发了新的轮效率协议来计算大型字段上的2度函数，并建立了此类函数的完整性。后一个结果扩展了Applebaum，Brakerski和Tsabary（TCC 2018，Eurocrypt 2019）最近的完备性定理，该定理仅限于二元域。
In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to $n/3$ of the parties. We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research. Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.