Ph.D Thesis | |

Ph.D Student | Paskin-Cherniavsky Anat |
---|---|

Subject | Secure Computation with Minimal Interaction |

Department | Department of Computer Science |

Supervisors | PROF. Yuval Ishai |

PROF. Eyal Kushilevitz | |

Full Thesis text |

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.