Player simulation and general adversary structures in perfect multiparty computation

The goal of secure multiparty computation is to transform a given protocol involving a trusted party into a protocol without need for the trusted part y, by simulating the party among the players. Indeed, by the same means, on e can simulate an arbitrary player in any given protocol. We formally defin e what it means to simulate a player by a multiparty protocol among a set o f (new) players, and we derive the resilience of the new protocol as a func tion of the resiliences of the original protocol and the protocol used for the simulation. In contrast to all previous protocols that specify the tolerable adversarie s by the number of corruptible players (a threshold), we consider general a dversaries 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 thresh old multiparty protocols results in protocols secure against general advers aries. The classical results in unconditional multiparty computation among a set o f n players state that, in the passive model, any adversary that corrupts l ess than n/2 players can be tolerated, and in the active model, any adversa ry that corrupts less than n/3 players can be tolerated. Strictly generaliz ing these results we prove that, in the passive model, every function (more generally, every cooperation specified by involving a trusted party) can b e 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, a nd, 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.