Secure Multi-Party Computation Made Simple

Published on Feb 3, 2026

·

~ 9 min read

Reference: https://crypto.ethz.ch/publications/files/Maurer06.pdf

Basic Terms

A secret-sharing scheme allows a dealer to share a value among a set $P = {p_1,..., p_n}$ of players. Only certain qualified subsets of players can reconstruct the secret. Other subsets, called ignorant sets, obtain no information about it. Natural secret-sharing schemes, including those in this paper, ensure that every subset of P is either qualified or ignorant.

An ignorant player set holds partial information about the shared value but must not obtain any additional information. In other words, what an ignorant set receives is statistically independent of both the information they already hold and the shared value. Put another way, such an ignorant set can simulate their shares with the same probability distribution as in the actual protocol.

The access structure is the set of parties who can combine their shares to reconstruct the complete secret. Typically, we refer to the minimum number of parties needed in such a set. Similarly, the adversary structure is the maximum size of corrupt parties who, when combining their shares, should not be able to reconstruct the original secret (this is what we want).

Main Idea of the Paper

Due to linearity, secure addition—and more generally, computing any linear function of shared values—is trivial. Every player locally computes the linear function of their shares and keeps the result as a share of the new value. Secrecy is trivially guaranteed because this step involves no communication. Correctness is also trivially guaranteed because, without communication, there is no chance for a corrupted player to cheat. Hence, the only remaining problem is the secure multiplication of shared values.

  • k out of k sharing Select $k_i - 1$ shares $s_1, ..., s_{k-1}$ at random from $D$ and let $s_k := s - \sum_{i=1}^{k-1}s_i$. The $i^{th}$ share is $s_i$.

This is a secret sharing scheme since you need all to add up to get the secret, and all $s_i$ are uniformly distributed and random.

The Secret-Sharing Scheme

The paper uses a "dual" approach to sharing, focusing on what an attacker cannot see.

The Setup

  • Secrecy Structure $\Sigma$: A collection of sets ${T_1, \dots, T_k}$ representing all possible groups of players that an adversary could corrupt.
  • Complement Sets: For every "bad" group $T_i$, we define a "good" group $\overline{T_i}$ (everyone not in $T_i$).

The Protocol

  1. Split: The secret $s$ is split into $k$ random shares $(s_1, \dots, s_k)$ such that $s = \sum s_i$ (k-out-of-k sharing).
  2. Distribute: Each share $s_i$ is sent to every player in the complement set $\overline{T_i}$ .
  3. Player Knowledge: A player $p_m$ holds the set of shares ${s_i: m \in \overline{T_i}}$ .

Why it's Secure

  • Any group $T_i \in \Sigma$ is, by definition, missing at least one share (specifically $s_i$).
  • Without that one share, the secret remains perfectly hidden (information-theoretically secure).

The Multiplication Protocol

Multiplication is the only step requiring communication. It relies on the condition $Q^2(\Sigma)$, meaning no two sets in the secrecy structure cover the whole group $T_1 \cup T_2 \neq P$.

The Mechanism

We want to compute $st = (\sum s_i) \cdot (\sum t_j) = \sum_{i,j} s_i t_j$.

Step Action Logic
1. Partition Assign each pair $(i, j)$ to a player $p_m$ who knows both shares $s_i$ and $t_j$ At least one such player always exists if $Q^2(\Sigma)$ holds.
2. Local Sum Player $p_m$ computes $v_m = \sum s_i t_j$ for all their assigned pairs. This is a "piece" of the final product.
3. Reshare Player $p_m$ shares $v_m$ among the group using the same basic secret-sharing scheme. Uses new independent randomness to maintain secrecy.
4. Finalize Players locally add the received shares of all $v_m$. This results in a valid sharing of the product $st$

Example

We'll multiply $z = x \cdot y$.

In a (4, 1) RSS, each secret is split into 4 shares $(x_1, x_2, x_3, x_4)$ such that $\sum x_i = x$.

