Non-interactive secure multiparty computation

We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function f(x₁,...,x _n) is specified by a joint probability distribution R = (R ₁,...,R_n) and local encoding functions Enc _i(x_i,r_i), 1 ≤ i ≤ n. Given correlated randomness (r₁,...,r_n) ∈_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₁,...,m_n can be used to decode f(x₁,...,x_n). For a set T ⊆ [n], the protocol is said to be T-robust if revealing the messages (Enc_i(x_i, r_i))_i∈T together with the randomness (r _i)_i∈T gives the same information about (x _1i∈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 ≤ t ≤ 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₁,...,x _n) = x₁x₂...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ⁿ → 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.