Paper 2013/042

Complexity of Multi-Party Computation Functionalities

Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek


The central objects of secure multiparty computation are the “multiparty functions” (or functionalities) that it seeks to securely realize. In this article we survey a set of results that constitute a Cryptographic Complexity Theory. This theory classifies and compares multiparty functions according to their secure computability and reducibility to each other. The basic questions studied, under various notions of security and reducibility, include: • Which functionalities are securely realizable (or are “trivial” – i.e., can be reduced to any functionality)? • Which functionalities are “complete” – i.e., those to which any functionality can be reduced? • More generally, which functionalities are reducible to which? Outside of triviality and completeness, this question is relatively less explored. Reductions yield relative measures of complexity among various functionalities. In the information- theoretic setting, absolute complexity measures have also been considered. In particular, we discuss results regarding which functions have t-private protocols (in which security is required against a passive adversary corrupting t out of n players) and how this set changes as t increases from 1 to n. We treat separately the results on two-party functionalities, for which the cryptographic complexity is much better understood. In particular, we present unified combinatorial characterizations of completeness and triviality for secure function evaluation using notions of isomorphism and the common information functionality (called the kernel) of a given functionality. Beyond completeness and triviality, we also discuss results on general reducibility, and, in the computationally bounded setting, the connection between these reductions and computational hardness assumptions. We briefly discuss results on reactive functionalities, which are much less studied than non-reactive (secure function evaluation) functionalities. Finally, we conclude with a selection of open problems.

Available format(s)
Publication info
Published elsewhere. Authors' version of a chapter in a book published by IOS Press (copyright retained by the authors)
Contact author(s)
mmp @ illinois edu
2013-01-29: received
Short URL
Creative Commons Attribution


      author = {Hemanta K.  Maji and Manoj Prabhakaran and Mike Rosulek},
      title = {Complexity of Multi-Party Computation Functionalities},
      howpublished = {Cryptology ePrint Archive, Paper 2013/042},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.