The Taub Faculty of Computer Science Events and Talks

In the problem of secure multiparty computation (MPC) we have n parties who want to jointly evaluate a function f on their local inputs. An MPC protocol should allow the parties to correctly compute f while hiding the inputs from each other to the extent possible. An important complexity measure of MPC protocols is their round complexity. This talk will cover two questions related to the goal of minimizing the round complexity of MPC: * Are there general MPC protocols which only use two rounds of interaction? We obtain several positive results which complement previous negative results in the area. * Does every polynomial-time computable f admit a constant-round MPC protocol which *perfectly* hides the inputs? All current constant-round protocols are either restricted to functions f in the parallel complexity class NC or alternatively hide the inputs only in a weaker, computational, sense. We show that a common general technique for constructing such protocols cannot apply to functions f outside the class NC. On the flip side, our proof of this negative result gives rise to a new paradigm for the design of parallel algorithms.