Understanding Beaver Triples: Enabling Private Multiplication in Secret Sharing

In the realm of secure multi-party computation (MPC), secret sharing allows multiple parties to jointly compute a function over their inputs while keeping those inputs private. While adding secret-shared values is straightforward due to the linearity of secret sharing, multiplication presents a significant technical hurdle. If you simply multiply two shared secrets, you inadvertently increase the degree of the underlying polynomial, which in turn increases the number of participants required to reconstruct the secret.

This is where Beaver Triples come into play. Named after Don Beaver, these precomputed triples allow parties to perform multiplications on secret shares without increasing the reconstruction threshold and without revealing the original secrets. This article explores the mechanics of Beaver Triples through a practical example of a privacy-preserving group decision process.

The Problem: The Multiplication Bottleneck

Imagine a group of four friends trying to choose a restaurant. To maintain privacy regarding their budgets and preferences, they use a secret sharing scheme where each person's input (affordability $a$ and preference $f$) is split into shares. The goal is to compute a "friend level score" $s = a \times f$ and then sum these scores to find the group's favorite restaurant.

If the group uses a basic secret sharing scheme (like Shamir's), the shares are represented as points on a polynomial. For a 2-of-4 scheme, the polynomial is of degree 1 (a line). When you multiply two such polynomials, the resulting polynomial is of degree 2 (a parabola).

This creates a critical issue: while the original secrets only required 2 people to reconstruct, the product now requires 3 people. As the complexity of the computation grows, the number of participants needed to reveal the result increases, eventually requiring nearly everyone in the group to cooperate, which defeats the purpose of a flexible threshold scheme.

The Geometric Intuition of Beaver Triples

To solve this without increasing the polynomial degree, we can use a geometric identity. Consider the product of two values, $x$ and $y$. We can represent this as the area of a rectangle. If we pick a random point $(a, b)$ inside that rectangle, we can express $x$ and $y$ as:

$x = a + d$
$y = b + e$

Where $d = x - a$ and $e = y - b$. The total area $xy$ can then be decomposed into four smaller rectangles:

$$xy = ab + (x-a)b + a(y-b) + (x-a)(y-b)$$

Substituting our variables $d$ and $e$:

$$xy = c + db + ae + de$$

In this case, $c = ab$. This identity is the foundation of the Beaver Triple. The values $a, b,$ and $c$ are the "triple."

How Beaver Triples Work in Practice

For the identity to maintain privacy, the triple $(a, b, c)$ must be generated randomly and used exactly once. If $a$ and $b$ were known or reused, an observer could subtract them from the revealed values $d$ and $e$ to uncover the original secrets $x$ and $y$.

The Workflow

1. Precomputation Phase: A trusted third party (or a distributed protocol) generates Beaver Triples $[a], [b], [c]$ where $c = ab$. Each participant receives a share of $a, b,$ and $c$, but no one knows the actual values.
2. Masking Phase: To multiply secret shares $[x]$ and $[y]$, the participants compute shares of the differences:
   • $[d] = [x] - [a]$
   • $[e] = [y] - [b]$
3. Opening Phase: The participants "open" (reconstruct) the values of $d$ and $e$. Because $a$ and $b$ are random masks, $d$ and $e$ reveal nothing about the original $x$ and $y$.
4. Computation Phase: Now that $d$ and $e$ are public constants, the participants can compute the shares of the product using the identity: $$[xy] = [c] + e[a] + d[b] + de$$

Because this formula only involves adding shares and multiplying shares by public constants (both linear operations), the degree of the polynomial does not increase. The reconstruction threshold remains exactly the same as it was for the original inputs.

A Concrete Example

Let's apply this to Ben, who has an affordability score of 8 and a preference score of 8 for a specific restaurant. The group wants to compute $[8 \times 8]$.

• The Triple: Suppose the precomputed triple is $a=5, b=6, c=30$. (Again, these are shared, not known to individuals).
• Masking: The group computes $[d] = [8] - [5]$ and $[e] = [8] - [6]$.
• Opening: The group opens $d=3$ and $e=2$.
• Final Calculation: $$[64] = [30] + 2[5] + 3[6] + (3 \times 2)$ $$[64] = [30] + [10] + [18] + 6 = [64]$$

Summary of the Protocol

By leveraging Beaver Triples, the group can compute the final restaurant scores by summing the individual friend-level scores. Only the final result is ever reconstructed using Lagrange interpolation, ensuring that no individual's budget or preference is ever leaked.

This mechanism transforms the complex problem of non-linear multiplication in secret sharing into a series of linear operations and public reconstructions of masked values, providing a robust foundation for secure multi-party computation.