We develop new tools to study the relative complexities of secure
multi-party computation tasks (functionalities) in the Universal
Composition framework. When one task can be securely realized using
another task as a black-box, we interpret this as a
qualitative, complexity-theoretic reduction between the two tasks.
Virtually all previous characterizations of MPC functionalities,
in the UC model or otherwise, focus exclusively on secure
function evaluation. In comparison, the tools we develop do not
rely on any special internal structure of the functionality, thus
applying to functionalities with arbitrary behavior. Our tools
additionally apply uniformly to both the PPT and unbounded
computation models.

Our first main tool is the notion of {\em splittability},
which is an exact characterization of realizability in the
UC framework with respect to a large class of communication
channel functionalities. Using this characterization, we
can rederive all previously-known impossibility results
as immediate and simple corollaries. We also complete the
combinatorial characterization of 2-party
secure function evaluation initiated by \cite{CanettiKuLi03}
and partially extend the combinatorial conditions to the
multi-party setting.

Our second main tool is the notion of {\em
deviation-revealing} functionalities, which allows us
to translate complexity separations in simpler MPC settings
(such as the honest-but-curious corruption model) to the
standard (malicious) setting.
Applying this tool, we demonstrate
the existence of functionalities which are neither
realizable nor complete, in the unbounded computation model.