Multi-Party Computation: Efficient Protocols, General Adversaries, and Voting
Martin Hirt
Secure multi-party computation allows a set of players to jointly compute an arbitrary function of their inputs, without revealing these inputs to each other. For example, the players can compute the average of their incomes in such a way that no player learns the income of any other player. Or, as a more applied example, a set of voters can compute the sum of their votes without revealing any particular vote.
The classical results in the literature state that $n$ players can compute any function in such a way that any subset of up to $t<n/2$ players obtains no (zero) information about the other players' inputs, except for what can be derived from the public function output. If the bad players may deviate from the protocol and try both to obtain information about the other players inputs as well as to falsify the public output of the computation, then up to $t<n/3$ can be tolerated. Both bounds are tight.
The achievements of this thesis are three-fold: First, we investigate the efficiency of multi-party protocols. Especially those protocols that allow the bad players to deviate from the protocol are very inefficient. We show that protocols that tolerate misbehavior of the players are almost as efficient as protocols that require all players to follow the protocol correctly. The framework that allows this speed-up is generic and might be used for other distributed tasks as well.
Second, we generalize the existential results for multi-party computation. We show that one can tolerate certain collusions to be larger than the mentioned threshold $t$, at the cost that some other collusions of size $t$ cannot be tolerated. This models well the fact that in the real-world, some players might be more likely to cheat than others. For various models, we give complete characterizations of the collusions that can be tolerated.
Third, we study secret-ballot voting, a particular application of multi-party computation. We are especially interested in the so-called “receipt-freeness” property, which essentially means that voters should not be able to sell their right to vote. Receipt-freeness is known to be a subtle property, because one has to deal with voters who are willing to do anything for convincing the vote-buyer that they have submitted the requested vote. We propose a modular framework for such protocols, and construct two concrete receipt-free voting protocols that are more efficient than any receipt-free voting protocol in the literature.
BibTeX Citation
@phdthesis{Hirt01,
author = {Martin Hirt},
title = {Multi-Party Computation: Efficient Protocols, General Adversaries, and Voting},
year = {2001},
month = {9},
note = {Reprint as vol.~3 of {ETH Series in Information Security and Cryptography}, {ISBN} 3-89649-747-2, {H}artung-{G}orre {V}erlag, {K}onstanz, 2001},
school = {{ETH Zurich}},
}