Shamir Interpolation Problem (Recovering secret with fewer parts than the threshold)

Question

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!

Answer 1

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.