Beaver Triples

A Beaver triple is a tuple ([a], [b], [c]) of secret-shared random values where c = a · b, generated in an offline phase before the actual computation. Don Beaver introduced them in 1991 to fix a longstanding annoyance in secret-sharing-based secure-multiparty-computation: multiplying two shared values naïvely doubles the polynomial degree, raising the reconstruction threshold.

The trick is the rectangle identity. Given shares [x], [y] and a fresh triple ([a], [b], [c=ab]):

1. Compute [d] = [x] - [a] and [e] = [y] - [b] — local, no communication.
2. Open d and e (one round of broadcast). Safe because a, b are uniform random masks.
3. Compute [xy] = [c] + d·[b] + e·[a] + d·e — local, no degree increase.

Two correctness conditions:

• The triple must be fresh (used exactly once). Reuse leaks linear relations among secret inputs.
• a, b must be uniformly random. Bias makes opening d = x - a leak information about x.

In practice the offline triple-generation phase is the expensive part. Common approaches:

• OT-based (TinyOT, MASCOT): generate triples from oblivious transfer; constant rounds, high bandwidth
• HE-based (SPDZ): use Paillier or BFV/BGV homomorphic encryption to generate triples; lower bandwidth, more compute
• TTP-based (training/setup phase, or hardware enclaves): trusted dealer generates triples; cheapest but requires the trust assumption MPC is meant to remove

Beaver triples generalize: there are matrix triples (for linear algebra), Boolean AND triples (for garbled-circuit-style evaluation), and squared triples ((a, a²) for division-like operations).

For a worked example, see mpc-beaver-triples (Stoffel's restaurant scenario).