Non-Interactive Secure Multiparty Computation∗
Amos Beimel, Ariel Gabizon, Yuval Ishai +3 more
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function f(x1,..., xn) is specified by a joint probability distribution R = (R1,..., Rn) and local encoding functions Enci(xi, Ri), 1 ≤ i ≤ n. Given correlated randomness (R1,..., Rn) ∈R R, each party Pi, using its input xi and its randomness Ri, computes the message mi = Enci(xi, Ri). The messagesm1,...,mn can be used to decode f(x1,..., xn). For a set T ⊆ [n], the protocol is said to be T-robust if revealing the messages (Enci(xi, Ri))i 6∈T together with the random-ness (Ri)i∈T gives the same information about (xi)i 6∈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. (Euro-
•Jan 1, 2014•0 citations