On the (In)Efficiency of Non-Interactive Secure Multiparty Computation

Secure multi-party computation (MPC) enables multiple players to cooperatively evaluate various functions in the presence of adversaries. In this paper, we consider non-interactive MPC (NIMPC) against honest-but-curious adversaries in the information-theoretic setting, which was introduced by Beimel et al. in CRYPTO 2014. Their main focus is to realize stronger security while completely avoiding interaction, and succeeded to show that every function admits a fully robust NIMPC protocol. A drawback of this positive result is the communication complexity, which is linear in the size of the input domain (i.e., exponential in the input length). We first prove that this inefficiency is essentially unavoidable by deriving a lower bound on the communication complexity. However, there is an exponential gap between the derived lower bound and the previous construction. We then reduce the gap between the lower and upper bounds to quadratic in the input length by presenting a much more efficient construction of an important building block, which is an NIMPC protocol for indicator functions.