We observe that the circuits used in many important applications of MPC such as training algorithms used to create machine learning models have a highly repetitive structure. We formalize this class of circuits and propose an MPC protocol that achieves O(|C|) total complexity for this class. We implement our protocol and show that it is practical and outperforms O(n|C|) protocols for modest numbers of players.
Category / Keywords: cryptographic protocols / Secure multiparty computation Original Publication (with major differences): IACR-EUROCRYPT-2021 Date: received 18 Apr 2021, last revised 3 Nov 2021 Contact author: gbeck at cs jhu edu, aarushig at cs jhu edu, abhishek at cs jhu edu, kaptchuk at bu edu Available format(s): PDF | BibTeX Citation Version: 20211103:201609 (All versions of this report) Short URL: ia.cr/2021/500