Cryptographic complexity of multi-party computation problems: Classifications and separations

Manoj Prabhakaran, Mike Rosulek

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2008 - 28th Annual International Cryptology Conference, Proceedings
Number of pages18
StatePublished - 2008
Externally publishedYes
Event28th Annual International Cryptology Conference, CRYPTO 2008 - Santa Barbara, CA, United States
Duration: Aug 17 2008Aug 21 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5157 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other28th Annual International Cryptology Conference, CRYPTO 2008
Country/TerritoryUnited States
CitySanta Barbara, CA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Cryptographic complexity of multi-party computation problems: Classifications and separations'. Together they form a unique fingerprint.

Cite this