Efficient Constructions for Almost-Everywhere Secure Computation

We study the problem of almost-everywhere reliable message transmission; a key component in designing efficient and secure Multi-party Computation (MPC) protocols for sparsely connected networks. The goal is to design low-degree networks which allow a large fraction of honest nodes to communicate reliably even when a small constant fraction of nodes experience byzantine corruption and deviate arbitrarily from the assigned protocol. In this paper, we achieve a minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\log$documentlog-degree network with a polylogarithmic work complexity protocol, thereby improving over the state-of-the-art result of Chandran et al. (ICALP 2010) who required a polylogarithmic-degree network and had a linear work complexity. In addition, we also achieve: A work efficient version of Dwork et al.’s (STOC 1986) butterfly network. An improvement upon the state of the art protocol of Ben-or and Ron (Information Processing Letters 1996) in the randomized corruption model—both in work-efficiency and in resilience.