You are looking at a specific version 20210601:143424 of this paper. See the latest version.

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 non-programable random oracle. The random oracle can be replaced with a common reference string (CRS), a statically-hiding non-interactive commitments (NICOM) and a family of ``R-intractable'' hash functions for which it is hard to find inputs that are correlated under some explicit sparse algebraically-simple relation R. - (Computational security) Every efficiently-computable function can be realized in 3 rounds in the plain model assuming computationally-hiding NICOM and R-intractable hash functions. The assumption of R-intractability can be removed in both settings at the expense of making any one of the following relaxations: (a) increasing the round complexity to 4; (b) restricting the attention to linear functionalities; or (c) restricting the adversary to be non-rushing. In fact, we can support an intermediate notion of semi-rushing adversaries that, in each round, can delay their messages till almost all honest parties speak. The latter notion may be of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
multiparty computationround complexityeverlasting security
Contact author(s)
bennyap @ post tau ac il,elirn chalon @ gmail com,arpita @ iisc ac in
History
2022-09-18: last of 3 revisions
2021-03-17: received
See all versions
Short URL
https://ia.cr/2021/346
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.