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 $$ is specified by a joint probability distribution $$ and local encoding functions $$, $$. Given correlated randomness $$, each party $$, using its input $$ and its randomness $$, computes the message $$. The messages $$ can be used to decode $$. For a set $$, the protocol is said to be $$-robust if revealing the messages $$ together with the randomness $$ gives the same information about $$ as an oracle access to the function $$ 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.