3
$\begingroup$

In the shamir secret sharing scheme, the Secret s is set as the constant in the equation

$ y_p = s+ \sum_{i=0}^{i = t-1} a_i * x_p^i$

s can only be the constant term or the last coefficient or the secret may be leaked. This is also per question below:

Coefficients in Shamir's Secret Sharing Scheme

How can I show this rigorously in a mathematical way? In the provided answer only an example is given.


Updated:

The mathematical way I currently have to show this is for the case of a (t,n) system where t = 3, sharing between two people, and y defined as

$y_1 = a_0 + s*x_1 + a_1*x_1^2$ mod P

$y_2 = a_0 + s*x_2 + a_1*x_2^2$ mod P

Then by rearranging (or by taking inverse of matrix) we have

$s = (y_2 - y_1)(x_2 - x_1) ^{-1} - a_1(x_2+x_1)$ mod P

and we get the case where S is revealed when $(x_2+x_1)$ mod P = 0.

How would we show using similar (or different) argument for t>=3, t-1 shares, that we will not have similar cases when s is the constant or the very last coefficient?

$\endgroup$
  • $\begingroup$ The answer to your linked question is perfectly rigorous: it shows that in some cases it is possible for an attacker to recover the middle coefficient even if they don't have enough shares to recover the polynomial completely, because all the possible polynomials have the same middle coefficient. Are you asking why this cannot happen with the constant coefficient? $\endgroup$ – fkraiem Dec 16 '19 at 16:03
  • $\begingroup$ Hi, yes your right, sorry for the confusion. To be more precise I wish to show rigorously why such cases as mentioned in the link cannot happen for if s is the constant term and also (having read the linked question more carefully) the very last coefficient i.e. $a_{t-1}$. Thanks for helping clarify. $\endgroup$ – ackbar03 Dec 16 '19 at 16:13
  • $\begingroup$ In the example given in the other post, the very last co-efficient is secure. But this cannot be extended to the general case. If $t\ge 3$, similar attacks can be constructed to reveal $a_{t-1}$. The only secure co-efficient is the constant term (or the first co-efficient in your words). $\endgroup$ – Changyu Dong Dec 16 '19 at 16:21
  • $\begingroup$ @ChangyuDong Hi professor Dong, thanks for taking the time to comment. I updated my question a bit for my interpretation of how to prove the secret is not secure for the linked example. How would I show something similar for t>=3? Is there a special theorem for matrix inverses under finite fields that can be used? Also I've also read from elsewhere that S placed as the final coefficient is secure so I'm quite curious to understand how the proof works. Thanks a lot! $\endgroup$ – ackbar03 Dec 16 '19 at 17:17
2
$\begingroup$

Here's one way to approach the question: if we have a $(n, t)$ Shamir secret sharing system, and we have $t-1$ shares $(x_0, y_0), (x_1, y_1), …, (x_{t-2}, y_{t-2})$, then all we can deduce that the secret polynomial is of the form:

$$P(x) + c \prod_{i=0}^{t-2}(x - x_i)$$

where $P(x)$ is a computable polynomial (exactly what that polynomial is depends on the known shares), and $c$ is an unknown constant (and which we have no information about).

So, the question is: given that the polynomial is of this form (for some $c$), and the secret we want is the $j$th coefficient, can we deduce the coefficient that's the secret we're interested in?

We know the $j$th coefficient for $P(x)$, and so this reduces to whether we know the $j$th coefficient of $c \prod_{i=0}^{t-2}(x - x_i)$; we can if and only if the $j$th coefficient of the polynomial $\prod_{i=0}^{t-2}(x - x_i)$ is 0. If it is 0, then (no matter what $c$ is) the $j$th coefficient of the entire polynomial will be the $j$th coefficient of $P(x)$ (which we know); if it is nonzero, then (depending on what $c$ is) it could be any value.

For the linear term ($j=0$), this coefficient is $\prod_{i=0}^{t-2}-x_i$, which (because we're in a field) is nonzero if and only if all the $x_i$ values are nonzero (which they are in Shamir's scheme).

For the highest term ($j=t-2$), this coefficient turns out to be 1, hence the secret is never leaked (even if the share $x_i=0$ was issued).

For the second term ($j=1$), this coefficient turns out to be $-\sum_{i=0}^{t-2}x_i$, that is, the secret is revealed if $x_0 + x_1 + … + x_{t-2} = 0$, which (for the case $t=3$) is what you came up with. Further note that, if we're in an even characteristic field ($1+1=0$), then $x_0 + x_1 \ne 0$ (unless $x_0 = x_1$, which cannot happen), hence in that specific case, the secret is not revealed.

Since I wrote the original answer, I found yet another corner case which is secure; if the field order is $p^z$ (that is, the field has that many elements), and if $t = p^z-1$, and the share $x_i = 0$ is not issued, then all coefficients are secure. That's because, for any $k$ $(k$ being the share which is not revealed), we have $\prod_{i \in GF(p^z), i \ne 0, k}(x - x_i) = (x^{t} - 1) / (x - k)$, and that doesn't have any 0 coefficients. For course, this really is a corner case, as there are only $t$ possible shares, and we need all $t$, hence this is a $(t, t)$ secret sharing scheme (and if so, why are we bothering with Shamir anyways; there are simpler methods).

Other than those cases, it is plausible for me to speculate (although I don't have proof) that for any middle coefficients, one can find a set $x_0, x_1, …, x_{t-2}$ that does leak the secret, assuming that the adversary can pick which shares he gets (which is analogous to the CPA assumption).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks very much for this. It seems this is much more complicated than what i was expecting, I'll have to digest it a bit. I thought at first the approach would be to show that by writing in the form of matrices, $Xa = y-a_0$, where a is the coefficient vector, we just need to show the inverse $X^{-1} (y-a_0)$ will not lead to a case where the a_0 cancels out for the first and last row, and there's some obscure theorem out there related to this. I guess thats a bit of an oversimplification however. thanks again for taking the time to expand on something you answered six years ago! $\endgroup$ – ackbar03 Dec 21 '19 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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