Paper 2021/346

Round-optimal Honest-majority MPC in Minicrypt and with Everlasting Security

Benny Applebaum and Eliran Kachlon and Arpita Patra

Abstract

We study the round complexity of secure multiparty computation (MPC) in the challenging model where full security, including guaranteed output delivery, should be achieved at the presence of an active rushing adversary who corrupts up to half of parties. It is known that 2 rounds are insufficient in this model (Gennaro et al., Crypto 2002), and that 3 round protocols can achieve computational security under public-key assumptions (Gordon et al., Crypto 2015; Ananth et al., Crypto 2018; and Badrinarayanan et al., ASIACRYPT 2020). However, despite much effort, it is unknown whether public-key assumptions are inherently needed for such protocols, and whether one can achieve similar results with security against computationally-unbounded adversaries. In this paper, we use Minicrypt-type assumptions to realize 3-round MPC with full and active security at the presence of honest-majority. Our protocols come in two flavors: standard computational security and online-computational security with statistical everlasting security, i.e., the protocol is secure against adversaries that are computationally unlimited after the protocol execution. Specifically, we prove the following results: - (Statistical everlasting security) Every NC1 functionality can be computed in 3 rounds given a hash function that is modeled as a random oracle. The random oracle can be replaced with a common reference string (CRS) and a family of hash functions for which it is hard to find inputs that are correlated under some explicit sparse algebraically-simple relation R. We can further relax the assumption on the hash function to standard collision-resistance if the adversary is only semi-rushing, i.e., in each round at least one, a-priory unknown, honest party speaks after the adversary. - (Computational security) Every efficiently-computable function can be realized in 3 rounds assuming non-interactive commitments (NICOM) and R-intractable hash function. The former assumption follows from the existence of injective one-way functions, and the latter can be completely removed if the adversary is semi-rushing.