Cryptology ePrint Archive: Report 2018/038

On the Message Complexity of Secure Multiparty Computation

Yuval Ishai and Manika Mittal and Rafail Ostrovsky

Abstract: We study the minimal number of point-to-point messages required for general secure multiparty computation (MPC) in the setting of computational security against semi-honest, static adversaries who may corrupt an arbitrary number of parties.

We show that for functionalities that take inputs from $n$ parties and deliver outputs to $k$ parties, $2n+k-3$ messages are necessary and sufficient. The negative result holds even when given access to an arbitrary correlated randomness setup. The positive result can be based on any 2-round MPC protocol (which can in turn can be based on 2-message oblivious transfer), or on a one-way function given a correlated randomness setup.

Category / Keywords: Secure Multiparty Computation

Original Publication (in the same form): IACR-PKC-2018

Date: received 8 Jan 2018

Contact author: yuvali at cs technion ac il,manikamittal22@gmail com,rafail@cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20180108:181903 (All versions of this report)

Short URL: ia.cr/2018/038

Discussion forum: Show discussion | Start new discussion