Abstract. In secure computation among a set P of players one considers an
adversary who can corrupt certain players. The three usually considered types
of corruption are active, passive, and fail corruption. The adversary’s corruption
power is characterized by a so-called adversary structure which enumerates the
adversary’s corruption options, each option being a triple (A,E, F) of subsets of
P, where the adversary can actively corrupt the players in A, passively corrupt
the players in E, and fail-corrupt the players in F.
This paper is concerned with characterizing for which adversary structures
general secure function evaluation (SFE) and secure (reactive) multi-party computation
(MPC) is possible, in various models. This has been achieved so far only
for the very special model of perfect security, where, interestingly, the conditions
for SFE and MPC are distinct. Such a separation was first observed by Ishai et al.
in the context of computational security. We give the exact conditions for general
SFE and MPC to be possible for information-theoretic security (with negligible
error probability) and for computational security, assuming a broadcast channel,
with and without setup. In all these settings we confirm the strict separation between
SFE and MPC. As a simple consequence of our results we solve an open
problem for computationally secure MPC in a threshold model with all three corruption
types.