2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Oct 27, 2022 at 22:56
  • $\begingroup$ 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? $\endgroup$
    – Mona
    Oct 28, 2022 at 1:10

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you very much for your answer. But what do you mean by "(if the leading coefficients are sign changes of each other)"? $\endgroup$
    – Mona
    Oct 28, 2022 at 10:37
  • $\begingroup$ @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$. $\endgroup$
    – Daniel S
    Oct 28, 2022 at 11:13
  • $\begingroup$ Yeah! I thought so, but I wanted to double-check. Thank you very much for your help. $\endgroup$
    – Mona
    Oct 28, 2022 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.