Efficient Constructions for Almost-Everywhere Secure Computation

Jayanti, Siddhartha; Raghuraman, Srinivasan; Vyas, Nikhil

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 [Formula: see text] -degree network with a polylogarithmic work complexity protocol, thereby improving over the state-of-the-art result of Chandran et al. 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.