Ph.D Thesis

Ph.D StudentPaskin-Cherniavsky Anat
SubjectSecure Computation with Minimal Interaction
DepartmentDepartment of Computer Science
Supervisors PROF. Yuval Ishai
PROF. Eyal Kushilevitz
Full Thesis textFull thesis text - English Version


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. In this thesis, we study a few questions related to the goal of minimizing the round complexity of MPC.

2-round MPC.  We study the possibility of MPC with only two rounds of interaction in the case that an honest majority is assumed. We obtain several positive results which complement previous negative results in the area.

On constant-round unconditional MPC.  We show that a common general technique for constructing such protocols can apply only to functions f in the class NC (that is, functions efficiently computable in parallel).

Many previous constant-round protocols relied on efficient representations of functions by low-degree randomizing polynomials. In most of these representations, the degree in the randomness is at most 2 and the degree in the input is constant. We show that any function f which has an efficient representation with such degree constraints must be in NC.

On the flip side, this negative result provides an avenue for obtaining new parallel algorithms via the construction of randomizing polynomials. We provide several examples for the potential usefulness of this approach.

Computing on encrypted data.  We present a 2-message two-party protocol for evaluating branching programs such that the communication complexity depends only on the length of the branching program and not on its size. This protocol implies an encryption scheme which supports an efficient evaluation of bounded-length branching programs on encrypted data. Subsequently to our work, a more general result (allowing to evaluate arbitrary circuits on encrypted data) was given in a breakthrough result of Gentry. However, our protocol is simpler, relies on a different intractability assumption, and can be more easily modified to offer protection against malicious parties.