We develop new tools to study the relative complexities of secure multi-party computation tasks 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 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 [12] and partially extend the combinatorial conditions to the multi-party setting. Our second main tool allows us to translate
complexity separations in simpler MPC settings (such as the honest-but-curious corruption model) to the standard (malicious)
setting. Using this tool, we demonstrate the existence of functionalities which are neither realizable nor complete, in the
unbounded computation model.