Communication-Efficient Multi-Party Computation for RMS Programs
Authors
Abstract
Despite much progress, general-purpose secure multi-party computation (MPC) with active security may still be prohibitively expensive in settings with large input datasets. This particularly applies to the secure evaluation of graph algorithms, where each party holds a subset of a large graph. Recently, Araki et al. (ACM CCS '21) showed that dedicated solutions may provide significantly better efficiency if the input graph is sparse. In particular, they provide an efficient protocol for the secure evaluation of “message passing” algorithms, such as the PageRank algorithm. Their protocol's computation and communication complexity are both
In this work, we show that PageRank can instead be captured efficiently as a restricted multiplication straight-line (RMS) program, and present a new actively secure MPC protocol tailored to handle RMS programs. In particular, we show that the local knowledge of the participants can be leveraged towards the first maliciously-secure protocol with communication complexity linear in
References
How to cite
Thomas Attema, Aron van Baarsen, Stefan van den Berg, Pedro Capitão, Vincent Dunning, and Lisa Kohl, Communication-Efficient Multi-Party Computation for RMS Programs. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ab0lmp-3y.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.