Reducing Communication Costs in Multi-Party Computation

  • Tim N Wood

Student thesis: Doctoral ThesisDoctor of Philosophy (PhD)


Multi-party computation (MPC) is a way of computing on private data without revealing the data itself. To do this, data is "secret-shared" amongst a set of mutually-distrusting parties, which perform local computations and interactive processes to evaluate a function. MPC protocols are diverse and offer a variety of different security guarantees, and employ different methodologies to optimize for different aspects of the evaluation. The goal of this work is to show how to reduce communication costs involved in different areas of MPC.

An access structure defines which sets of parties a so-called adversary can corrupt such that the inputs remain private and the outputs are revealed to the right parties; one type of access structure is called Q2, under which assumption there are many classical results on what sorts of functions can be evaluated. One of the contributions of this work is to show how special "error-detection" properties that apply in the context of Q2 access structures can be used to define MPC protocols that improve on the efficiency of classical results.

In the so-called preprocessing model, parties evaluate a function on random inputs, and later "derandomize" using the real (private) inputs. This model is popular in MPC as function evaluation is expensive, whereas derandomization is cheap. In this thesis, a generic method is given for outsourcing preprocessing to a set of servers, which means that low-powered clients who wish to evaluate functions on their data can do so.

The final contribution is a protocol that allows parties to mix two different MPC techniques called garbled circuits and secret-sharing in a secure way, even when the adversary deviates arbitrarily from the protocol description. Mixing these methods is useful as they optimize for different aspects of
Date of Award1 Oct 2019
Original languageEnglish
Awarding Institution
  • The University of Bristol
SponsorsDARPA & FWO Flanders
SupervisorNigel P Smart (Supervisor)


  • cryptography
  • secret-sharing
  • mpc
  • garbled circuits
  • preprocessing model

Cite this