Complexity of multi-party computation functionalities

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The central objects of secure multiparty computation are the "multiparty functions" (or functionalities) that it seeks to securely realize. In this chapter 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.

Original languageEnglish (US)
Title of host publicationSecure Multi-Party Computation
PublisherIOS Press
Pages249-283
Number of pages35
ISBN (Print)9781614991687
DOIs
StatePublished - 2013

Publication series

NameCryptology and Information Security Series
Volume10
ISSN (Print)1871-6431
ISSN (Electronic)1879-8101

Fingerprint

Function evaluation
Hardness

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this

Maji, H. K., Prabhakaran, M., & Rosulek, M. (2013). Complexity of multi-party computation functionalities. In Secure Multi-Party Computation (pp. 249-283). (Cryptology and Information Security Series; Vol. 10). IOS Press. https://doi.org/10.3233/978-1-61499-169-4-249

Complexity of multi-party computation functionalities. / Maji, Hemanta K.; Prabhakaran, Manoj; Rosulek, Mike.

Secure Multi-Party Computation. IOS Press, 2013. p. 249-283 (Cryptology and Information Security Series; Vol. 10).

Research output: Chapter in Book/Report/Conference proceedingChapter

Maji, HK, Prabhakaran, M & Rosulek, M 2013, Complexity of multi-party computation functionalities. in Secure Multi-Party Computation. Cryptology and Information Security Series, vol. 10, IOS Press, pp. 249-283. https://doi.org/10.3233/978-1-61499-169-4-249
Maji HK, Prabhakaran M, Rosulek M. Complexity of multi-party computation functionalities. In Secure Multi-Party Computation. IOS Press. 2013. p. 249-283. (Cryptology and Information Security Series). https://doi.org/10.3233/978-1-61499-169-4-249
Maji, Hemanta K. ; Prabhakaran, Manoj ; Rosulek, Mike. / Complexity of multi-party computation functionalities. Secure Multi-Party Computation. IOS Press, 2013. pp. 249-283 (Cryptology and Information Security Series).
@inbook{2446071d9eee4f20ac3b10c8b58637c7,
title = "Complexity of multi-party computation functionalities",
abstract = "The central objects of secure multiparty computation are the {"}multiparty functions{"} (or functionalities) that it seeks to securely realize. In this chapter 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.",
author = "Maji, {Hemanta K.} and Manoj Prabhakaran and Mike Rosulek",
year = "2013",
doi = "10.3233/978-1-61499-169-4-249",
language = "English (US)",
isbn = "9781614991687",
series = "Cryptology and Information Security Series",
publisher = "IOS Press",
pages = "249--283",
booktitle = "Secure Multi-Party Computation",
address = "Netherlands",

}

TY - CHAP

T1 - Complexity of multi-party computation functionalities

AU - Maji, Hemanta K.

AU - Prabhakaran, Manoj

AU - Rosulek, Mike

PY - 2013

Y1 - 2013

N2 - The central objects of secure multiparty computation are the "multiparty functions" (or functionalities) that it seeks to securely realize. In this chapter 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.

AB - The central objects of secure multiparty computation are the "multiparty functions" (or functionalities) that it seeks to securely realize. In this chapter 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.

UR - http://www.scopus.com/inward/record.url?scp=84888139771&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84888139771&partnerID=8YFLogxK

U2 - 10.3233/978-1-61499-169-4-249

DO - 10.3233/978-1-61499-169-4-249

M3 - Chapter

AN - SCOPUS:84888139771

SN - 9781614991687

T3 - Cryptology and Information Security Series

SP - 249

EP - 283

BT - Secure Multi-Party Computation

PB - IOS Press

ER -