论文标题
具有异步后备的完美安全同步MPC保证
Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees
论文作者
论文摘要
安全多方计算（MPC）是安全分布式计算中的基本问题。 MPC协议允许一组$ n $互不信任的各方对其私人投入进行任何联合计算，而无需披露有关其输入的任何其他信息。具有信息理论安全性的MPC提供了最强的安全保证，即使在计算无限的对手身上，也仍然安全。完美安全的MPC协议是一类信息从理论上安全的MPC协议，该协议以无错误的方式提供了所有安全保证。这项工作的重点是完美的MPC。已知协议的设计假设是同步或异步通信网络。众所周知，只要对手可以破坏任何$ t_s <n/3 $派对，就可以完全安全同步MPC协议。另一方面，完美安全的异步MPC协议可以忍受高达$ t_a <n/4 $腐败的各方。一个自然的问题是，对于当事方不知道确切的网络类型的设置，是否存在单个MPC协议，并且可以在同步网络中忍受高达$ t_s <n/3 $损坏，而在异步网络中最多可容忍$ t_a <n/4 $损坏。我们设计了如此最佳的世界，完美安全的MPC协议，提供了$ 3T_S + T_A <n $保留。 为了设计我们的协议，我们设计了两个重要的构件，它们具有独立的兴趣。第一个构建块是最佳世界拜占庭协议（BA）协议（BA）协议，可容忍$ t <n/3 $腐败，并且在同步和异步网络中保持安全。第二个构建块是基于多项式的最佳世界，可验证的秘密共享（VSS）协议，可以在同步和异步网络中忍受高达$ t_s $和$ t_a $腐败。
Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of $n$ mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC with information-theoretic security provides the strongest security guarantees and remains secure even against computationally unbounded adversaries. Perfectly-secure MPC protocols is a class of information-theoretically secure MPC protocols, which provides all the security guarantees in an error-free fashion. The focus of this work is perfectly-secure MPC. Known protocols are designed assuming either a synchronous or asynchronous communication network. It is well known that perfectly-secure synchronous MPC protocol is possible as long as adversary can corrupt any $t_s < n/3$ parties. On the other hand, perfectly-secure asynchronous MPC protocol can tolerate up to $t_a < n/4$ corrupt parties. A natural question is does there exist a single MPC protocol for the setting where the parties are not aware of the exact network type and which can tolerate up to $t_s < n/3$ corruptions in a synchronous network and up to $t_a < n/4$ corruptions in an asynchronous network. We design such a best-of-both-worlds perfectly-secure MPC protocol, provided $3t_s + t_a < n$ holds. For designing our protocol, we design two important building blocks, which are of independent interest. The first building block is a best-of-both-worlds Byzantine agreement (BA) protocol tolerating $t < n/3$ corruptions and which remains secure, both in a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worlds verifiable secret-sharing (VSS) protocol, which can tolerate up to $t_s$ and $t_a$ corruptions in a synchronous and in an asynchronous network respectively.
