Non-interactive Secure Multiparty Computation for Symmetric Functions, Revisited: More Efficient Constructions and Extensions

Non-interactive secure multiparty computation (NIMPC) is a variant of secure computation which allows each of n players to send only a single message depending on his input and correlated randomness. Abelian programs, which can realize any symmetric function, are defined as functions on the sum of the players’ inputs over an abelian group and provide useful functionalities for real-world applications. We improve and extend the previous results in the following ways: We present NIMPC protocols for abelian programs that improve the best known communication complexity. If inputs take any value of an abelian group G, our protocol achieves the communication complexity O(| G| (log | G| ) ²) improving O(| G| ²n²) of Beimel et al. (Crypto 2014). If players are limited to inputs from subsets of size at most d, our protocol achieves | G| (log | G| ) ²(max { n, d} ) ^(1+o(1))t where t is a corruption threshold. This result improves | G| ³(nd) ^(1+o(1))t of Beimel et al. (Crypto 2014), and even | G| ^logn+O(1)n of Benhamouda et al. (Crypto 2017) if t= o(log n) and | G| = n^Θ(1).We propose for the first time NIMPC protocols for linear classifiers that are more efficient than those obtained from the generic construction.We revisit a known transformation of Benhamouda et al. (Crypto 2017) from Private Simultaneous Messages (PSM) to NIMPC, which we repeatedly use in the above results. We reveal that a sub-protocol used in the transformation does not satisfy the specified security. We also fix their protocol with only constant overhead in the communication complexity. As a byproduct, we obtain an NIMPC protocol for indicator functions with asymptotically optimal communication complexity with respect to the input length.