# Time complexity of a brute force attack on Shamir's Secret Sharing SSS

I have searched everywhere in academic papers about time complexity of a brute force attack on a Shamir's Secret Sharing key. I'm confused between if it is $$O(p^k)$$ or $$O(p)$$, such that $$p$$ is the modulo of encryption and $$k-1$$ is the degree of the encryption polynome. Because practically, if we're going to rebuild the polynome of encryption, it's equivalent to brute forcing all $$p$$ possible values for the $$k$$ coeficients, which leads to an $$O(p^k)$$ algorithm. But searching directly the secret which is the constant coefficient of the polynome, and knowing that $$S, leads to an $$O(p)$$ algorithm. Could anyone tell me please what's the right one, and if it is $$O(p^k)$$, why the linear algorithm doesn't work ?

I have searched everywhere in academic papers about time complexity of a brute force attack on a Shamir's Secret Sharing key.

A brute force attack isn't possible; even if you could perform any arbitrary computation, with $$k-1$$ shares, you still would not obtain any information on the secret (assuming that randomness was used to generate the shares; if they were generated via a deterministic random number generator, you could).

Because practically, if we're going to rebuild the polynome of encryption, it's equivalent to brute forcing all $$p$$ possible values for the $$k$$ coeficients, which leads to an $$O(p^k)$$ algorithm.

No, even that doesn't work, because there's no way to determine whether you found the correct polynomial; for any possible value of the secret, there is an equal number of polynomials that are consistent with it. Hence, you obtain no information (even probabilistic information) about the secret.

• thanks for the fast answer ! but I found here [link] (ijcaonline.org/archives/volume155/number13/…) that The value of p should not be too small or it could be susceptible to brute-force attack. If the value of p is 128 bits then this provides 2^128 possible values, which is a range too large for brute force to ever attempt. What does it mean then ? Jun 8, 2021 at 14:19
• If there's some way to verify the secret, it can be brute-forced, but that's not really attacking SSS. Jun 8, 2021 at 14:34
• @AmanGrewal so that means that attacking SSS is equivalent to rebuilding the polynomial used in encryption and not only refinding the secret ? Jun 8, 2021 at 15:11
• @HamzaBa-mohammed: that comment you found is wrong Jun 8, 2021 at 16:28
• @AmanGrewal: "if there's some way to verify the secret"; well, yes, if you can search through all possible secret values, and detect which is the right one, yes, you can learn it. However, you're not using the shares; they don't give you any information that you didn't already have Jun 8, 2021 at 16:29