Paper 2014/960

Non-Interactive Secure Multiparty Computation

Amos Beimel and Ariel Gabizon and Yuval Ishai and Eyal Kushilevitz and Sigurd Meldgaard and Anat Paskin-Cherniavsky

Abstract

We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function $f(x_1,\ldots,x_n)$ is specified by a joint probability distribution $R=(R_1,\ldots,R_n)$ and local encoding functions $Enc_i(x_i,R_i)$, $1 <= i <= n$. Given correlated randomness $(R_1,\ldots,R_n)\in_R R$, each party $P_i$, using its input $x_i$ and its randomness $R_i$, computes the message $m_i= Enc_i(x_i,R_i)$. The messages $m_1,\ldots,m_n$ can be used to decode $f(x_1,\ldots,x_n)$. For a set $T\subseteq[n]$, the protocol is said to be $T$-robust if revealing the messages $(Enc_i(x_i,R_i))_{i\not\in T}$ together with the randomness $(R_i)_{i\in T}$ gives the same information about $(x_i)_{i\not\in T}$ as an oracle access to the function $f$ restricted to these input values. Namely, a coalition $T$ can learn no more than the restriction of $f$ fixing the inputs of uncorrupted parties, which, in this non-interactive setting, one cannot hope to hide. For $0\le t\le n$, the protocol is $t$-robust if it is $T$-robust for every $T$ of size at most $t$ and it is fully robust if it is $n$-robust. A 0-robust NIMPC protocol for $f$ coincides with a protocol in the private simultaneous messages model of Feige et al.~(STOC 1994). 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.