Paper 2023/1204

On Fully-Secure Honest Majority MPC without $n^2$ Round Overhead

Abstract

Fully secure multiparty computation (or guaranteed output delivery) among $n$ parties can be achieved with perfect security if the number of corruptions $t$ is less than $n/3$, or with statistical security with the help of a broadcast channel if $t<n/2$. In the case of $t<n/3$, it is known that it is possible to achieve linear communication complexity, but at a cost of having a round count of $\Omega(\mathsf{depth}(C) + n)$ in the worst case. The number of rounds can be reduced to $O(\mathsf{depth}(C))$ by either increasing communication, or assuming some correlated randomness (a setting also known as the preprocesing model). For $t<n/2$ it is also known that linear communication complexity is achievable, but at the cost of $\Omega(\mathsf{depth}(C) + n^2)$ rounds, due to the use of a technique called dispute control. However, in contrast to the $t<n/3$ setting, it is not known how to reduce this round count for $t<n/2$ to $O(\mathsf{depth}(C))$, neither allowing for larger communication, or by using correlated randomness. In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for $t<n/2$ in the preprocessing model, that achieves linear communication complexity, and whose round complexity is only $O(\mathsf{depth}(C))$, without the additive $n^2$ term that appears from the use of dispute control. While on the $t<n/3$ such result requires circuits of width $\Omega(n)$, in our case circuits must be of width $\Omega(n^2)$, leaving it as an interesting future problem to reduce this gap. Our $O(\mathsf{depth}(C))$ round count is achieved by avoiding the use of dispute control entirely, relying on a different tool for guaranteeing output. In the $t<n/3$ setting when correlated randomness is available, this is done by using error correction to reconstruct secret-shared values, but in the $t<n/2$ case the equivalent is robust secret-sharing, which guarantees the reconstruction of a secret in spite of errors. However, we note that a direct use of such tool would lead to \emph{quadratic} communication, stemming from the fact that each party needs to authenticate their share towards each other party. At the crux of our techniques lies a novel method for reconstructing a batch of robustly secret-shared values while involving only a linear amount of communication per secret, which may also be of independent interest.