Shamir's secret sharing can be considered multiplicatively homomorphic, if one is aware of the fact that multiplying two shares of a (n,t)-threshold shared secret yields a share of the same secret, but over a (n, 2t)-threshold sharing.
To overcome this, there is a secure degree reduction protocol, which is already explained in this question. My follow-up question tackles an unexplained point in that question's accepted answer:
The subsharings ($\sigma_3(x)$ to $\sigma_5(x)$ in the referenced answer) are polynomials of degree 1, i.e. 2 shares are needed for proper recombination.
However, trying this using two arbitrary shares for interpolation fails. At the end of this question I paste a short Python script using VIFF that shows the misbehavior. When using a threshold of 2 (needing 3 shares) for recombining the subshares, then the final shares can be arbitrarily recombined using only two shares, as expected from the secure degree reduction protocol.
How comes that you need a larger number of subshares than the degree of the corresponding polynomials for proper recombination?
In the following the Python snippet (note that there is a 1/11 chance that the lower threshold accidentially works):
from viff import shamir from viff.field import GF # Zp(x) gives an object that corresponds to x mod 11 and allows for multiplication # I.e., Zp(3) * Zp(5) == Zp(15) == Zp(4) Zp = GF(11) # Share 5 and 2 among 3 players with threshold 1 (>= 2 shares needed) t = 1 sh1 = (shamir.share(Zp(5), t, 3)) sh2 = (shamir.share(Zp(2), t, 3)) # Multiply shares, implies shares for 5*2 = 10, but threshold is 2 multiplied_shares = [ (Zp(i+1), sh1[i] * sh2[i]) for i in xrange(0, 3) ] print('Recombination ' + ('works' if shamir.recombine(multiplied_shares[0:2*t+1]) == Zp(10) else 'does not work')) # Create subshares of the multiplied shares, using threshold 1 (*) sh3 = shamir.share(multiplied_shares, t, 3) sh4 = shamir.share(multiplied_shares, t, 3) sh5 = shamir.share(multiplied_shares, t, 3) # Distribute the subshares p1_shares = [ (Zp(1), sh3), (Zp(2), sh4), (Zp(3), sh5) ] p2_shares = [ (Zp(1), sh3), (Zp(2), sh4), (Zp(3), sh5) ] p3_shares = [ (Zp(1), sh3), (Zp(2), sh4), (Zp(3), sh5) ] # Try to recombine subshares using threshold 1 fails despite sharing (*) above p1_final1 = shamir.recombine(p1_shares[0:t+1]) p2_final1 = shamir.recombine(p2_shares[0:t+1]) p3_final1 = shamir.recombine(p3_shares[0:t+1]) final_shares1 = [ (Zp(1), p1_final1), (Zp(2), p2_final1), (Zp(3), p3_final1) ] final1 = shamir.recombine(final_shares1[0:t+1]) print(str(final1) + ' is ' + ('' if final1 == Zp(10) else 'NOT ') + 'correct') # However, recombining subshares using threshold 2 works p1_final2 = shamir.recombine(p1_shares[0:2*t+1]) p2_final2 = shamir.recombine(p2_shares[0:2*t+1]) p3_final2 = shamir.recombine(p3_shares[0:2*t+1]) final_shares2 = [ (Zp(1), p1_final2), (Zp(2), p2_final2), (Zp(3), p3_final2) ] final2 = shamir.recombine(final_shares2[0:t+1]) print(str(final2) + ' is ' + ('' if final2 == Zp(10) else 'NOT ') + 'correct')