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<p$, 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 ?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ 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 ? $\endgroup$– hambamCommented Jun 8, 2021 at 14:19
-
1$\begingroup$ If there's some way to verify the secret, it can be brute-forced, but that's not really attacking SSS. $\endgroup$ Commented Jun 8, 2021 at 14:34
-
$\begingroup$ @AmanGrewal so that means that attacking SSS is equivalent to rebuilding the polynomial used in encryption and not only refinding the secret ? $\endgroup$– hambamCommented Jun 8, 2021 at 15:11
-
1$\begingroup$ @HamzaBa-mohammed: that comment you found is wrong $\endgroup$– ponchoCommented Jun 8, 2021 at 16:28
-
3$\begingroup$ @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 $\endgroup$– ponchoCommented Jun 8, 2021 at 16:29