Originally published by Hacker News
Computing with Secret Shares - Introducing Beaver Triples
Mikerah Quintyne-Collins
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 leveragesecret sharingto solve this problem. You figure out a simple scoring rule to determine which restaurant everyone will go to: For a restaurantj, personiwill submit
aᵢⱼ= how much can I afford to eat at this restaurant
fᵢⱼ= how much do I want to eat at this restaurant
Eachaᵢⱼ and fᵢⱼare graded on a 0-10 scale.The friend level score will besᵢⱼ= aᵢⱼ* fᵢⱼ.The group level score for a restaurantjwill beSⱼ=Σ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’saᵢⱼandfᵢⱼ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 restaurantjand friendi, that we get the following shares:
pᵢⱼ(x) = aᵢⱼ+ px, qᵢⱼ(x) = fᵢⱼ+ qx
wherepᵢⱼ(0) = aᵢⱼandqᵢⱼ(0) = fᵢⱼ.
If we were to directly computepᵢⱼ(x)qᵢⱼ(x), we getpqx² + (fᵢⱼp + aᵢⱼq)x + aᵢⱼfᵢⱼwherepᵢⱼ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 degreetwhere 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 arbitraryxandy, let’s consider the following plot:
Notice that the distance between 0 andxon the x-axis is x and similarly, the distance between 0 and y on the y-axis isy. We can draw a rectangle and get a rectangle with dimensionsxxywith areasxy.
Is there a way to leverage this geometric interpretation ofxyto 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 areaab.
Notice that to we can writexandyin terms of a and b like sox = a + (x-a), y = b + (y-b).
Then we can recompute the area ofxyin terms ofaandb. We get
Each term forms a smaller rectangle within the largerxyrectangle.Now, letd = 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!
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], whered, e, and care defined as above. But how do we handledandeif they are also secret shared? The key is actually to revealdandeand use them as publicly known numbers.
But doesn’t that revealxandy?No, because as we will show,aandbact as randomly generated masks forxandy. Thus, revealingdandereveals nothing aboutxandy.
First, suppose thatais not randomly generated. Thenais the result of some known process and can be discerned by an external observer. Which means that using the known relationd=x-a, an external observer can infer information aboutx. If an external observer can calculateadirectly, then they can getxdirectly viax = d + a. So, openingdreveals information aboutx. Thus,aneeds to be randomly generated. A similar argument follows forb.
Second, suppose that[a]and[b]are being reused across two different multiplications,(x, y)and(x’, y’). Then, we have thatd = x-a, d’ = x’-a, e = y-b, e’ = y’-b. Then, we can see thatd’-d = x’-xande’-e = y’-y, revealing relationships between secret valuesx, x’, y, y’. These relationships contradict the fact that openingd, d’, e, and e’shouldn’t reveal anything meaningful aboutx, 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 thataandbneed to be randomly generated and used exactly once in order to be masks ofxandy. Which means thatdandecan be safely revealed without giving an external observer information aboutxandy.
To bring it all together, we can now compute
sincedandecan be safely revealed.
The triples[a], [b], [c], where c=abare what are known asBeaver Triplesnamed 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 ofa, one share ofb, and one share ofc. 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 rawa, b, and cvalues.
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 submitsa=8 andf=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 valuesa=5,b=6, andc=ab=30. The notation is a little overloaded here. Thisais 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.
- Ahead of time, everyone gets precomputed secret shared triples,[a], [b], [c],wherec=ab
Ahead of time, everyone gets precomputed secret shared triples,[a], [b], [c],wherec=ab
- Everyone secret shares their preference and affordability scores into 4
Everyone secret shares their preference and affordability scores into 4
- Everyone passes their shares to each other
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 identityxy = c + bd + ae + de
Upon your signal, everyone goes through the algorithm and uses the triples[a], [b], [c]to compute the multiplications involved using the identityxy = 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
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!
A restaurant for the group dinner has been chosen!
Compute sensitive data without liability
The raw data stays where it belongs. The computation happens privately. The liability stays off your books.
Compute sensitive data without liability
The raw data stays where it belongs. The computation happens privately. The liability stays off your books.
Compute sensitive data without liability
The raw data stays where it belongs. The computation happens privately. The liability stays off your books.
Federated Learning Aggregator
© 2025 Stoffel Labs Inc. All rights reserved.
Federated Learning Aggregator
© 2025 Stoffel Labs Inc. All rights reserved.
Federated Learning Aggregator
© 2025 Stoffel Labs Inc. All rights reserved.
As an Amazon Associate, we earn from qualifying purchases at no extra cost to you.