Computing with Secret Shares - Introducing Beaver Triples

You and your friends are planning to go out to dinner. Typically, you are the friend in the friend group that pays for everyone else's meals. But recently, the market isn't doing to well recently. So, everyone needs to start paying up.

However, not all of the homies are ballin' because well, the market isn't doing too well and one of them is still a student. But, just because external forces are kicking everyone's butt doesn't prevent the friend group from hanging out and enjoying a nice meal together. In order to have an enjoyable meal together, a restaurant needs to be decided upon. But, not everyone likes the same cuisine and some restaurants are more expensive than others. Considering that everyone's financial situation and food preferences are different, you attempt to devise a privacy-respecting way to allow the group to come to consensus on which restaurant to go to.

As you are a cryptographer, you know that you can leverage secret sharing to solve this problem. You figure out a simple scoring rule to determine which restaurant everyone will go to: For a restaurant j, person i will submit

aᵢⱼ = how much can I afford to eat at this restaurant

fᵢⱼ = how much do I want to eat at this restaurant

Each aᵢⱼ and fᵢⱼ are graded on a 0-10 scale. The friend level score will be sᵢⱼ = aᵢⱼ * fᵢⱼ. The group level score for a restaurant j will be Sⱼ = Σsᵢⱼ.

At the end, at least 2 friends will unveil the scores for the restaurant and then decide which restaurant the dinner will happen at.

We want to keep each person's aᵢⱼ and fᵢⱼ scores private in order to keep the peace among everyone in the group chat.

There are 4 friends in the friend group and you all are trying to decide among 3 restaurants to have the dinner at. You need at least 2 of them together to unveil the group level restaurant scores.

To make this concrete, let's say the 4 friends are Alice, Ben, Chloe, and Stoffel. The group is deciding between 3 restaurants: Restaurant A, Restaurant B, and Restaurant C.

Each friend submits a pair (a,f), where a is affordability and f is food preference.

The private inputs are:

Restaurant A: Alice (8,5), Ben (7,6), Chloe (9,4), Stoffel (6,5).

Restaurant B: Alice (6,9), Ben (8,8), Chloe (7,7), Stoffel (5,9).

Restaurant C: Alice (9,3), Ben (4,7), Chloe (6,6), Stoffel (8,4).

The goal is not to reveal these numbers to everyone in the group chat. The goal is to use them to privately compute the restaurant scores and only reveal the final group level scores at the end.

Using secret sharing notation, every private input gets turned into shares. So instead of Alice revealing her affordability score for Restaurant A, the group gets a share of that value. In notation, this is one instance of [aᵢⱼ].

Instead of Alice revealing her food preference score for Restaurant A, the group gets a share of that value. In notation, this is one instance of [fᵢⱼ].

The same thing happens for every friend and every restaurant. More generally, every private affordability score becomes [aᵢⱼ] and every private food preference score becomes [fᵢⱼ].

What we want is to compute shares of the friend level scores [sᵢⱼ] = [aᵢⱼfᵢⱼ], and then shares of the group level restaurant scores [Sⱼ] = Σ[sᵢⱼ].

At the end, the group opens the final restaurant scores for Restaurant A, Restaurant B, and Restaurant C, but not the individual affordability or food preference scores.

But you realize that there is one issue.

How can you actually compute [aᵢⱼ] [fᵢⱼ]?

We know that for each restaurant j and friend i, that we get the following shares:

pᵢⱼ(x) = aᵢⱼ + px, qᵢⱼ(x) = fᵢⱼ + qx

where pᵢⱼ(0) = aᵢⱼ and qᵢⱼ(0) = fᵢⱼ.

If we were to directly compute pᵢⱼ(x)qᵢⱼ(x), we get pqx² + (fᵢⱼp + aᵢⱼq)x + aᵢⱼfᵢⱼ where pᵢⱼqᵢⱼ(0) = aᵢⱼfᵢⱼ. So, this would indeed give us the right per restaurant per friend score privately.

The issue is that now, before we required at least 2 friends to unveil the final scores. But now, we require at least 3 friends to unveil the final scores; which is nearly everyone in the group chat.

Is there a way to still get a polynomial of degree t where the intercept of this polynomial is still aᵢⱼfᵢⱼ?

Well, it turns out, the answer is yes.

Computing with secret shares

Remember from the secret sharing article that secret sharing itself is a linear function with the following properties:

For secret shares [x] and [y], we have

For a known number a, we have

Additionally, we have the open operation which is reconstruction of the secret using Lagrange Interpolation:

How can we go about computing [x][y] without increasing the threshold needed for reconstruction?

For arbitrary x and y, let's consider the following plot:

Notice that the distance between 0 and x on the x-axis is x and similarly, the distance between 0 and y on the y-axis is y. We can draw a rectangle and get a rectangle with dimensions x x y with areas xy.

Is there a way to leverage this geometric interpretation of xy to come up with a way to compute [x][y] ?

In the plot, let's look closer at the interior of the rectangle. For an arbitrary point (a,b), we can similarly form another rectangle of area ab.

Notice that to we can write x and y in terms of a and b like so x = a + (x-a), y = b + (y-b).

Then we can recompute the area of xy in terms of a and b. We get

Each term forms a smaller rectangle within the larger xy rectangle.
Now, let d = x-a, e = y-b and c = ab. Then

We now have a relation that we can use towards enabling multiplication of shared secrets without increasing the degree of the underlying polynomial!

But hold on.

We are almost there but not quite.

