Score:1

Shamir's secret sharing homomorphism for different degree polynomials

tr flag

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?

kodlu avatar
sa flag
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.
Mona avatar
tr flag
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?
Score:2
ru flag

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 avatar
tr flag
Thank you very much for your answer. But what do you mean by "(if the leading coefficients are sign changes of each other)"?
Daniel S avatar
ru flag
@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$.
Mona avatar
tr flag
Yeah! I thought so, but I wanted to double-check. Thank you very much for your help.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.