Beaver Triples for Secure Multiplication

Stoffel Labs (an MPC-as-a-service company) wrote a friendly walkthrough of beaver-triples using a four-friends-pick-a-restaurant story. The framing matters because the protocol is exactly the kind of thing that looks abstract until somebody draws the rectangle.

The setup: four people each rate three restaurants on affordability a and food preference f, both 0–10. The group wants per-restaurant scores S_j = Σ a_ij · f_ij without anyone learning the individual a_ij and f_ij. They use secret-sharing with a 2-of-4 reconstruction threshold.

Addition of secret shares is free — secret sharing is linear, so [x] + [y] = [x+y] with no interaction and no degree increase. Multiplication is the hard part: naïvely computing [x][y] doubles the polynomial degree, which means the reconstruction threshold rises from 2 to 3. That breaks the protocol's assumption that two people can open the result.

The fix is a precomputed triple ([a], [b], [c]) where c = ab and a, b are random masks. Beaver's identity rewrites the rectangle of area xy using (x-a) and (y-b):

xy = c + (x-a)·b + a·(y-b) + (x-a)·(y-b)
   = c + d·b + a·e + d·e          where d = x-a, e = y-b

Crucially d and e can be safely opened because a and b are uniformly random one-time masks. With d and e public, the right-hand side is computable from shares alone — no degree increase. The cost is one fresh triple per multiplication, plus one round of communication to open d and e.

The two correctness/security caveats Stoffel emphasizes:

• a and b must be uniformly random; if either has any bias, opening d=x-a leaks information about x.
• Each triple must be used exactly once. Reusing [a],[b] across two multiplications (x,y) and (x',y') reveals d'-d = x'-x and e'-e = y'-y, which leaks linear relationships among the secret inputs.

Beaver triples are typically generated in an offline phase (sometimes by a TTP, sometimes via OT/HE-based protocols) and consumed in the online phase. The pattern is the foundation of every modern semi-honest MPC stack — SPDZ, MASCOT, TinyOT — and the reason Stoffel can sell "MPC as a service" without rebuilding the cryptography per use case.

Cross-references: secret-sharing, secure-multiparty-computation, beaver-triples, stoffel-mpc.