Paper 2022/623
Fast Fully Secure MultiParty Computation over Any Ring with TwoThirds Honest Majority
Anders Dalskov, Daniel Escudero, and Ariel Nof
Abstract
We introduce a new MPC protocol to securely compute any functionality over an arbitrary blackbox 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 secretsharing, 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}, except for a light constantround check that is performed at the end before revealing the output. Furthermore, the amortized communication complexity of our protocol is not only constant, but very small: only $1 + \frac{t1}{n}<1\frac{1}{3}$ ring elements per party, per multiplication gate over two rounds of interaction. This improves over the stateofthe 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. As an alternative, we also describe a variant of our protocol which has only one round of interaction per multiplication gate on average, and amortized communication cost of $\le 1\frac{1}{2}$ ring elements per party on average for any natural circuit. 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$).
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Minor revision. The ACM Conference on Computer and Communications Security 2022 (CCS'22)
 Keywords
 Multiparty ComputationHonest MajorityRobust Computation
 Contact author(s)

daniel escudero @ protonmail com
ariel nof @ biu ac il
anderspkd @ fastmail com  History
 20220523: received
 Short URL
 https://ia.cr/2022/623
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/623, author = {Anders Dalskov and Daniel Escudero and Ariel Nof}, title = {Fast Fully Secure MultiParty Computation over Any Ring with TwoThirds Honest Majority}, howpublished = {Cryptology ePrint Archive, Paper 2022/623}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/623}}, url = {https://eprint.iacr.org/2022/623} }