Multi-Party Computation (MPC), in depth: secret-shared arithmetic, Beaver triples, garbled circuits and security models

What secure means

The definition is a thought experiment. Imagine an incorruptible trusted party: everyone sends it their input, it computes f and hands back the output. This is the ideal world. A protocol is secure if anything an adversary can do or learn in the real protocol, it could also do or learn in the ideal world. Formally, there is a simulator that produces the adversary's view using only the corrupted parties' inputs and the output. The consequence matters in practice: MPC never hides what the output itself reveals. If the output is the sum of three salaries, two colluding parties can subtract their own and learn the third. Choosing f is part of the security design.

Two axes classify the adversary. A semi-honest (passive) adversary follows the protocol but reads everything it sees. A malicious (active) adversary deviates arbitrarily: it sends wrong shares, aborts or lies about inputs. The second axis is how many parties it corrupts. With an honest majority, protocols built on Shamir sharing are fast and need no expensive public-key operations per gate. With a dishonest majority, the setting that covers every two-party case, you need heavier machinery: oblivious transfer or homomorphic encryption for preprocessing, and in the malicious case information-theoretic MACs on every share, as the SPDZ family does. Malicious security with a dishonest majority cannot guarantee that everyone gets the output, only that cheating is detected and the protocol aborts.

What secure means

The definition is a thought experiment. Imagine an incorruptible trusted party: everyone sends it their input, it computes f and hands back the output. This is the ideal world. A protocol is secure if anything an adversary can do or learn in the real protocol, it could also do or learn in the ideal world. Formally, there is a simulator that produces the adversary's view using only the corrupted parties' inputs and the output. The consequence matters in practice: MPC never hides what the output itself reveals. If the output is the sum of three salaries, two colluding parties can subtract their own and learn the third. Choosing f is part of the security design.

Two axes classify the adversary. A semi-honest (passive) adversary follows the protocol but reads everything it sees. A malicious (active) adversary deviates arbitrarily: it sends wrong shares, aborts or lies about inputs. The second axis is how many parties it corrupts. With an honest majority, protocols built on Shamir sharing are fast and need no expensive public-key operations per gate. With a dishonest majority, the setting that covers every two-party case, you need heavier machinery: oblivious transfer or homomorphic encryption for preprocessing, and in the malicious case information-theoretic MACs on every share, as the SPDZ family does. Malicious security with a dishonest majority cannot guarantee that everyone gets the output, only that cheating is detected and the protocol aborts.

Additive secret sharing

Fix a prime p and work in the integers mod p. To share a value x among n parties, pick n - 1 uniformly random numbers as the first shares and set the last share so that all n add up to x mod p. Any n - 1 shares are uniformly random and independent of x, so a coalition missing even one share learns nothing. This is n-of-n additive sharing, and the notation [x] means "x, held as shares".

Linear operations are free. If every party adds its share of x to its share of y, the results are shares of x + y; no messages are sent. Multiplying by a public constant is also local. Adding a public constant k is done by one designated party, since if all n parties added k the result would be shifted by nk. So any linear function of the inputs, such as a sum, a weighted score or a count, costs one round to distribute inputs and one round to open the output. Everything interesting happens at multiplication, because the product of two shares is not a share of the product: (x1 + x2)(y1 + y2) has cross terms that no single party can compute.

Multiplication with Beaver triples

Beaver's 1991 trick moves the hard part to a phase that does not depend on the inputs. Suppose the parties already hold shares of a random triple [a], [b], [c] with c = ab, where a and b are uniform and nobody knows them. To multiply [x] by [y], each party computes its share of d = x - a and e = y - b and broadcasts it, so d and e become public. Revealing them is safe because a and b act as one-time pads: d is uniformly random whatever x is. Then the identity

xy = c + d*b + e*a + d*e

lets each party compute a share of xy locally: its share of c, plus d times its share of b, plus e times its share of a, with one party also adding the public product de. One multiplication costs one triple and one round in which every party sends two field elements. Multiplications at the same depth of the circuit share that round, so latency scales with the multiplicative depth of f, not its size.

The rule that follows is absolute: a triple is used exactly once. If the same (a, b) masks two different inputs x and x', an observer sees x - a and x' - a and subtracts them to get x - x'.

A tested implementation

This is a semi-honest, three-party simulation over the Mersenne prime 2^61 - 1. A dealer function stands in for the offline phase so the online arithmetic is visible; a real deployment never has a dealer that sees a and b.

import secrets

P = 2**61 - 1  # a Mersenne prime; all arithmetic is mod P

def share(x, n=3):
    """Additive n-of-n sharing: n-1 random shares plus a correction."""
    s = [secrets.randbelow(P) for _ in range(n - 1)]
    s.append((x - sum(s)) % P)
    return s

def reveal(shares):
    return sum(shares) % P

def add(xs, ys):                 # local, no messages
    return [(a + b) % P for a, b in zip(xs, ys)]

def add_const(xs, k):            # only party 0 adds the public constant
    return [(xs[0] + k) % P] + xs[1:]

def mul_const(xs, k):            # local
    return [(a * k) % P for a in xs]

def dealer_triple(n=3):
    """Stand-in for the offline phase: random a, b and c = a*b, all shared."""
    a, b = secrets.randbelow(P), secrets.randbelow(P)
    return share(a, n), share(b, n), share(a * b % P, n)

