Biblio

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.

The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavours of termination guarantee - with overwhelming probability and with probability one. The latter type termed as almost-surely terminating BAs are the focus of this paper. An eluding problem in the domain of almost-surely terminating BAs is achieving a constant expected running time. Our work makes progress in this direction. In a setting with n parties and an adversary with unbounded computing power controlling at most t parties in Byzantine fashion, we present two asynchronous almost-surely terminating BA protocols: With the optimal resilience of t \textbackslashtextless n3 , our first protocol runs for expected O(n) time. The existing protocols in the same setting either runs for expected O(n2) time (Abraham et al, PODC 2008) or requires exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions that offer almost-surely terminating feature. With the resilience of t \textbackslashtextless n/3+ε for any ε \textbackslashtextgreater 0, our second protocol runs for expected O( 1 ε ) time. The expected running time of our protocol turns constant when ε is a constant fraction. The known constructions with constant expected running time either require ε to be at least 1 (Feldman-Micali, STOC 1988), implying t \textbackslashtextless n/4, or calls for exponential computing power from the honest parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to asynchronous verifiable secretsharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning. A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with t \textbackslashtextless n/3 and t \textbackslashtextless n 3+ε guarantee Ω(n) and respectively Ω(εt 2) conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol constitutes another contribution of our paper.