Beaver Triples

A Beaver triple is a set of three secret-shared values ([a], [b], [c]) where c = a * b and a and b are uniformly random and unknown to any party. These triples are generated in a data-independent preprocessing phase, completely decoupled from the actual computation inputs. This separation is the key to performance: the heavy cryptographic lifting is done offline before the real data arrives.

To multiply two secretly shared values [x] and [y], parties consume one precomputed triple ([a], [b], [c]):

• Each party locally computes and broadcasts [x] - [a] and [y] - [b].
• The differences ε = x - a and δ = y - b are reconstructed openly.
• The product is computed locally as [x*y] = [c] + ε[b] + δ[a] + εδ. This reduces a complex interactive protocol to one round of communication and simple local arithmetic.

Generating valid triples without revealing a, b, or c to any party is the core challenge. Common generation techniques include:

• Homomorphic Encryption: One party encrypts a and b, and another computes c under encryption using additive homomorphism.
• Oblivious Transfer (OT): Using OT extension to generate many triples efficiently from a small base of public-key operations.
• Trusted Dealer: A third party generates and distributes triples, suitable for the honest-majority setting. The choice of method directly impacts the protocol's security model and throughput.

Each multiplication gate in an arithmetic circuit consumes exactly one Beaver triple. The total number of triples required equals the number of multiplication operations in the computation. Addition and subtraction gates are free, requiring no triples and no communication. This makes the multiplicative depth of a circuit the primary metric for estimating both the preprocessing storage requirements and the online round complexity of an MPC protocol.

In protocols secure against malicious adversaries (like SPDZ), triples are not just secret-shared but also authenticated using information-theoretic message authentication codes (MACs). Each share comes with a MAC share, allowing parties to verify that an opened value (like ε) was not tampered with. The preprocessing phase must generate these authenticated triples, which are then consumed in the online phase to guarantee correctness with abort.

Beaver triples represent a classic storage-for-speed trade-off:

• A single triple for 64-bit values is roughly 384 bytes of storage.
• A circuit with 1 million multiplication gates requires ~366 MB of precomputed triples.
• Modern OT-based generation can produce millions of triples per second on commodity hardware. This makes the approach viable for deep neural network inference, where matrix multiplications dominate the computational graph.