Player simulation and general adversary structures in perfect multiparty computation (Q1976004)

Multiparty computation is a scenario in which a set of players wish to cooperate in a computation, but do not trust each other and no mutually trusted party is available. The security of such computations is investigated under the assumption that there is an adversary that may corrupt certain players, and to find a solution means to give a protocol that allows \(n\) players to cooperate securely even if some players are corrupted. Previous results specified the set of potentially corrupted players by their cardinality, i.e. given protocols have allowed secure computations under the assumption that the number of corrupted players is not greater than a certain limit. Here, the security is defined in a more general way, namely with respect to an adversary structure, i.e. a monotone set of subsets of the players, where the adversary may corrupt players of \textit{one} set in this structure. First, a framework for constructing new secure multiparty protocols is proposed. The approach allows one to begin with a known protocol and modify it by simulating a player by a set of players, i.e. to perform all operations of the simulated player by a multiparty protocol among the simulating players. Also, the adversary structure tolerated by the resulting protocol is derived. Then, two results are given concerning adversary structures that can be tolerated in information-theoretically secure multiparty computations. Particularly, it is shown that in the passive model, perfect multiparty computation is possible if and only if no two sets in the adversary structure cover the full player set. A similar result holds in the active model case except that there the condition is that no three sets in the adversary structure cover the full player set. It is also shown that for some adversary structures, the length of every resilient protocol grows exponentially in the number of processors. Finally, some open problems are outlined.