International Association
for Cryptologic Research

We study network-agnostic {\it secure multi-party computation} (MPC) in the presence of {\it computationally-bounded} adversaries. A network-agnostic protocol provides the best possible security guarantees, irrespective of the type of underlying communication network. Previous MPC protocols in this regime either assume a setup for a common reference string (CRS) and a threshold additively homomorphic encryption (Blum et al. CRYPTO 2020) or a plain public-key infrastructure (PKI) setup (Bacho et al. CRYPTO 2023). Both these MPC protocols perform circuit-evaluation over encrypted data and also deploy different forms of zero-knowledge (ZK) proofs, along with other computationally-expensive cryptographic machinery. We aim to build an MPC protocol based on circuit evaluation on secret-shared data, {\it avoiding} ZK proofs and other computationally-expensive cryptographic machinery and based on a {\it plain} PKI setup. To achieve our goal, we present the {\it first} network-agnostic {\it verifiable secret sharing} (VSS) protocol with the {\it optimal} threshold conditions, which is of independent interest. Previously, network-agnostic VSS is known either with {\it perfect} security (Appan et al. IEEE IT 2023) where the threshold conditions are {\it not} known to be optimal or with {\it statistical security} (Appan et al. TCC 2023) where the threshold conditions are optimal, but the parties need to perform {\it exponential} amount of computation and communication. Although our proposed MPC protocol incurs higher communication complexity compared to state-of-the-art network-agnostic MPC protocols, it offers valuable insights and motivates alternative directions for designing {\it computationally inexpensive} MPC protocols, based on a plain PKI setup, which has not been explored in the domain of network-agnostic MPC.

Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of n mutually distrusting parties with private inputs to securely compute any publicly known function of their inputs, by keeping their respective inputs as private as possible. While several works in the past have addressed the problem of designing communication-efficient MPC protocols in the synchronous communication setting, not much attention has been paid to the design of efficient MPC protocols in the asynchronous communication setting. In this work, we focus on the design of efficient asynchronous MPC (AMPC) protocol with statistical security, tolerating a computationally unbounded adversary, capable of corrupting up to t parties out of the n parties. The seminal work of Ben-Or, Kelmer and Rabin (PODC 1994) and later Abraham, Dolev and Stern (PODC 2020) showed that the optimal resilience for statistically secure AMPC is $$t < n/3$$ t < n / 3 . Unfortunately, the communication complexity of the protocol presented by Ben-Or et al. is significantly high, where the communication complexity per multiplication is $$\Omega (n^{13} \kappa ^2 \log n)$$ Ω ( n 13 κ 2 log n ) bits (where $$\kappa $$ κ is the statistical-security parameter). To the best of our knowledge, no work has addressed the problem of improving the communication complexity of the protocol of Ben-Or et al. In this work, our main contributions are the following. We present a new statistically secure AMPC protocol with the optimal resilience $$t < n/3$$ t < n / 3 , where the communication complexity is $$\mathcal {O}(n^4 \kappa )$$ O ( n 4 κ ) bits per multiplication. Apart from improving upon the communication complexity of the protocol of Ben-Or et al., our protocol is relatively simpler and based on very few sub-protocols, unlike the protocol of Ben-Or et al. which involves several layers of sub-protocols. A central component of our AMPC protocol is a new and simple protocol for verifiable asynchronous complete secret-sharing (ACSS), which is of independent interest. As a side result, we give the security proof for our AMPC protocol in the standard universal composability (UC) framework of Canetti (FOCS 2001, JACM 2020), which is now the de facto standard for proving the security of cryptographic protocols. This is unlike the protocol of Ben-Or et al., which was missing the formal security proofs.

In this paper, we design unconditionally secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally unbounded malicious adversary characterized by an adversary structure $$\mathcal {Z}$$ Z , which enumerates all possible subsets of potentially corrupt parties. We present protocols with both perfect-security , as well as with statistical-security . While the protocols in the former class achieve all the security properties in an error-free fashion, the protocols belonging to the latter category achieve all the security properties except with a negligible error. Our perfectly secure protocol incurs an amortized communication of $$\mathcal {O}(|\mathcal {Z}|^2)$$ O ( | Z | 2 ) bits per multiplication. This improves upon the protocol of Choudhury and Pappu (INDOCRYPT 2020) with the least known amortized communication complexity of $$\mathcal {O}(|\mathcal {Z}|^3)$$ O ( | Z | 3 ) bits per multiplication. On the other hand, our statistically secure protocol incurs an amortized communication of $$\mathcal {O}(|\mathcal {Z}|)$$ O ( | Z | ) bits per multiplication. This is the first statistically secure asynchronous MPC protocol against general adversaries. Previously, perfectly secure and statistically secure MPC with an amortized communication cost of $$\mathcal {O}(|\mathcal {Z}|^2)$$ O ( | Z | 2 ) and $$\mathcal {O}(|\mathcal {Z}|)$$ O ( | Z | ) bits, respectively, per multiplication was known only in the relatively simpler synchronous communication setting (Hirt and Tschudi in ASIACRYPT, Springer, 2013).

In this work, we initiate the study of network agnostic MPC protocols with statistical security. Network agnostic MPC protocols give the best possible security guarantees, irrespective of the behaviour of the underlying network. While network agnostic MPC protocols have been designed earlier with perfect and computational security, nothing is known in the literature regarding their possibility with statistical security. We consider the general-adversary model, where the adversary is characterized by an adversary structure which enumerates all possible candidate subsets of corrupt parties. Known statistically-secure synchronous MPC (SMPC) and asynchronous MPC (AMPC) protocols are secure against adversary structures satisfying the Q^{(2)} and Q^{(3)} conditions respectively, meaning that the union of no two and three subsets from the adversary structure cover the entire set of parties. Fix adversary structures Z_s and Z_a, satisfying the Q^{(2)} and Q^{(3)} conditions respectively, where Z_a \subset Z_s. Then given an unconditionally-secure PKI, we ask whether it is possible to design a statistically-secure MPC protocol, which is resilient against Z_s and Z_a in a synchronous and an asynchronous network respectively, even if the parties are unaware of the network type. We show that this is possible iff Z_s and Z_a satisfy the Q^{(2, 1)} condition, meaning that the union of any two subsets from Z_s and any one subset from Z_a is a proper subset of the set of parties. The complexity of our protocol is polynomial in |Z_s|.