[Resource Topic] 2014/960: Non-Interactive Secure Multiparty Computation

Welcome to the resource topic for 2014/960

Non-Interactive Secure Multiparty Computation

Authors: Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Anat Paskin-Cherniavsky


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.

ePrint: https://eprint.iacr.org/2014/960

Talk: https://www.youtube.com/watch?v=OHXU1vfRcWg

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .