Paper 2014/960

Non-Interactive Secure Multiparty Computation

Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz, 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,\dots ,x_n)$ is specified by a joint probability distribution $R=(R_1,\dots ,R_n)$ and local encoding functions $En{c}_i(x_i,R_i)$, $1<=i<=n$. Given correlated randomness $(R_1,\dots ,R_n){\in }_{R}R$, each party $P_i$, using its input $x_i$ and its randomness $R_i$, computes the message $m_i=En{c}_i(x_i,R_i)$. The messages $m_1,\dots ,m_n$ can be used to decode $f(x_1,\dots ,x_n)$. For a set $T\subseteq [n]$, the protocol is said to be $T$-robust if revealing the messages $(En{c}_i(x_i,R_i){)}_{i\notin T}$ together with the randomness $(R_i{)}_{i\in T}$ gives the same information about $(x_i{)}_{i\notin T}$ as an oracle access to the function $f$ restricted to these input values. Namely, a coalition $$ can learn no more than the restriction of $$ fixing the inputs of uncorrupted parties, which, in this non-interactive setting, one cannot hope to hide. For $$, the protocol is $$-robust if it is $$-robust for every $$ of size at most $$ and it is fully robust if it is $$-robust. A 0-robust NIMPC protocol for $$ 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 $$, the iterated group product function $$ admits an efficient, fully robust NIMPC protocol. Small functions. Every function $$ 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 $$, where $$ is an input domain of constant size, admits a $$-robust NIMPC protocol of complexity $$. For the case where $$ is a $$-out-of-$$ threshold function, we get a fully robust protocol of complexity $$. 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.