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