Abstract: | We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating $t<n/3$ active corruptions while \textit{guaranteeing output delivery} (G.O.D.).
Our protocol is based on replicated secret-sharing, whose share size is known to grow exponentially with the number of parties $n$.
However, even though the internal storage and computation in our protocol remains exponential, the communication complexity of our protocol is \emph{constant}, unlike most previous works based on replicated secret-sharing for any number of parties. Furthermore, the communication complexity of our protocol is not only constant, but very small: only $1 + \frac{t-1}{n}<1\frac{1}{3}$ ring elements per party, per multiplication gate, on average.
This improves over the state-of-the art protocol in the same setting by Furukawa and Lindell (CCS 2019), which has a communication complexity of $2\frac{2}{3}$ \emph{field} elements per party, per multiplication gate and while achieving fairness only.
Furthermore, for the base case of this setting, namely, $n=4$ and $t=1$, our protocol requires sending~\textit{1 ring element per party per multiplication}, which improves over the protocols by Dalskov et al.and Koti et al.(USENIX 2021), which require $1\frac{1}{2}$ ring elements, and also over the protocol of Koti et al.~(NDSS 2022), which requires $1\frac{1}{4}$ ring elements. Motivated by the fact that efficiency of distributed protocols are much more penalized by high communication complexity than local computation/storage, we perform a detailed analysis together with experiments in order to explore how large the number of parties can be, before the storage and computation overhead becomes prohibitive.
Our results show that our techniques are viable even for a moderate number of parties (e.g., $n>10$). |
Bio: | Daniel Escudero is a researcher on Cryptography with interests in Secure Multiparty Computation, Distributed Systems, Privacy-Preserving Machine Learning, among others. Daniel completed his PhD from Aarhus University, Denmark, in November 2021, and he currently holds a research position at JP Morgan AI Research, New York. |
