4
$\begingroup$

I'm studying about polynomials and interpolation with shamir secret sharing. I have some questions about it.

I found that there are always lower-degrees polynomials that intersects with 2 or more points (passing through 0) with another polynomial of degree at least 3 (in Zp).

Example: Supose a secret sharing scheme with threshold $5$, with the polynomial $x^4$ in $Z_{11}$ and the secret is $0$. Theoretically i could only recover the original polynomial and consequently the independent term (secret = $0$) if i have at least 5 points, right? However, if i combine correctly some shares $(x, f(x))$, i could recover another polynomial with the same independent term, and consequently, the secret. For example, instead of combining 5 points, i could combine the points $(1, 2, 8)$ with their evaluations and recover the polynomial $g(x) = 7x^2 + 5x + 0$. This gives to me the secret $0$.

Now supose all the polynomials $a_4x^4 + a_3x^3 + a_2x^2 + a_1x + a0$ where $\{a_4, a_3, a_2, a_1, a_0\} \in Z_{11}$.

All polynomials of degree 3, 4, ..., $n$ have this property. Some secrets could be recovered with 2, 3, ... points and others only with 2 or 3 or more points. Note that even using less points (2 or 3) its not monotonic.

Questions:

1 - Is it correct to say that there is some kind of "failure" of shamir secret sharing scheme because of this combination of points?

2 - Could i prove that there are always less degree polynomials that intersects with high degree polynomials in point 0 and another one in $Z_p$?

Edit: I've made some experiments.

I have picked all combinations $C^p_2$ and $C^p_3$ of $(x, (fx))$ to all polynomials $ a_3x^3 + a_2x^2 + a_1x + a0$ where $\{a_3, a_2, a_1, a_0\} \in Z_{5}, Z_{7}$ and $a_3 > 0$. I can always recover the secret using less points than the threshold.

Thanks to everyone!

$\endgroup$
10
  • $\begingroup$ In your example, the math just so happens to work out for this one case. It won't in many others. $\endgroup$
    – mikeazo
    Sep 30, 2017 at 3:21
  • $\begingroup$ Actually it happens in all polynomials of $Z_5$, $Z_7$ and $Z_11$ with my experiments. I have a "feeling" that it happens to all polynomial in all $Z_p$. $\endgroup$
    – Rick
    Sep 30, 2017 at 12:08
  • $\begingroup$ But does it happen with all subset of shares? $\endgroup$
    – mikeazo
    Sep 30, 2017 at 15:39
  • 1
    $\begingroup$ As mikeazo explains this is not a weakness of Shamir's scheme. Algebraically it is because given less than the required number of points on the graph of a polynomial of a bounded degree you can add any point $(0,S)$ to the list of points the graph must go thru, and find a solution for any value $S$ of the secret. Therefore no small set of colluding users can reliably recover the secret unless they have some side information. $\endgroup$ Oct 4, 2017 at 5:33
  • 1
    $\begingroup$ Actually, if it was impossible to recover the secret without guessing, then the adversary could just try out various combinations and look for the value which isn't possible. Information theoretic security is absolute in that sense - knowing less than the required number of shares is equivalent to knowing nothing, and then you can always guess the secret. Btw, in a setting with 5 shares the polynomial actually could be just degree 4 or even less - $0$ must not be excluded for any of the coefficients to achieve information theoretic security. $\endgroup$
    – tylo
    Oct 4, 2017 at 11:01

1 Answer 1

4
$\begingroup$

I have picked all combinations $C^p_2$ and $C^p_3$ of $(x, (fx))$ to all polynomials $ a_3x^3 + a_2x^2 + a_1x + a0$ where $\{a_3, a_2, a_1, a_0\} \in Z_{5}, Z_{7}$ and $a_3 > 0$. I can always recover the secret using less points than the threshold.

From your comments, it sounds like when you say "I can always recover the secret" what you mean is that there is some subset of shares that results in the correct secret. Not that all subsets of shares always reveals the correct secret.

That is the expected behavior. Under the typical usage of Shamir secret sharing, a subset of fewer than the threshold can use their shares to try to recover a secret, but they will have no idea if they are correct, and their probability of being correct is no better than random guessing.

You said in a comment that "if you consider that the Dealer can be malicious". Shamir never claimed (or proved) the scheme to be secure in the presence of a malicious dealer. For that threat model, you would have to use other schemes.

$\endgroup$
2
  • $\begingroup$ How to get back polynomial function from enough shares? How to find coeffs ? $\endgroup$
    – Macko
    Dec 16, 2021 at 21:37
  • $\begingroup$ @macko, I suggest you ask this as a new question on the site. $\endgroup$
    – mikeazo
    Dec 19, 2021 at 1:13

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.