Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
Did you look at this one. –  DrLecter Jan 23 at 17:45
    
I hadn't. Thank you! –  user3225551 Jan 24 at 2:43
add comment

1 Answer 1

up vote 5 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 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 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 at 4:07
1  
@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 at 13:23
add comment

Your Answer

 
discard

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.