Recall our "Missing Piece" distribution:

  • $P_1$ has: $(x_2, x_3, x_4)$ and $(y_2, y_3, y_4)$
  • $P_2$ has: $(x_1, x_3, x_4)$ and $(y_1, y_3, y_4)$
  • $P_3$ has: $(x_1, x_2, x_4)$ and $(y_1, y_2, y_4)$
  • $P_4$ has: $(x_1, x_2, x_3)$ and $(y_1, y_2, y_3)$

Step 1: The Local Product (The "Expansion")

Multiplying $(\sum x_i) \cdot (\sum y_j)$ gives us 16 terms: $x_1y_1, x_1y_2, \dots, x_4y_4$. We assign each term to one specific player who already holds both indices. This keeps things secure and efficient.

We define the local sums L_i as follows:

  • $P_1$ computes $L_1$: $x_2y_2 + x_2y_3 + x_2y_4 + x_3y_2 + x_4y_2$
  • $P_2$ computes $L_2: x_3y_3 + x_3y_4 + x_3y_1 + x_4y_3 + x_1y_3$
  • $P_3$ computes $L_3: x_4y_4 + x_4y_1 + x_4y_2 + x_1y_4 + x_2y_4$
  • $P_4$ computes $L_4: x_1y_1 + x_1y_2 + x_1y_3 + x_2y_1 + x_3y_1$

Note: Each of the 16 terms appears exactly once across these four sums. Therefore, $L_1 + L_2 + L_3 + L_4 = x \cdot y$.

Step 2: Random Masking (Zero-Sharing)

If $P_1$ simply sent $L_1$ to the others, they might learn something about $x$ or $y$. We need to "blind" these values. The players use pre-shared random seeds to generate values that sum to zero.

Each pair of players $(P_i, P_j)$ shares a random number $r_{i,j}$.

  • $P_1$ calculates: $M_1 = L_1 + r_{1,2} + r_{1,3} + r_{1,4}$
  • $P_2$ calculates: $M_2 = L_2 - r_{1,2} + r_{2,3} + r_{2,4}$
  • $P_3$ calculates: $M_3 = L_3 - r_{1,3} - r_{2,3} + r_{3,4}$
  • $P_4$ calculates: $M_4 = L_4 - r_{1,4} - r_{2,4} - r_{3,4}$

Now, $\sum M_i = \sum L_i = x \cdot y$. Each $M_i$ is a random-looking share of the product.

Step 3: Resharing (Who Sends What)

We need to distribute $M_1, M_2, M_3, M_4$ so they follow the (4, 1) RSS rule again. For the new secret $z$, we want:

  • $P_1$ to have $z_2, z_3, z_4$
  • $P_2$ to have $z_1, z_3, z_4$

...and so on.

Each player $P_i$ defines their masked value $M_i$ as the new share $z_i$, then sends it to everyone except themselves.

The Communication Table:

  1. $P_1$ sends $M_1$ to $P_2, P_3, P_4$
  2. $P_2$ sends $M_2$ to $P_1, P_3, P_4$
  3. $P_3$ sends $M_3$ to $P_1, P_2, P_4$
  4. $P_4$ sends $M_4$ to $P_1, P_2, P_3$

Step 4: Final State (What Does Everyone Have?)

After receiving the messages, here's what each player holds:

  • $P_1$ received $M_2, M_3, M_4$. It already knew its own $M_1$ but doesn't keep it (following the "missing piece" rule). So $P_1$ now holds $(z_2, z_3, z_4).$
  • $P_2$ received $M_1, M_3, M_4.$ It now holds $(z_1, z_3, z_4).$
  • $P_3$ received $M_1, M_2, M_4.$ It now holds $(z_1, z_2, z_4).$
  • $P_4$ received $M_1, M_2, M_3.$ It now holds $(z_1, z_2, z_3).$

Success! We've computed $z = x \cdot y$, and the result is perfectly shared in (4, 1) RSS format. No single player knows $z.$ Each player only sees random masks $M_j,$ which the Simulator can easily replicate.

