Paper 2026/1555
Non-Interactive Secure Computation with Constant Communication Overhead
, Technion and AWS, University of Toronto, University of TorontoAbstract
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
- A major revision of an IACR publication in EUROCRYPT 2026
- DOI
- 10.1007/978-3-032-25324-8_5
- Keywords
- MPCNISCCommunication Cost
- Contact author(s)
-
yuval ishai @ gmail com
ziyang @ cs toronto edu
naty @ post bgu ac il
akshayaram srinivasan @ utoronto ca - History
- 2026-08-03: approved
- 2026-07-29: received
- See all versions
- Short URL
- https://ia.cr/2026/1555
- License
-
CC BY
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},
doi = {10.1007/978-3-032-25324-8_5},
url = {https://eprint.iacr.org/2026/1555}
}
