## Cryptology ePrint Archive: Report 2008/454

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

*Hemanta K. Maji and Manoj Prabhakaran and Mike Rosulek*

**Abstract: **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.

**Category / Keywords: **foundations / multi-party computation, universal composition, secure function evaluation

**Date: **received 28 Oct 2008, last revised 3 Nov 2010

**Contact author: **rosulek at uiuc edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20101104:043916 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]