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.