Efficient Perfectly Secure Computation with Optimal Resilience

Abstract

Secure computation enables n mutually distrustful parties to compute a function over their private inputs jointly. In 1988 Ben-Or, Goldwasser, and Wigderson (BGW) demonstrated that any function can be computed with perfect security in the presence of a malicious adversary corrupting at most t < n/3 parties. After more than 30 years, protocols with perfect malicious security, with round complexity proportional to the circuit's depth, still require sharing a total of O(n^2) values per multiplication. In contrast, only O(n) values need to be shared per multiplication to achieve semi-honest security. Indeed sharing Ω(n) values for a single multiplication seems to be the natural barrier for polynomial secret sharing-based multiplication. In this paper, we close this gap by constructing a new secure computation protocol with perfect, optimal resilience and malicious security that incurs sharing of only O(n) values per multiplication, thus, matching the semi-honest setting for protocols with round complexity that is proportional to the circuit depth. Our protocol requires a constant number of rounds per multiplication. Like BGW, it has an overall round complexity that is proportional only to the multiplicative depth of the circuit. Our improvement is obtained by a novel construction for {\em weak VSS for polynomials of degree-2t}, which incurs the same communication and round complexities as the state-of-the-art constructions for {\em VSS for polynomials of degree-t}. Our second contribution is a method for reducing the communication complexity for any depth-1 sub-circuit to be proportional only to the size of the input and output (rather than the size of the circuit). This implies protocols with \emph{sublinear communication complexity} (in the size of the circuit) for perfectly secure computation for important functions like matrix multiplication.