MPC Protocols

The Arcium Network initially supports the BDOZ MPC protocol, but over time multi-protocol support will be added.

MPC protocols come in many flavors, striking different tradeoffs in their security models, efficiency and cryptographic assumptions. In terms of security models, we distinguish two types:

• Honest Majority: this assumes that at least N/2 participants are honest, meaning they do not maliciously deviate from the protocol.

• Dishonest Majority: in this model, up to N-1 participants can maliciously collude and still be unable to extract information from the honest participant, or falsify an output.

Additionally, protocols may vary in their underlying cryptographic assumptions:

• Computationally secure systems rely on the assumed hardness of a problem for their security, for example factoring large numbers. This requires a certain amount of care, as assumptions that are true today may become challenged at some point in the future, e.g. by quantum computers.

• Information-theoretically secure systems achieve security based on information theory, without relying on any computational hardness assumptions. Additive secret sharing falls into this category, as it is impossible to derive any information about the underlying value without having access to all the shares.

State-of-the-art protocols, such as BDOZ or SPDZ, typically adopt the so-called preprocessing model, where the most expensive parts of the protocol are independent of the computation and can therefore be conducted in advance in a so-called "offline phase". The computation is then executed in the online phase, which is much faster, and consumes some of the data produced in the offline phase. Preprocessing data can therefore be generated during times of lighter load, allowing nodes to remain flexible in their resource allocation.

Dishonest Majority Protocols

As described above, this category of protocols can handle all but one participant being malicious without the possibility of falsifying results or leaking information. Coupled with external game theoretic incentives, this assumption provides the strongest soundness and security guarantees for computations. In this setting, two of the most used secret sharing-based protocols are SPDZ and BDOZ, as well as their variants.

Both of these systems rely on the use of secret sharing, i.e. splitting up a value and providing a share to each participant. The properties of these shares allow the addition of two shares and multiplication by a constant to be performed locally by each peer. Share multiplication requires some communication between peers. To verify the soundness of a value when it is sent from one peer to another, these schemes rely on MACs (Message Authentication Codes) which cannot be forged by peers. As such, these MACs help guarantee that no cheating has occurred: if forgery is spotted, a peer can choose to unilaterally abort the protocol.

It's important to understand that while the online phase actually executes the computation, the offline phase is where the most expensive and complex operations happen, opening up large opportunities for optimization. As such, while the online phases have undergone little change since the original papers, the offline phases have witnessed significant speedups, often by orders of magnitude. We can count roughly two main ways of running these offline phases:

1. Oblivious transfer-based protocols: OT is a simple but powerful cryptographic primitive that allows a sender to send two messages A and B to a receiver, who can then learn either A or B, while not letting the sender know which one he picked. These protocols can typically be made computationally efficient but involve heavy communication overhead between players, though recent advances in OT protocols, such as silent OTs, have made these methods significantly more competitive.

2. FHE and ZKP-based methods: these protocols combine Fully Homomorphic Encryption (FHE) and Zero-Knowledge Proofs (ZKPs) to pass around messages between peers in an encrypted manner and compute on them as needed to produce valid preprocessing values. The ZKPs are typically used to verify the correctness of the FHE ciphertexts, ensuring peers cannot maliciously deviate from the protocol without being detected. These protocols are rather efficient in terms of their communication overhead, but the computations involved for FHE remain fairly heavy despite recent advances.

Honest majority protocols

In a setting where you can reliably trust over half of the peers in a computation, using honest majority protocols such as GSZ can lead to significant efficiency gains. GSZ uses Shamir secret sharing and deferred batch checks to achieve reduced computational and communication overhead.