When performing Shamir secret sharing I'm trying to find $z_i$, such that $z = x + y$. Where $n = 6$ and $t = 3$.

I believe this would be the correct solution (correct me if I'm wrong):

  1. Each party computes $x_i + y_i = z_i$
  2. Each party shares $z_i$ with the other 2 parties
  3. Each party uses Lagrange basis polynomials to compute the secret (using the 2 obtained values).

My question is this: if the shares are in the form $(i, f(i))$ (for $1$ to $i$) my assumption is that the involved parties can use Lagrange basis polynomials because they will know the "$i$" of the other parties that sent them their computed $z_i$. Is that correct?


You really only need to do step 1. If each party has shares of x and y (say $x_i,y_i$) then $z_i=x_i+y_i$ is a valid sharing of $z=x+y$.

What you are doing is used to multiply shares. Multiply, share the shares, reconstruct. In that case everything you said is correct. The reason this is needed in multiplication of shares and not addition can be seen by looking at the polynomials that were used for sharing. In the case of additions, the coefficients add pairwise, thus the individual coefficients of the resulting polynomial which shares $z$ has independent coefficients and has the same degree. In the case of multiplication, the degree goes from $t$ to $2t$ and the coefficients are not not pairwise independent.

  • $\begingroup$ Thanks for the answer! So, just to clarify, you are saying my steps are valid for a multiplication scenario like: z = xy, not an addition one, z = x + y, correct? $\endgroup$ – William Seemann Apr 20 '13 at 23:48
  • $\begingroup$ Yes that is correct for multiplication. For addition you only need step 1. The multiplication protocol is secure in the honest-but-curious adversary model. If that doesn't make sense or doesn't matter to you, ignore. $\endgroup$ – mikeazo Apr 21 '13 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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