Information Security and Cryptography Research Group

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 efficiency of multi-party computation protocols, and present the following contributions:

• 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).
• 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 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.
• 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.
• 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 all players to give input if the very first round of the communication is synchronous, and taking at least $n-t$ inputs in a fully asynchronous setting.

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

BibTeX Citation

@phdthesis{Beerli08,
    author       = {Zuzana {Beerliova-Trubiniova}},
    title        = {Efficient Multi-Party Computation with Information-Theoretic Security},
    year         = 2008,
    month        = 9,
    school       = {{ETH Zurich}},
}

Files and Links

• PDF