International Association
for Cryptologic Research

We study secure multiparty computation in the asynchronous setting with perfect security and optimal resilience (less than one-fourth of the participants are malicious). It has been shown that every function can be computed in this model [Ben-OR, Canetti, and Goldreich, STOC'1993]. Despite 30 years of research, all protocols in the asynchronous setting require $\Omega(n^2C)$ communication complexity for computing a circuit with $C$ multiplication gates. In contrast, for nearly 15 years, in the synchronous setting, it has been known how to achieve $\mathcal{O}(nC)$ communication complexity (Beerliova and Hirt; TCC 2008). The techniques for achieving this result in the synchronous setting are not known to be sufficient for obtaining an analogous result in the asynchronous setting. We close this gap between synchronous and asynchronous secure computation and show the first asynchronous protocol with $\mathcal{O}(nC)$ communication complexity for a circuit with $C$ multiplication gates. Linear overhead forms a natural barrier for general secret-sharing-based MPC protocols. Our main technical contribution is an asynchronous weak binding secret sharing that achieves rate-1 communication (i.e., $\mathcal{O}(1)$-overhead per secret). To achieve this goal, we develop new techniques for the asynchronous setting, including the use of \emph{trivariate polynomials} (as opposed to bivariate polynomials).

A major challenge of any asynchronous MPC protocol is the need to reach an agreement on the set of private inputs to be used as input for the MPC functionality. Ben-Or, Canetti and Goldreich [STOC 93] call this problem Agreement on a Core Set (ACS) and solve it by running n parallel instances of asynchronous binary Byzantine agreements. To the best of our knowledge, all results in the perfect and statistical security setting used this same paradigm for solving ACS. Using all known asynchronous binary Byzantine agreement protocols, this type of ACS has Omega(log n) expected round complexity, which results in such a bound on the round complexity of MPC protocols as well (even for constant depth circuits). We provide a new solution for Agreement on a Core Set that runs in expected O(1) rounds. Our perfectly secure variant is optimally resilient (t<n/4) and requires just O(n^4 log n) expected communication complexity. We show a similar result with statistical security for t<n/3. Our ACS is based on a new notion of Asynchronously Validated Asynchronous Byzantine Agreement (AVABA) and new information-theoretic analogs to techniques used in the authenticated model. Along the way, we also construct a new perfectly secure packed asynchronous verifiable secret sharing (AVSS) protocol with just O(n^3 log n) communication complexity, improving the state of the art by a factor of O(n). This leads to a more efficient asynchronous MPC that matches the state-of-the-art synchronous MPC. We provide a new solution for Agreement on a Core Set that runs in expected O(1) rounds. Our perfectly secure variant is optimally resilient (t<n/4) and requires just O(n^4 log n) expected communication complexity. We show a similar result with statistical security for t<n/3. Our ACS is based on a new notion of Asynchronously Validated Asynchronous Byzantine Agreement (AVABA) and new information-theoretic analogs to techniques used in the authenticated model. Along the way, we also construct a new perfectly secure packed asynchronous verifiable secret sharing (AVSS) protocol with just O(n^3 log n) communication complexity, improving the state of the art by a factor of O(n). This leads to a more efficient asynchronous MPC that matches the state-of-the-art synchronous MPC.

We prove that perfectly-secure optimally-resilient secure Multi-Party Computation (MPC) for a circuit with $C$ gates and depth $D$ can be obtained in $O((Cn+n^4 + Dn^2)\log n)$ communication complexity and $O(D)$ expected time. For $D \ll n$ and $C\geq n^3$, this is the \textbf{first} perfectly-secure optimal-resilient MPC protocol with \textbf{linear} communication complexity per gate and \textbf{constant} expected time complexity per layer. Compared to state-of-the-art MPC protocols in the player elimination framework [Beerliova and Hirt TCC'08, and Goyal, Liu, and Song CRYPTO'19], for $C>n^3$ and $D \ll n$, our results significantly improve the run time from $\Theta(n+D)$ to expected $O(D)$ while keeping communication complexity at $O(Cn\log n)$. Compared to state-of-the-art MPC protocols that obtain an expected $O(D)$ time complexity [Abraham, Asharov, and Yanai TCC'21], for $C>n^3$, our results significantly improve the communication complexity from $O(Cn^4\log n)$ to $O(Cn\log n)$ while keeping the expected run time at $O(D)$. One salient part of our technical contribution is centered around a new primitive we call \textit{detectable secret sharing}. It is perfectly-hiding, weakly-binding, and has the property that either reconstruction succeeds, or $O(n)$ parties are (privately) detected. On the one hand, we show that detectable secret sharing is sufficiently powerful to generate multiplication triplets needed for MPC. On the other hand, we show how to share $p$ secrets via detectable secret sharing with communication complexity of just $O(n^4\log n+p \log n)$. When sharing $p\geq n^4$ secrets, the communication cost is amortized to just $O(1)$ per secret. Our second technical contribution is a new Verifiable Secret Sharing protocol that can share $p$ secrets at just $O(n^4\log n+pn\log n)$ word complexity. When sharing $p\geq n^3$ secrets, the communication cost is amortized to just $O(n)$ per secret. The best prior required $O(n^3)$ communication per secret.

We present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share f+1 secrets with a total communication complexity of O(λn^2) words, where λ is the security parameter and n is the number of parties. Using Bingo, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses O(λn^3) expected words and constant expected time, which we in turn use to construct an adaptively secure high-threshold asynchronous distributed key generation (ADKG) protocol that uses O(λn^3) expected words and constant expected time. To the best of our knowledge, our ADKG is the first to allow for an adaptive adversary while matching the asymptotic complexity of the best known static ADKGs.

Broadcast is an essential primitive for secure computation. We focus in this paper on optimal resilience (i.e., when the number of corrupted parties $t$ is less than a third of the computing parties $n$), and with no setup or cryptographic assumptions. While broadcast with worst case $t$ rounds is impossible, it has been shown [Feldman and Micali STOC'88, Katz and Koo CRYPTO'06] how to construct protocols with expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, specifically $\bigO(n^2L+n^6\log n)$ expected number of bits transmitted for broadcasting a message of length $L$. This leads to a significant communication blowup in secure computation protocols in this setting. In this paper, we substantially improve the communication complexity of broadcast in constant expected time. Specifically, the expected communication complexity of our protocol is $\bigO(nL+n^4\log n)$. For messages of length $L=\Omega(n^3 \log n)$, our broadcast has no asymptotic overhead (up to expectation), as each party has to send or receive $\bigO(n^3 \log n)$ bits. We also consider parallel broadcast, where $n$ parties wish to broadcast $L$ bit messages in parallel. Our protocol has no asymptotic overhead for $L=\Omega(n^2\log n)$, which is a common communication pattern in perfectly secure MPC protocols. For instance, it is common that all parties share their inputs simultaneously at the same round, and verifiable secret sharing protocols require the dealer to broadcast a total of $\bigO(n^2\log n)$ bits. As an independent interest, our broadcast is achieved by a \emph{packed verifiable secret sharing}, a new notion that we introduce. We show a protocol that verifies $\bigO(n)$ secrets simultaneously with the same cost of verifying just a single secret. This improves by a factor of $n$ the state-of-the-art.

Secure computation enables n mutually distrustful parties to compute a function over their private inputs jointly. In 1988, Ben-Or, Goldwasser, and Wigderson (BGW) proved that any function can be computed with perfect security in the presence of a malicious adversary corrupting at most $$t< n/3$$ t < n / 3 parties. After more than 30 years, protocols with perfect malicious security, and round complexity proportional to the circuit’s depth, still require (verifiably) sharing a total of $$O(n^2)$$ O ( n 2 ) values per multiplication. In contrast, only O ( n ) values need to be shared per multiplication to achieve semi-honest security. Sharing $$\Omega (n)$$ Ω ( n ) values for a single multiplication seems to be the natural barrier for polynomial secret-sharing-based multiplication. In this paper, we construct a new secure computation protocol with perfect, optimal resilience and malicious security that incurs (verifiably) sharing O ( n ) values per multiplication. 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 weak VSS for polynomials of degree 2t , which incurs the same communication and round complexities as the state-of-the-art constructions for 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 sub-linear communication complexity (in the size of the circuit) for perfectly secure computation for important functions like matrix multiplication.

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.