MPC Protocol with Additions and Multiplications for FREE

DaWNFoRCe

11/9/23, 7:36 AM

Imagine an MPC protocol where both multiplications and additions come for free (2 round). The protocol works over arithmetic circuits, and the security setup is as relaxed as possible:

Semi-Honest.
Honest Majorities.

Does such a protocol exist?
If so, what would be the most restrictive security model, and maintain the 2 rounds?

0 + 2

multiparty-computation

homomorphic-encryption

secret-sharing

lamba

11/24/23, 10:04 AM

How do you define "free"? Do you want the communication cost to be independent to the number of additions and multiplications? and require constant round complexity? Usually secret-sharing or GC-based MPC protocols don't have these properties, but you can probably achieve using FHE. The communication complexity would be proportional to the size of the input (plus the key switching keys which might be big). But FHE is much more expensive computationally.

DaWNFoRCe

12/7/23, 6:50 AM

@lamba. Thanks so much for your comment. Indeed, free in this case means, round complexity. I am aware of impossibility results stating that I need at least 2 rounds.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: MPC Protocol with Additions and Multiplications for FREE

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.