Paper 2023/1204
On FullySecure 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 secretshared values, but in the $t<n/2$ case the equivalent is robust secretsharing, 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 secretshared values while involving only a linear amount of communication per secret, which may also be of independent interest.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Minor revision. LATINCRYPT 2023
 Keywords
 MPCHonest MajorityRobust SecretSharing
 Contact author(s)

daniel escudero @ protonmail com
fehr @ cwi nl  History
 20230810: approved
 20230808: received
 See all versions
 Short URL
 https://ia.cr/2023/1204
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1204, author = {Daniel Escudero and Serge Fehr}, title = {On FullySecure Honest Majority MPC without $n^2$ Round Overhead}, howpublished = {Cryptology ePrint Archive, Paper 2023/1204}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1204}}, url = {https://eprint.iacr.org/2023/1204} }