Paper 2008/454

Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation

Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek


In symmetric secure function evaluation (SSFE), Alice has an input $x$, Bob has an input $y$, and both parties wish to securely compute $f(x,y)$. We classify these functions $f$ according to their ``cryptographic complexities,'' and show that the landscape of complexity among these functions is surprisingly rich. We give combinatorial characterizations of the SSFE functions $f$ that have passive-secure protocols, and those which are protocols secure in the standalone setting. With respect to universally composable security (for unbounded parties), we show that there is an infinite hierarchy of increasing complexity for SSFE functions, That is, we describe a family of SSFE functions $f_1, f_2, \ldots$ such that there exists a UC-secure protocol for $f_i$ in the $f_j$-hybrid world if and only if $i \le j$. Our main technical tool for deriving complexity separations is a powerful protocol simulation theorem which states that, even in the strict setting of UC security, the canonical protocol for $f$ is as secure as any other protocol for $f$, as long as $f$ satisfies a certain combinatorial characterization. We can then show intuitively clear impossibility results by establishing the combinatorial properties of $f$ and then describing attacks against the very simple canonical protocols, which by extension are also feasible attacks against {\em any} protocol for the same functionality.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
multi-party computationuniversal compositionsecure function evaluation
Contact author(s)
rosulek @ uiuc edu
2010-11-04: revised
2008-10-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hemanta K.  Maji and Manoj Prabhakaran and Mike Rosulek},
      title = {Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2008/454},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.