Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
Did you look at this one. – DrLecter Jan 23 '14 at 17:45
I hadn't. Thank you! – user3225551 Jan 24 '14 at 2:43
up vote 7 down vote accepted

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.

share|improve this answer
I followed until the last line. Where does 3,7,0 come from? Thank you! – user3225551 Jan 24 '14 at 2:44
Party 1 interpolates the subshares it holds and gets 3, party 2 does the same and gets 7, etc. – mikeazo Jan 24 '14 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.) – user3225551 Jan 24 '14 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. – mikeazo Jan 24 '14 at 13:23

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".

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.