On the Message Complexity of Secure Multiparty Computation
Yuval Ishai, Manika Mittal, Rafail OstrovskyAbstract:
We study the minimal number of 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 in turn can be based on 2-message oblivious transfer) or on a one-way function given a correlated randomness setup.
comment: PKC (1) 2018: 698-711
Fetch PDF file of the paper
|Back to Publications List|