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

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$?

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!

• In your example, the math just so happens to work out for this one case. It won't in many others. – mikeazo Sep 30 '17 at 3:21
• 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$. – Rick Sep 30 '17 at 12:08
• But does it happen with all subset of shares? – mikeazo Sep 30 '17 at 15:39
• 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. – Jyrki Lahtonen Oct 4 '17 at 5:33
• 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. – tylo Oct 4 '17 at 11:01

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.