In the setting of computational (indistinguishability-based) security, fully robust NIMPC is implied by multi-input functional encryption, a notion that was recently introduced by Goldwasser et al. (Eurocrypt 2014) and realized using indistinguishability obfuscation. We consider NIMPC in the information-theoretic setting and obtain unconditional positive results for some special cases of interest:
Group products. For every (possibly non-abelian) finite group $G$, the iterated group product function $f(x_1,\ldots,x_n)=x_1x_2\ldots x_n$ admits an efficient, fully robust NIMPC protocol.
Small functions. Every function $f$ admits a fully robust NIMPC protocol whose complexity is polynomial in the size of the input domain (i.e., exponential in the total bit-length of the inputs).
Symmetric functions. Every symmetric function $f:\X^n\to \Y$, where $\X$ is an input domain of constant size, admits a $t$-robust NIMPC protocol of complexity $n^{O(t)}$. For the case where $f$ is a $w$-out-of-$n$ threshold function, we get a fully robust protocol of complexity $n^{O(w)}$.
On the negative side, we show that natural attempts to realize NIMPC using private simultaneous messages protocols and garbling schemes from the literature fail to achieve even 1-robustness.
Category / Keywords: cryptographic protocols / secure multiparty computation, obfuscation, private simultaneous messages protocols, randomized encoding of functions, garbling schemes, multi-input functional encryption Original Publication (with major differences): IACR-CRYPTO-2014 Date: received 24 Nov 2014 Contact author: amos beimel at gmail com Available format(s): PDF | BibTeX Citation Version: 20141125:204221 (All versions of this report) Short URL: ia.cr/2014/960