Does evaluating the products of shares $a_jb_j$ give a secret sharing of $ab$? I think it's a no, but I am not sure on how to prove it.

  • $\begingroup$ What secret sharing technique are you using? Shamir? $\endgroup$ – mikeazo Nov 2 '13 at 14:35
  • $\begingroup$ Can be any one @mikeazo $\endgroup$ – meta_warrior Nov 2 '13 at 14:39

The primary secret sharing methods in use for multiparty computation today are Shamir's and additive. I'm going to assume that you understand both.

No. When you go to reconstruct, you would have (simplified for 2 parties) $a_1b_1+a_2b_2\neq(a_1+a_2)(b_1+b_2)$. To prove it in the general case you would have to extend that analysis to $n$ parties.

Yes and no. In Shamir's we say that $a_i=p(i)$ for some polynomial $p$ and $b_i=q(i)$ for some polynomial $q$. Now lets assume that $p$ is used to share $s$ (i.e., $p(0)=s$) and $q$ is used to share $t$. It is the case that $a_ib_i=(p*q)(i)$ and $(p*q)(0)=st$. So, $a_ib_i$ is indeed a valid share from some polynomial which evaluates to $st$ at $0$. There are, however, two problems.

  1. The polynomial $(p*q)$ does not have random coefficients. The coefficients will depend on each other
  2. The degree of the polynomial changes. Lets say that both $p$ and $q$ have degree $r$ (thus it takes $r+1$ shares to reconstruct the secret). The polynomial $(p*q)$ has degree $2r$, so it would take $2r+1$ shares to reconstruct $st$.

For these reasons, MPC protocols which use Shamir have a multiplication protocol which fixes these issues.

Another possibility
I don't even know if this is a secure secret sharing method (I'm hoping someone can comment). But you could use multiplicative secret sharing.

Fix a multiplicative group, say $\mathbb{Z}_p^*$.

Let $a_i$ be shares of $s$ such that $s=\displaystyle\prod_i(a_i)$ and similarly $b_i$ are shares of $t$. Then thanks to the commutativity of multiplication $a_ib_i$ would be a multiplicative share of $st$

| improve this answer | |
  • $\begingroup$ So evaluating $a_j+b_j$ gives a secret sharing of $ab$ for Shamir's secret sharing? @mikeazo $\endgroup$ – meta_warrior Nov 4 '13 at 4:43
  • $\begingroup$ @freak_warrior, no $a_j+b_j$ gives a share of $a+b$, $a_jb_j$ gives a share of $ab$ but with the caveats listed above. $\endgroup$ – mikeazo Nov 4 '13 at 12:52
  • 1
    $\begingroup$ @freak_warrior, FYI I asked a specific question about the multiplicative version: crypto.stackexchange.com/questions/11535/… $\endgroup$ – mikeazo Nov 5 '13 at 15:24

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.