Non-interactive Secure Computation with Constant Communication Overhead

We study the communication complexity of non-interactive secure computation (NISC) protocols with security against malicious adversaries. We give a general NISC protocol for any two-party function computed by a Boolean circuit $C$ using only $O(|C|\lambda)$ bits of communication, where $\lambda$ is a computational security parameter. This protocol is unconditionally secure in the random oracle model, assuming a standard random bit OT correlations setup. Compared to Yao's semi-honest protocol, our protocol incurs only a constant communication overhead and achieves security against malicious parties with no additional interaction. Prior works achieved such constant overhead by either using a larger number of rounds or more structured correlations.