0
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
5
  • $\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$ Jun 8 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$ Jun 8 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$ Jun 8 at 15:11
  • $\begingroup$ @HamzaBa-mohammed: that comment you found is wrong $\endgroup$
    – poncho
    Jun 8 at 16:28
  • 2
    $\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$
    – poncho
    Jun 8 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.