**Efficient Perfectly Secure Computation with Optimal Resilience**

*Ittai Abraham and Gilad Asharov and Avishay Yanai*

**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 $\Omega(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.

**Category / Keywords: **Perfect Security, Secure Computation

**Original Publication**** (with major differences): **IACR-TCC-2021

**Date: **received 16 Sep 2021, last revised 18 Oct 2021

**Contact author: **iabraham at vmware com, Gilad Asharov at biu ac il, yanaia at vmware com

**Available format(s): **PDF | BibTeX Citation

**Version: **20211018:134205 (All versions of this report)

**Short URL: **ia.cr/2021/1206

[ Cryptology ePrint archive ]