def mul(xs, ys, triple):
    """Beaver multiplication: one round, each party broadcasts two values."""
    a, b, c = triple
    d = reveal([(x - ai) % P for x, ai in zip(xs, a)])   # d = x - a, safe to open
    e = reveal([(y - bi) % P for y, bi in zip(ys, b)])   # e = y - b, safe to open
    z = add(c, add(mul_const(b, d), mul_const(a, e)))    # c + d*b + e*a
    return add_const(z, d * e % P)                       # + d*e, once

With salaries 91,000, 78,500 and 105,250 shared this way, summing the share vectors and opening gives 274,750, and squaring each shared salary with a fresh triple then summing gives 25,520,812,500, the exact sum of squares. With those two numbers the parties get a mean and a variance and nothing else. A loop of 2,000 random products checked every result against x * y mod p.

Worked example over p = 97

Shrink p to 97 so every step fits in your head. The parties hold shares of x = 7 and y = 9 and a triple with a = 5, b = 11, c = 55. Each party subtracts its share of a from its share of x and broadcasts it. The broadcasts are 87, 87 and 22, which sum to 196 = 2 mod 97, so d = 2. Likewise for y - b: 39, 1 and 55 sum to 95, so e = 95, which is -2. Check the identity in plain integers: 55 + 2 x 11 + (-2) x 5 + 2 x (-2) = 55 + 22 - 10 - 4 = 63 = 7 x 9. The three output shares are 85, 82 and 90, which sum to 257 = 63 mod 97. No party saw 7, 9, 5 or 11. Each saw only its own shares and two numbers masked by randomness it does not know.

Where triples come from, and garbled circuits

The triples have to come from somewhere, and generating them is most of the cost. In the two-party and dishonest-majority settings they are produced with oblivious transfer (OT), a primitive where a sender offers two messages and a receiver gets exactly one without the sender learning which. OT can be built from public-key operations such as Diffie-Hellman, and OT extension then stretches a small number of base OTs into millions using only symmetric crypto. The alternative is somewhat homomorphic encryption, where parties multiply encrypted shares. In the honest-majority setting no triples are needed: with Shamir sharing, a product of two degree-t sharings is a degree-2t sharing, which honest parties re-share down to degree t.

A different family evaluates Boolean circuits. In Yao's garbled circuits, one party (the garbler) encrypts each gate's truth table under random wire labels. The other (the evaluator) fetches the labels for its own input bits by OT and decrypts its way through the circuit, learning one label per wire and nothing about what it means. Garbling is constant-round, which suits high-latency links, but its cost is per gate and proportional to circuit size. Modern optimisations make XOR gates free and AND gates cost two ciphertexts under the half-gates technique. GMW does the same job with XOR-shared bits and needs a round per AND layer. The practical consequence: comparisons and bit operations are cheap in Boolean circuits and expensive in arithmetic sharing; dot products are the opposite.

Operational guidance

• Start from the output, not the protocol. Write down exactly what each party may learn, then check what the output leaks under collusion. Add thresholds (only release an average over at least k records) or noise from differential privacy when the output alone is too revealing.
• Use a maintained framework. MP-SPDZ implements dozens of protocols behind one high-level language, EMP-toolkit covers garbled circuits, and CrypTen targets machine learning in PyTorch. Do not invent protocols.
• Pick the security model from the threat model. Semi-honest protocols are much cheaper and suit audited institutions bound by contract, not parties who can profit from cheating undetected.
• Budget latency in rounds. Count the multiplicative depth of f. On a 50 ms wide-area link, a depth-40 circuit costs at least two seconds of pure waiting regardless of bandwidth, while garbled circuits trade those rounds for bulk data.
• Encode reals as fixed point. Scale by 2^f and store integers mod p, leaving headroom so the largest intermediate does not wrap. Every multiplication doubles the scale, so it must be followed by a truncation protocol; truncation is where many numeric bugs hide.
• Run the offline phase ahead of demand. Generate triples in advance and alert before the stock runs out.

Failure modes

• Triple reuse. Using a triple twice reveals the difference of two secrets, as shown above. Make the triple store a consume-once queue with the index logged, never an array indexed by gate number that a restart can replay.
• Weak randomness. Shares drawn from a non-cryptographic generator, or from a seed shared across parties, are not uniform to an attacker. Use the operating system's CSPRNG, as secrets.randbelow does.
• Modulus overflow. A fixed-point sum that exceeds p wraps silently and opens to a plausible but wrong number. Bound every intermediate on paper before the first run.
• Leaking through control flow. Message sizes or timing that depend on data leak it. Evaluate both sides of every branch and select with a multiplexer.
• Malicious inputs. Even a maliciously secure protocol computes f on whatever the cheater feeds in. If a party can inflate the average by submitting absurd values, validate ranges inside the protocol or bind inputs to signed records, for example with zero-knowledge proofs.
• Collusion beyond the threshold. Additive n-of-n sharing tolerates n - 1 corruptions; Shamir-based honest-majority protocols tolerate fewer than half. Exceed the bound and privacy is gone completely, not partially.

Trade-offs

What to do next

1. Run the code above, then share a value among five parties and confirm that any four shares are uniformly distributed by sampling.
2. Add a mean-and-variance function for n parties and write down what two colluding parties learn from its output.
3. Break it deliberately: reuse one triple for two multiplications and recover x - x' from the broadcasts.
4. Install MP-SPDZ, implement the same statistics in its language, and compare a semi-honest protocol with a malicious one on your network.
5. Read elliptic curve cryptography to understand the public-key operations that base OTs rely on.
6. Before production, write the ideal functionality, corruption model and output leakage on one page and get it reviewed.