Key Contribution

The MPC Puzzle

A unification of 2-, 3-, and 4-party secret-sharing schemes — showing how seemingly separate frameworks share a common algebraic foundation and can convert between each other.

2-Party (2PC)

Dishonest Majority

Algebraic Structure $\mathbb{Z}_{2^{\ell}}$, $\mathbb{Z}_2$, $\mathbb{F}_p$

Security SH / Active-Covert

Techniques OT, HE, GC, FSS, SS

Representative SecureML, CryptFlow2, Llama

Largest class. Typically client-server or outsourcing setting. Relies on OT/HE for garbling and secret sharing between two mutually distrusting parties.

3-Party (3PC)

Honest Majority

Algebraic Structure $\mathbb{Z}_{2^{\ell}}$, $\mathbb{F}_p$

Security SH / A / F / R

Techniques Replicated SS, OT

Representative ABY3, Falcon, SecureNN

Efficient semi-honest protocols with strong honest majority assumption. Replicated secret sharing enables cheap multiplications with low communication rounds.

4-Party (4PC)

Super Honest Majority

Algebraic Structure $\mathbb{Z}_{2^{\ell}}$, $\mathbb{Z}_2$

Security A/R / F/R

Techniques Replicated SS

Representative FLASH, Trident, Tetrad

Strongest security guarantees — tolerates up to one active corruption with guaranteed output delivery (robustness). Higher communication but maximum resilience.

Secret-Sharing Schemes

The three algebraic building blocks unified across every party configuration

Additive sharing

a value $x$ is additively shared among $n$ parties if each party $P_i$ holds a share $x_i$ such that $x = \sum_{i=1}^{n} x_i$.

Replicated sharing

a value $x$ is in replicated sharing among $n$ parties with threshold $t$ (where $n > 2t+1$) if $x$ is split into $q = \binom{n}{t}$ additive shares, each held by every party in the complementary set for that share — so any $t+1$ or more parties can reconstruct $x$.

Masked sharing

a value $x$ is in masked sharing among $n$ parties if there exist $\hat{x}, \lambda_x$ such that $\hat{x} = x + \lambda_x$, where $\hat{x}$ is a masked value known to all parties and $\lambda_x$ is a random mask secret-shared among the parties (additively or via replicated sharing).

any scheme can be converted to any other by re-sharing — treat each share under the source scheme as a fresh input to the destination scheme's input-sharing protocol, then linearly recombine. This always works (thanks to linearity) but is rarely optimal; the tables below give the better, scheme-specific protocols.

Conversion Costs

Communication cost per secret-shared element, from the paper's Appendix E

Same party set

Cross party set

From \ To

All costs are in bits per element. = ring/field bitwidth. A range (e.g. ) gives the communication-optimized protocol first, the direct one-round protocol second. Source: Appendix E.

Insight: Share Conversions

Within a fixed party set, whether a conversion is local or interactive is fully determined by whether it discards or constructs redundancy. Reducing to additive sharing (a) is always local, and masked-to-replicated (m→r) is local too since the mask is already replicated-shaped. Every other direction requires at least one round, with cost depending on how much redundancy the source scheme already carries. Once the party set itself changes, this locality disappears entirely: every cross-party-set conversion above requires a full reshare, regardless of scheme.

Full Details in the Paper