International Association
for Cryptologic Research

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.

In the classical notion of multiparty computation (MPC), an honest party learning private inputs of others, either as a part of protocol specification or due to a malicious party's unspecified messages, is not considered a potential breach. Several works in the literature exploit this seemingly minor loophole to achieve the strongest security of guaranteed output delivery via a trusted third party, which nullifies the purpose of MPC. Alon et al. (CRYPTO 2020) presented the notion of {\it Friends and Foes} ($\mathtt{FaF}$) security, which accounts for such undesired leakage towards honest parties by modelling them as semi-honest (friends) who do not collude with malicious parties (foes). With real-world applications in mind, it's more realistic to assume parties are semi-honest rather than completely honest, hence it is imperative to design efficient protocols conforming to the $\mathtt{FaF}$ security model. Our contributions are not only motivated by the practical viewpoint, but also consider the theoretical aspects of $\mathtt{FaF}$ security. We prove the necessity of semi-honest oblivious transfer for $\mathtt{FaF}$-secure protocols with optimal resiliency. On the practical side, we present QuadSquad, a ring-based 4PC protocol, which achieves fairness and GOD in the $\mathtt{FaF}$ model, with an optimal corruption of $1$ malicious and $1$ semi-honest party. QuadSquad is, to the best of our knowledge, the first practically efficient $\mathtt{FaF}$ secure protocol with optimal resiliency. Its performance is comparable to the state-of-the-art dishonest majority protocols while improving the security guarantee from abort to fairness and GOD. Further, QuadSquad elevates the security by tackling a stronger adversarial model over the state-of-the-art honest-majority protocols, while offering a comparable performance for the input-dependent computation. We corroborate these claims by benchmarking the performance of QuadSquad. We also consider the application of liquidity matching that deals with highly sensitive financial transaction data, where $\mathtt{FaF}$ security is apt. We design a range of $\mathtt{FaF}$ secure building blocks to securely realize liquidity matching as well as other popular applications such as privacy-preserving machine learning (PPML). Inclusion of these blocks makes QuadSquad a comprehensive framework.

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.