Rafail Ostrovsky - Publications

On the Message Complexity of Secure Multiparty Computation

Yuval Ishai, Manika Mittal, Rafail Ostrovsky

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