If we have shares [x][y] then we'd like to reuse our rectangle identity to compute [xy] = [c] + [bd] + [ae] + [de], where d, e, and c are defined as above. But how do we handle d and e if they are also secret shared? The key is actually to reveal d and e and use them as publicly known numbers.

But doesn't that reveal x and y?
No, because as we will show, a and b act as randomly generated masks for x and y. Thus, revealing d and e reveals nothing about x and y.

First, suppose that a is not randomly generated. Then a is the result of some known process and can be discerned by an external observer. Which means that using the known relation d=x-a, an external observer can infer information about x. If an external observer can calculate a directly, then they can get x directly via x = d + a. So, opening d reveals information about x. Thus, a needs to be randomly generated. A similar argument follows for b.

Second, suppose that [a] and [b] are being reused across two different multiplications, (x, y) and (x', y'). Then, we have that d = x-a, d' = x'-a, e = y-b, e' = y'-b. Then, we can see that d'-d = x'-x and e'-e = y'-y, revealing relationships between secret values x, x', y, y'. These relationships contradict the fact that opening d, d', e, and e' shouldn't reveal anything meaningful about x, x', y, and y'. Thus, [a], [b] and [c] need to be used exactly once.

For example, if anyone in the group chat can discern that Ben has scored a restaurant 5 points higher than Chloe, then they know that have enough information to infer what Ben's private scores were. Maybe he likes the restaurant more. Maybe he can afford it more. Who knows? Well, no one should. We don't want anyone in the group chat to be able to determine such information.

We now have shown that a and b need to be randomly generated and used exactly once in order to be masks of x and y. Which means that d and e can be safely revealed without giving an external observer information about x and y.

To bring it all together, we can now compute

since d and e can be safely revealed.

The triples [a], [b], [c], where c=ab are what are known as Beaver Triples named after the original author, Don Beaver.

How do we use them though?

You know that there's a service that gives you beaver triples generated using entropy from satellites. Using this service, everyone in the group chat gets their shares of the same beaver triples [a], [b], [c].

Wait? Everyone gets the same beaver triples?

Yes and no. Everyone gets shares of the same underlying beaver triples. They do not get the raw values a, b, and c.

Alice gets one share of a, one share of b, and one share of c. Ben, Chloe, and Stoffel get their own shares too. Together, their shares represent the same underlying beaver triple [a], [b], [c]. But no individual person knows the raw a, b, and c values.

Since there are 4 friends and 3 restaurants, we need 12 friend level scores. Each friend level score requires one multiplication. So, the group needs 12 fresh beaver triples. Each triple is used exactly once.

Now, let's walk through one score. Take Ben's score for Restaurant B. Ben submits a=8 and f=8. Here, a is affordability and f is food preference. So Ben's friend level score for Restaurant B should be 8 * 8 = 64.

But Ben does not reveal either of these values directly. The group chat does not need to know how much Ben can afford Restaurant B. The group chat also does not need to know how badly Ben wants to eat at Restaurant B.

So, Ben secret shares both values. The group has [8] and [8], and now needs to compute [8 * 8].

For this multiplication, suppose the beaver triple has the underlying values a=5, b=6, and c=ab=30. The notation is a little overloaded here. This a is the beaver triple mask. It is not Ben's affordability score.

Again, nobody sees the raw values 5, 6, and 30. Everyone only has shares [5], [6], and [30].

The group computes [d] = [8] - [5] and [e] = [8] - [6]. Then the group opens d=3 and e=2. This is safe because 5 and 6 are random masks that remain hidden.

Now everyone can compute [xy] = [c] + d[b] + e[a] + de.

Substituting in the numbers, [64] = [30] + 3[6] + 2[5] + 3 * 2 = [30] + [18] + [10] + 6 = [64].

So the group now has shares of Ben's score for Restaurant B: [64], without Ben revealing his affordability score or his food preference score.

This same process happens for every friend and every restaurant. Inside the protocol, the individual friend level scores are not public values. The group only has shares [sᵢⱼ] for every friend i and restaurant j.

Now, because secret sharing is linear, the group can compute the restaurant level scores by adding shares.

For Restaurant A, the group computes [40] + [42] + [36] + [30] = [148].

For Restaurant B, the group computes [54] + [64] + [49] + [45] = [212].

For Restaurant C, the group computes [27] + [28] + [36] + [32] = [123].

At this point, the group has shares of the final restaurant scores.

No one has learned everyone else's affordability scores. No one has learned everyone else's food preference scores. No one even needs to learn the individual friend level scores.

All that needs to be opened are the final restaurant scores. Since this is a 2-of-4 secret sharing scheme, at least 2 friends need to open the scores.

Suppose Alice and Chloe are designated to open the final scores. They reveal their shares of the final restaurant scores. Using Lagrange interpolation, the group reconstructs Restaurant A's score as 148, Restaurant B's score as 212, and Restaurant C's score as 123.

Now the group compares the scores: 212 > 148 > 123. So the restaurant with the highest score is Restaurant B.

The dinner has been decided. Nobody had to reveal how much they could afford. Nobody had to reveal how badly they wanted a particular restaurant. The group chat remains peaceful. And a restaurant for the group dinner has been chosen.

To Recap

• Ahead of time, everyone gets precomputed secret shared triples, [a], [b], [c], where c=ab

• Everyone secret shares their preference and affordability scores into 4

• Everyone passes their shares to each other

• Upon your signal, everyone goes through the algorithm and uses the triples [a], [b], [c] to compute the multiplications involved using the identity xy = c + bd + ae + de

• Once completed, 2 members of the group open the group-level restaurant scores using lagrange interpolation and reveal the results to the group

• A restaurant for the group dinner has been chosen!