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

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?

share|improve this question
up vote 2 down vote accepted

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.

share|improve this answer
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? – William Seemann Apr 20 '13 at 23:48
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. – mikeazo Apr 21 '13 at 0:03

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.