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.

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.

share|improve this question
    
What secret sharing technique are you using? Shamir? –  mikeazo Nov 2 '13 at 14:35
    
Can be any one @mikeazo –  freak_warrior Nov 2 '13 at 14:39
add comment

1 Answer

up vote 2 down vote accepted

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.

Additive
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.

Shamir
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$

share|improve this answer
    
So evaluating $a_j+b_j$ gives a secret sharing of $ab$ for Shamir's secret sharing? @mikeazo –  freak_warrior Nov 4 '13 at 4:43
    
@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. –  mikeazo Nov 4 '13 at 12:52
1  
@freak_warrior, FYI I asked a specific question about the multiplicative version: crypto.stackexchange.com/questions/11535/… –  mikeazo Nov 5 '13 at 15:24
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.