Welcome to the resource topic for 2023/1204
Title:
On Fully-Secure Honest Majority MPC without n^2 Round Overhead
Authors: Daniel Escudero, Serge Fehr
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 t2. In the case of t3, 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 t2 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 t3 setting, it is not known how to reduce this round count for t2 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 t2 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 t3 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 t3 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.
ePrint: https://eprint.iacr.org/2023/1204
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .