4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\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
  • $\begingroup$ @mikeazo quick question for clarification. z_i would be the output of a polynomial with a constant term that is double that of x_i and y_i no? If this is the case then isn't (x_i + y_i)/2 a valid sharing of z_i and not just the sum? I realize this might be nit picking and you might have just been ignoring constants, but I was just curious. $\endgroup$ – z.karl Nov 14 at 23:11
  • $\begingroup$ @z.karl, all math is done in the underlying field, so I think that the answer is no. $\endgroup$ – mikeazo Nov 14 at 23:33
  • $\begingroup$ @mikeazo Hmm I might have explained my question incorrectly. The secret for any given share is the constant term of the polynomial to which the share is associated, correct? If so, x_i = a_n * x^n + ... (Secret) and y_i = a_n * y^n + ... (Secret) and the sum of x_i and y_i will yield a_n * (x^n + y^n) + ... + 2 * (Secret), no? So in order for z_i = x_i + y_i to be a valid share we must divide z_i by 2 in order to force the (Secret) to which it corresponds to be the same as the one for x_i and y_i, yes? Please feel free to correct me if I have erred:) $\endgroup$ – z.karl Nov 16 at 1:48

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.