Paper 2026/378 Original: eprint.iacr.org/2026/378 ↗
Information-Theoretic Network-Agnostic MPC with Polynomial Communication
Abstract
Network-agnostic MPC protocols tolerate simultaneously a higher number of corruptions $t_s < n/2$ when the network is synchronous, and a lower number $t_a < n/3$ when the network is asynchronous. As such, they provide strong resilience, irrespective of the type of underlying communication network. We focus on improving the communication complexity of network-agnostic MPC with optimal resilience $2t_s + t_a < n$. In this regime, there are no polynomial-time information-theoretic solutions and current computational protocols (without fully-homomorphic encryption) communicate $O(n^2)$ elements per multiplication gate. In this work, we significantly advance the landscape by introducing the first information-theoretic protocol with quadratic communication per multiplication gate and the first computational protocol with linear communication per multiplication gate based solely on signatures and symmetric-key encryption.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2026-02-24: last updated
- 2026-02-24: published
- Short URL
- https://ia.cr/2026/378
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/378,
author = {Xiaoyu Ji and Chen-Da Liu-Zhang and Daniel Pöllmann and Yifan Song},
title = {Information-Theoretic Network-Agnostic MPC with Polynomial Communication},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/378},
year = {2026},
url = {https://eprint.iacr.org/2026/378}
}