Theory Seminar: Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model

Wednesday, May 10, 2017 - 1:30pm
CS 4310

Speaker Name: 

Oxana Poburinnaya

Speaker Institution: 

Boston University

Cookies: 

Yes

Cookies Location: 

CS 4310

Description: 

Secure multiparty computation (MPC) allows a set of parties, who don't trust each other, to jointly compute a function on their inputs such that each party learns the output, but nothing else. This task naturally arises in many scenarios where privacy must be preserved, such as voting, e-commerce, and computing statistics on sensitive data.

While this problem is one of the main focal points of cryptography, attracting much research, some basic questions still remain unanswered. One of them is how to deal with the natural case where parties become corrupted adaptively, as the protocol proceeds. Specifically, in that case all known protocols for secure MPC require O(d) rounds of interaction, where d is the depth of the circuit which computes the function. This stands in contrast with the static case (where the set of dishonest parties is fixed in advance), in which case 4 round protocols exist.

We build the first fully adaptive constant-round protocol for secure MPC, which doesn't need a commonly trusted setup. In this talk I will focus on the simplest scenario: a two-party protocol where even dishonest parties follow the protocol instructions (but can use all information which is available to them in order to learn about the input of the other party). Already in this simple case previously known solutions require O(d) rounds; we demonstrate a two-round protocol. Using standard techniques, such a protocol can then be transformed into a protocol against adversaries which don't have to follow instructions of the protocol. Our protocols use hardness assumptions which are similar to assumptions needed for the static case.


Joint work with Ran Canetti and Muthuramakrishnan Venkitasubramaniam