# Secure degree reduction for Shamir's secret sharing

I understand the basic Shamir Secret Sharing protocol, and when two shares are multiplied, the degree of the polynomial increases. I've seen in a number of papers a reference to a degree reduction protocol that can be performed to securely reduce the degree back to the original $t$. Yet I cannot find this construction anywhere. Could someone explain to me how the degree reduction is done and/or point me to a paper which describes the details?

• Did you look at this one. Jan 23, 2014 at 17:45

The process is pretty simple. As you say, each party multiplies their two shares. They then use Shamir secret sharing to share the resulting value with the other parties. Once they have received a "subshare" from each other party, each party simply runs Lagrangian interpolation on the subshares they received (plus their own subshare). The result is a share of the product of the two inputs with the proper degree for the sharing polynomial.

I'll illustrate it with a simple example. Say we have shared two secrets ($5$ and $2$) with three parties as follows. Math done in $\mathbb{Z}_{11}$.

$\sigma_1(x) = 5 + 8x$
$\sigma_2(x) = 2 + 9x$

So the shares of 5 that the parties hold are 2, 10, 7.
The shares of 2 are 0, 9, 7.

So, each party multiplies their shares. The new shares are 0, 2, 5.

They each share these using new polynomials

$\sigma_3(x) = 0 + 3x$ for party 1
$\sigma_4(x) = 2 + 6x$ for party 2
$\sigma_5(x) = 5 + 2x$ for party 3

Which generate subshares: (3, 6, 9); (8, 3, 9); (7, 9, 0)

Thus, after distributing the shares, party 1 holds (3,8,7); party 2 holds (6,3,9); and party 3 holds (9,9,0).

After interpolation, the shares held by the parties are 3, 7, 0. Interpolating these to get the constant term give us 10 as expected.

• I followed until the last line. Where does 3,7,0 come from? Thank you! Jan 24, 2014 at 2:44
• Party 1 interpolates the subshares it holds and gets 3, party 2 does the same and gets 7, etc. Jan 24, 2014 at 3:22
• Thank you very much! What is the source for this protocol?( I was looking at the one in the paper that was referenced in the comments on this question, and it seems much more complicated.) Jan 24, 2014 at 4:07
• @user3225551 it should be in the referenced paper. That paper gives 2 MPC protocols. One in the honest-but-curious (semi-honest) model. That is the one that works as I described. The other is in the malicious model which is much more complicated. Their explanation of the multiplication step is just presented in a different manner. See also this. Jan 24, 2014 at 13:23
• Thanks. Doing everything in Z11 and making the math simple is a gem for explaining the process. I'm asking all my team members who might not be up to speed on this to read it. Nov 7, 2019 at 15:39

This degree-reduction construction has a chance to be re-invented, still a reference would be "Simplified VSS and fast-track multiparty computations with applications to threshold cryptography".