Beaver Triples

A Beaver Triple is a set of three secret-shared values (a, b, c) where a and b are randomly generated, and c is defined such that c = a * b under a finite field. In secure multi-party computation (MPC), these pre-generated triples are used as a one-time pad to facilitate the secure multiplication of private inputs without revealing the underlying values to any single party. The core innovation is that the multiplication of two secret values, x and y, can be performed by consuming a pre-computed triple, using a protocol that reveals only masked, random data, thus preserving the secrecy of x and y.

The protocol for using a Beaver Triple, often called Beaver's Multiplication Trick, involves each party holding additive secret shares of the inputs x and y, as well as shares of the triple (a, b, c). The parties first compute and publicly reveal masked values e = x - a and d = y - b. Because a and b are random, e and d reveal nothing about x or y. Using these public values and the linearity of secret sharing, the parties can locally compute shares of the product x * y as c + e*b + d*a + e*d. This process allows a complex, non-linear operation (multiplication) to be performed using only local linear operations and the revelation of random data.

Beaver Triples are pre-computed in an offline phase, which is often computationally expensive, and then consumed in an online phase where actual private data is processed. This separation is critical for performance, as the offline generation can use heavier cryptographic machinery like Oblivious Transfer (OT) or homomorphic encryption, while the online phase is extremely fast. Their generation must be secure against passive (semi-honest) or active (malicious) adversaries, depending on the MPC model, ensuring the triples are correctly formed and unknown to any party.

The primary application of Beaver Triples is in MPC protocols such as SPDZ and BGW, where they enable complex functions like private machine learning, secure auctions, and privacy-preserving data analytics. They are a key component in making general-purpose MPC feasible by efficiently handling the non-linear gates in arithmetic circuits. Their use extends to zero-knowledge proof systems and threshold cryptography, where secure multi-party multiplication is a required subroutine.

While powerful, Beaver Triples have limitations. They introduce a circuit-dependent communication round for each multiplication gate and require secure storage and distribution of the pre-computed triples. Advances in homomorphic secret sharing and specialized protocols aim to reduce these overheads. Nonetheless, they remain a cornerstone of practical MPC, providing a clear and elegant method for transforming secure additions into secure multiplications.

The term Beaver Triples originates from a seminal 1990 paper by cryptographer Donald Beaver titled "Efficient Multiparty Protocols Using Circuit Randomization." In this work, Beaver introduced a method to precompute random multiplicative triples—values (a, b, c) where c = a * b—to dramatically speed up secure multi-party computation (MPC) protocols. The name is a straightforward eponym, derived from the author's surname, following a common convention in computer science for naming algorithms and constructs after their inventors (e.g., Diffie-Hellman, Merkle tree).

Conceptually, Beaver's innovation addressed a critical bottleneck in MPC. Performing multiplication on secret-shared data is computationally expensive and requires communication between parties. Beaver's key insight was that if parties could precompute random, correlated triples of secret-shared values offline, they could later consume these triples during the online phase to efficiently perform a multiplication with minimal interaction. This separation of a costly offline preprocessing phase from a fast online phase became a cornerstone of practical MPC, making complex computations feasible.

The protocol's foundation relies on homomorphic encryption or oblivious transfer to generate these triples securely without any party learning the individual values of a, b, or c. The triples themselves are a form of correlated randomness, a resource that enables efficient cryptographic protocols. Over time, the generation of Beaver Triples has been optimized and adapted for various settings, including malicious security models and dishonest majorities, but the core concept and nomenclature have remained consistent, cementing "Beaver Triples" as a fundamental primitive in the MPC lexicon.

A Beaver triple is a set of three secret-shared values—(a, b, c)—where a and b are random values, and c is their product (a * b). These triples are generated in a preprocessing phase by a trusted dealer or via a secure distributed protocol, and are then distributed as shares among the participating parties. The core utility of a Beaver triple is that it allows parties to convert a multiplication of two secret-shared values into a series of local additions and a single opening of a masked value, which reveals no information about the original secrets.

The protocol works by using the triple as a one-time pad for multiplication. Suppose two parties hold secret shares of values x and y. They first publicly reveal the masked differences ε = x - a and δ = y - b. Since a and b are random, ε and δ reveal nothing about x or y. The parties can then locally compute shares of the product x * y using the linear relationship: x*y = (a + ε)*(b + δ) = c + ε*b + δ*a + ε*δ. Because a, b, and c are pre-shared, and ε and δ are now public, each term can be computed locally or with simple linear operations on the existing shares.

This technique is crucial because multiplication is non-linear in most secret-sharing schemes, unlike addition which is straightforward. Beaver triples effectively "outsource" the complexity of secure multiplication to a pre-computed, correlated randomness. Their security relies on the fact that the masks a and b are uniformly random and unknown to any individual party, ensuring the opened values ε and δ are perfectly hiding. This makes them a cornerstone for more complex MPC circuits, enabling private evaluation of functions like those used in private machine learning and secure auctions.

A Beaver triple is a set of three secret-shared random numbers, (a, b, c), where c = a * b under a finite field, that are generated offline and later used to facilitate secure multiplication in Multi-Party Computation (MPC) protocols. These triples act as a one-time cryptographic "pad" that allows parties holding secret shares of two values, [x] and [y], to compute a share of their product [x * y] without revealing the individual values x or y. The security relies on the fact that the random values a and b mask the actual inputs during the online computation phase.

The protocol's power comes from its division into two phases. In the offline (preprocessing) phase, a trusted dealer or a secure distributed protocol generates many Beaver triples and distributes secret shares of (a, b, c) to each participant. This is the computationally expensive step but can be done ahead of time, independent of the actual inputs. In the subsequent online phase, when parties want to multiply their private inputs x and y, they use the pre-shared triple to perform a local masking, exchange of corrected shares, and a linear recombination, resulting in shares of x * y. The original inputs remain hidden because they are only ever manipulated while blinded by the random a and b.

Beaver triples are crucial for building efficient MPC circuits for complex functions like privacy-preserving machine learning, secure auctions, and genomic analysis. Their use transforms non-linear operations (multiplication) into linear ones, which are vastly more efficient to compute securely. While the classic formulation is for three parties, variations exist for two-party computation using Oblivious Transfer (OT) and for threshold settings with more parties. The generation of the triples themselves is a major research area, employing techniques like homomorphic encryption or specialized OT extensions to remove the need for a trusted dealer.