Paper 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
- A minor revision of an IACR publication in EUROCRYPT 2026
- Keywords
- MPCNetwork-AgnosticInformation-Theoretic SecureGuarantee Output Delivery
- Contact author(s)
-
jixy23 @ mails tsinghua edu cn
chen-da liuzhang @ hslu ch
daniel poellmann @ hslu ch
yfsong @ mail tsinghua edu cn - History
- 2026-02-25: approved
- 2026-02-24: received
- See all versions
- Short URL
- https://ia.cr/2026/378
- License
-
CC BY
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}
}