Comparison: Maurer vs. Beaver-Wool

  • Beaver-Wool (BW98): Based on minimal qualified sets. Requires the $Q^2$ condition just to reconstruct a secret.
  • Maurer (This Paper): Dual approach. Does not require $Q^2$ for reconstruction, only for multiplication.
  • The Advantage: Maurer's scheme can be enhanced to handle active corruption, whereas Beaver-Wool cannot.

Would you like me to move on to Section 6, where we introduce "Active Corruption" and how to make this multiplication robust against cheaters?

Section 5 of the paper focuses on the Passive Case, where the primary goal is to ensure the secrecy of data against "semi-honest" players who follow the rules but try to learn everything they can.

Here are the Notion-ready notes for this section.

To move from the Passive Case to the Active Case, we must assume the adversary is no longer just "curious" but is now "evil"—they can make corrupted players lie, send false data, or stop participating entirely.

Section 6 of the paper introduces Verifiable Secret Sharing (VSS) and a Robust Multiplication Protocol to ensure that even if some players cheat, the computation remains correct and private.

The Adversary Model: (Σ, Δ)

In this scenario, we don't just have one secrecy structure. We have two:

  • $\Sigma$ (Secrecy Structure): The sets of players who, if corrupted, should not learn any information.
  • $\Delta$ (Adversary Structure): The sets of players who can actively cheat and deviate from the protocol.
  • Rule: For a computation to be secure and correct, the paper proves we need the condition: $P \notin \Sigma \sqcup \Delta \sqcup \Delta$ for VSS , and $P \notin \Sigma \sqcup \Sigma \sqcup \Delta$ for multiplication.

Verifiable Secret Sharing (VSS)

Standard secret sharing fails if the Dealer sends different values to different people or if players lie during reconstruction. VSS fixes this using Pairwise Checks and Broadcasts.

Step-by-Step VSS Protocol:

  1. Distribution: The Dealer splits the secret $s$ into $s_1, \dots, s_k$ and sends $s_i$ to everyone in $\overline{T_i}.$
  2. The Consistency Check: Every pair of players who were supposed to receive the same share $s_i$ talk to each other over a secure channel.
    • Example: If $P_1$ and $P_2$ both received $s_3$, they compare notes.
  3. Complaint & Resolution: If their values don't match, they broadcast a complaint.
    • The Dealer must then broadcast the correct value of $s_i$ to everyone.
    • If the Dealer refuses or lies again, they are disqualified.
  4. Robust Reconstruction: During the final reveal, players send their shares to each other. Each player looks for the unique value that matches most of the shares, ignoring the "noise" created by cheaters in $\Delta.$

Robust Multiplication Protocol

The passive multiplication fails if a player shares a false product $s_i t_j$. To prevent this, we use a "Check then Compute" approach.

The Example: Computing $x \cdot y$ Robustly

Imagine we have the same 3-player setup. We want to ensure the term $x_1 y_2$ is calculated correctly.

  • Step 1: Redundant Sharing: Instead of just one player calculating $x_1 y_2$, every player who knows both indices (e.g., $P_3$ and $P_4$) calculates it and shares it using VSS.
  • Step 2: The Zero-Knowledge Check: Let's say $P_3$ shares $v_a$ and $P_4$ shares $v_b$. They should be identical.
    • The players locally compute the difference $D = v_a - v_b$.
    • They "open" $D$. If $D = 0$, they know the shares were likely correct and use $v_a.$
  • Step 3: Fault Recovery: If $D \neq 0$, someone is lying.
    • The protocol immediately pauses and reconstructs the original shares $x_1$ and $y_2$ publicly.
    • Since these shares are now public, everyone can just compute $x_1 \cdot y_2$ themselves and continue.

Why This Works

The paper notes that even if we have to reconstruct a share publicly (Step 3), secrecy is not lost. This is because a conflict only happens if at least one player in the set is a cheater—and if they are a cheater, they already knew those shares anyway!

This is just a little understanding of the paper! Very nice paper.