Efficient Multi-Party Computation with Information-Theoretic Security

Zuzana Beerliova-Trubiniova

Multi-party computation (MPC) enables a set of $n$ mutually distrusting
players to perform some computation on their private inputs, such that the
correctness of the output as well as the privacy of the honest players'
inputs is guaranteed even in the presence of an adversary corrupting up to
$t$ of the players and making them misbehave arbitrarily.

In this thesis, we focus on the \emph{efficiency} of multi-party computation
protocols, and present the following contributions:

\begin{itemize}
\item The main efficiency bottleneck in MPC is the computation of the
  multiplication gates. However, since recently, for $t<n/3$ multiplication
  can be reduced to non-robust generation of correct sharings of secret
  random values. We present a novel technique which allows to perfectly and
  very efficiently generate such random sharings. Based on this technique,
  we construct a perfectly secure MPC protocol for $t<n/3$, communicating
  $\O(n\kappa)$ bits per multiplication (where $\kappa$ denotes the
  bit-length of a value).
\item An efficient way of limiting the number of times when the adversary
  can disturb (and slow down) the computation is player elimination --
  every time an inconsistency is detected, a pair of players, at least one
  of them corrupted, is localized and eliminated. However, honest players
  can get eliminated as well, which causes several limitations of this
  technique. We generalize and extend the player elimination-technique, by
  finding other means (than elimination) of preventing localized players
  from disturbing the computation ever again. Our new technique, called
  \emph{dispute control}, allows to construct efficient MPC protocols in
  settings where player elimination is not applicable: We present an
  actively secure MPC protocol that provides optimal security
  (unconditional security against a faulty minority) and communicates only
  $\O(n^2\kappa)$ bits per multiplication.
\item Byzantine agreement (BA) is an MPC primitive which allows the players
  to agree on a particular value. It is used as a building block in many
  distributed protocols, and hence its efficiency is of particular
  importance. Known information-theoretically secure BA protocols with
  optimal resilience are very involved and inefficient -- the most
  efficient known BA protocol requires $\O(n^{17}\kappa)$ bits of
  communication. We propose a new, conceptually simpler BA protocol
  communicating $\O(n^5\kappa)$ bits per BA.
\item Lastly, we concentrate on MPC in asynchronous networks, where there
  is no upper bound on message delay. Known MPC protocols for the
  asynchronous setting suffer from two main disadvantages: they tend to
  have substantially higher communication complexity, and they do not allow
  to take the inputs of all honest players. We propose a solution to both
  these problems.  We present a perfectly secure asynchronous MPC protocol
  that communicates only $\O(n^3\kappa)$ bits per multiplication.
  Furthermore, we extend the protocol for a hybrid communication model,
  allowing \emph{all} players to give input if the \emph{very first round}
  of the communication is synchronous, and taking at least $n-t$ inputs in
  a fully asynchronous setting.
\end{itemize}

All four mentioned contributions are optimal in all security parameters,
i.e., achieve statistical security where $t<n/2$, and achieve perfect
security where $t<n/3$ (respectively $t<n/4$ in the asynchronous world).