International Association
for Cryptologic Research

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|.