# Player Simulation and General Adversary Structures in Perfect Multiparty Computation

## Martin Hirt and Ueli Maurer

```
``` The goal of secure multiparty computation is to transform a given
protocol involving a trusted party into a protocol without need for the
trusted party, by * simulating\/*} the party among the players. Indeed,
by the same means, one can simulate an arbitrary player in any given
protocol. We formally define what it means to simulate a player by a
multiparty protocol among a set of (new) players, and we derive the
resilience of the new protocol as a function of the resiliences of the
original protocol and the protocol used for the simulation.
In contrast to all previous protocols that specify the tolerable
adversaries by the number of corruptible players (a threshold), we
consider general adversaries characterized by an adversary structure, a
set of subsets of the player set, where the adversary may corrupt the
players of one set in the structure. Recursively applying the simulation
technique to standard threshold multiparty protocols results in protocols
secure against general adversaries.
The classical results in unconditional multiparty computation among a set
of $n$ players state that, in the passive model, any adversary that
corrupts less than $n/2$ players can be tolerated, and in the active
model, any adversary that corrupts less than $n/3$ players can be
tolerated. Strictly generalizing these results we prove that in the
passive model, every function (more generally, every cooperation
specified by involving a trusted party) can be computed securely with
respect to a given adversary structure if and only if no * two\/*} sets
in the adversary structure cover the full set of players, and in the
active model, if and only if no * three\/*} sets cover the full set of
players. The complexities of the protocols are polynomial in the number
of maximal adverse player sets in the adversary structure.

\medskip

\noindent{\bf Key words.} Multiparty computation, Information-theoretic
security, Player simulation, General adversaries, Adversary structures.