Paper 2026/1555 Original: eprint.iacr.org/2026/1555 ↗
Non-Interactive Secure Computation with Constant Communication Overhead
Abstract
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2026-07-29: last updated
- 2026-07-29: published
- Short URL
- https://ia.cr/2026/1555
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/1555,
author = {Yuval Ishai and Ziyang Jin and Naty Peter and Akshayaram Srinivasan},
title = {Non-Interactive Secure Computation with Constant Communication Overhead},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1555},
year = {2026},
url = {https://eprint.iacr.org/2026/1555}
}