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).