International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity

Authors:
Alexander Bienstock , J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE
Daniel Escudero , J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE
Antigoni Polychroniadou , J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE
Download:
DOI: 10.62056/aesg89n4e
URL: https://cic.iacr.org/p/1/4/28
Search ePrint
Search Google
Abstract:

The Fluid multiparty computation (MPC) model, introduced in (Choudhuri et al. CRYPTO 2021), addresses dynamic scenarios where participants can join or leave computations between rounds. Communication complexity initially stood at $\Omega(n^2)$ elements per gate, where $n$ is the number of parties in a committee online at a time. This held for both statistical security (honest majority) and computational security (dishonest majority) in (Choudhuri et al. CRYPTO'21) and (Rachuri and Scholl, CRYPTO'22), respectively. The work of (Bienstock et al. CRYPTO'23) improved communication to $O(n)$ elements per gate. However, it's important to note that the perfectly secure setting with one-third corruptions per committee has only recently been addressed in the work of (David et al. CRYPTO'23). Notably, their contribution marked a significant advancement in the Fluid MPC literature by introducing guaranteed output delivery. However, this achievement comes at the cost of prohibitively expensive communication, which scales to $\Omega(n^9)$ elements per gate.

In this work, we study the realm of perfectly secure Fluid MPC under one-third active corruptions. Our primary focus lies in proposing efficient protocols that embrace the concept of security with abort. Towards this, we design a protocol for perfectly secure Fluid MPC that requires only linear communication of $O(n)$ elements per gate, matching the communication of the non-Fluid setting. Our results show that, as in the case of computational and statistical security, perfect security with abort for Fluid MPC comes “for free” (asymptotically linear in $n$) with respect to traditional non-Fluid MPC, marking a substantial leap forward in large scale dynamic computations, such as Fluid MPC.

BibTeX
@article{cic-2025-34921,
  title={Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 4},
  url={https://cic.iacr.org/p/1/4/28},
  doi={10.62056/aesg89n4e},
  author={Alexander Bienstock and Daniel Escudero and Antigoni Polychroniadou},
  year=2025
}