# Shamir's secret sharing homomorphism for different degree polynomials

The $$(t,n)$$ Shamir’s polynomial based secret sharing scheme is $$(+,+)$$-homomorphic in which the addition of two polynomials secrets equals the Lagrange’s interpolation of the sum-of-shares for the same subset of shares.

My question is: Does the two polynomials need to have the same degree to satisfy the SSS $$(+,+)$$-homomorphic property? Specifically, suppose that polynomial $$P_1$$ defines secret $$s_1$$ and polynomial $$P_2$$ defines secret $$s_2$$. The first polynomial $$P_1$$ is of $$(t-1)$$-degree and the second polynomial $$P_2$$ is $$(m-1)$$-degree in which $$m\ge t$$. Suppose I have $$m$$ shareholders. In this case, can I still say that SSS is $$(+,+)$$-homomorphic for the same subset of $$m$$ shares?

• If $m>t,$ then $t$ shares determine $P_1$ but $t$ shares are not enough to uniquely determine $P_2$. You need to precisely clarify what exactly you are asking mathematically. Oct 27, 2022 at 22:56
• Yes, I corrected the question. If I have m shareholders available to participate in the SSS. This should recover P_2 and P_1 polynomials. But can I still say that this is a SSS (+,+)-homomorphic?
– Mona
Oct 28, 2022 at 1:10

Yes. The polynomial $$P_3(x)=(P_1+P_2)(x)$$ is of degree $$m-1$$ and we can see that if we have shares $$P_1(x_i)=s_{1,i}$$ and $$P_2(x_i)=s_{2,i}$$ for $$1\le i\le m$$ then $$P_3(x_i)=s_{1,i}+s_{2,i}$$ and we can write $$s_{3,i}$$ for these recovered values. We now have $$m$$ points $$(x_i,s_{3,i})$$ through which $$P_3$$ passes and so can recover $$P_3(x)$$.
In general SSS works if we replace the words "polynomials of degree $$m$$" with the words "polynomial of degree at most $$m$$", though secrets that are known to be associated with a polynomial of smaller degree can be recovered by a smaller set of colluders. Note that if $$F_1$$ and $$F_2$$ are two polynomials of degree $$m$$ it is possible (albeit unlikely) that $$F_1+F_2$$ is a polynomial of degree less than $$m$$ (if the leading coefficients are sign changes of each other).
• @Mona for example if $F_1(x)=17x^m-13x^{m-1}+\cdots-5$ and $F_2(x)=-17x^m+7x^{m-1}+\cdots -23$ then $F_1+F_2=-6x^{m-1}+\cdots -28$. Oct 28, 2022 at 11:13