Shamir's secret sharing homomorphism for different degree polynomials

Mona

10/27/23, 8:47 PM

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?

163

1 + 2

homomorphic-encryption

secret-sharing

threshold-cryptography

homomorphic-signatures

kodlu

10/27/23, 10:56 PM

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

10/28/23, 1:10 AM

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

Crypto

Daniel S

10/28/23, 7:05 AM

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

+ 3

Mona

10/28/23, 10:37 AM

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

10/28/23, 11:13 AM

@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

10/28/23, 3:30 PM

Yeah! I thought so, but I wanted to double-check. Thank you very much for your help.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Shamir's secret sharing homomorphism for different degree polynomials

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.