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

hambam

10/8/22, 1:18 PM

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 ?

127

1 + 0

brute-force-attack

secret-sharing

complexity

Score:3

Crypto

poncho

10/8/22, 2:04 PM

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.

0 + 5

hambam

10/8/22, 2:19 PM

thanks for the fast answer ! but I found here [link] (https://www.ijcaonline.org/archives/volume155/number13/kannan-2016-ijca-912051.pdf) 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 ?

Aman Grewal

10/8/22, 2:34 PM

If there's some way to verify the secret, it can be brute-forced, but that's not really attacking SSS.

hambam

10/8/22, 3:11 PM

@AmanGrewal so that means that attacking SSS is equivalent to rebuilding the polynomial used in encryption and not only refinding the secret ?

poncho

10/8/22, 4:28 PM

@HamzaBa-mohammed: that comment you found is wrong

poncho

10/8/22, 4:29 PM

@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

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: ความซับซ้อนของเวลาของการโจมตีด้วยกำลังเดรัจฉานใน Secret Sharing SSS ของ Shamir

RO: Complexitatea temporală a unui atac cu forță brută asupra SSS Secret Sharing a lui Shamir

RU: Временная сложность атаки грубой силы на SSS Shamir's Secret Sharing

VI: Độ phức tạp về thời gian của một cuộc tấn công vũ phu vào SSS Chia sẻ Bí mật của Shamir

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.