Paper 2023/839

On Linear Communication Complexity for (Maximally) Fluid MPC

Alexander Bienstock, New York University
Daniel Escudero, J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE
Antigoni Polychroniadou, J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE

Secure multiparty computation protocols with dynamic parties, which assume that honest parties do not need to be online throughout the whole execution of the protocol, have recently gained a lot of traction for computations of large scale distributed protocols, such as blockchains. More specifically, in Fluid MPC, introduced in (Choudhuri et al. CRYPTO 2021), parties can dynamically join and leave the computation from round to round. The best known Fluid MPC protocol in the honest majority setting communicates $O(n^2)$ elements per gate where $n$ is the number of parties online at a time. While Le Mans (Rachuri and Scholl, CRYPTO 2022) extends Fluid MPC to the dishonest majority setting with preprocessing, it still communicates $O(n^2)$ elements per gate. In this work we present alternative Fluid MPC solutions that require $O(n)$ communication per gate for both the information-theoretic honest majority setting and the information-theoretic dishonest majority setting with preprocessing. Our solutions also achieve maximal fluidity where parties only need to be online for a single communication round. Additionally, we show that a protocol in the information-theoretic dishonest majority setting with sub-quadratic $o(n^2)$ overhead per gate requires for each of the $N$ parties who may ever participate in the (later) execution phase, $\Omega(N)$ preprocessed data per gate.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2023
MPCFluid MPCHonest MajorityDishonest MajorityLower Bound
Contact author(s)
abienstock @ cs nyu edu
daniel escudero @ protonmail com
antigonipoly @ gmail com
2023-06-06: approved
2023-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander Bienstock and Daniel Escudero and Antigoni Polychroniadou},
      title = {On Linear Communication Complexity for (Maximally) Fluid MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2023/839},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.