Concretely Efficient Fluid MPC with Linear Communication
摘要
Traditional Secure Multi-Party Computation (MPC) req-uires parties to stay online through the whole computation, which compromises scalability when dealing with large-scale and complex tasks. The notion of fluid MPC, introduced by Choudhuri et al. (Crypto 2021), aims to address this challenge by presenting a dynamic participation model where parties have the flexibility to join and leave as needed. The best-known honest-majority MPC protocol by Bienstock et al. (Crypto 2023) in the fluid setting achieves linear communication complexity, but still incurs a substantially higher communication overhead than MPC in the classical setting. In this paper, we present two concretely efficient fluid MPC protocols in the honest-majority setting. The first, \(\textsf{Velora}\) , is an unconditionally secure maximal-fluid MPC protocol, which achieves the lowest communication cost among maximally fluid MPC protocols by introducing a new approach of transferring the output sharings held by the current committee to the next committee. To eliminate the inherent overhead of \(\textsf{Velora}\) , we also propose a separation-generation approach for random double sharings and integrate it into the second protocol as \(\textsf{Ion}\) . As a trade-off, \(\textsf{Ion}\) relaxes the fluidity requirement to the submaximal fluidity, allowing an extra internal communication round for each committee. Both protocols \(\textsf{Velora}\) and \(\textsf{Ion}\) enable us to extend the ATLAS technique from the classical setting to the fluid setting for further lowering communication overhead. Compared to the best-known fluid MPC protocol, our protocols reduce the communication cost per multiplication gate by a factor of \(5.4 \sim 7.5 \times \) (resp., \(20.7 \sim 28 \times \) ) for semi-honest security (resp., malicious security). Compared to the state-of-the-art ATLAS protocol by Goyal et al. (Crypto 2021) in the classical setting, our semi-honest protocols only introduce a \(1 \sim 1.5\times \) larger communication overhead for securely computing multiplication gates.