# Proof of theoritical security of Shamir's secret sharing

community !

I'm looking for the proof of theoritical security of Shamir's secret sharing. I found some articles saying that it's assimilable to the halting problem, which implies that there is no general algorithm to solve it for all possible program-input pairs. But, I don't understand why it stands for SSS encryption.. Why we say that we can only calculate all possible solutions for a threeshold whitout been able to verify them ?

I mean for example, for a $$(k,n)$$ threeshold we can build $$2^{Nk}$$ distinct polynomials ($$N$$ the number of bits of encryption) with a brute force, then build $$k$$ shares with eash polynomial, then verify if those shares lead to the right secret by Lagrange's interpolation or by Gaussian elimination. Thus and with a suffisant power of computing, we must soon or late find the secret.

Furthermore, I think that this brute force could be optimized to $$O(2^N)$$ if we consider only testing the constant polynomials, which means brute forcing directly on the $$2^N$$ possible values that the secret could take.

So I'm basically wondering : why this scenario isn't possible ? Where is the fault in my thought ?

• You are missing the important point; How you can in/validate each candidate? Also, even you can verify you still need to test all possible cases like in OTP! Jun 10 at 22:24
• @kelalaka couldn't we just inject every set of $k$ shares we generate to the authentification system (decoding system) as if it was the real shares ? I mean "practically" testing them and not only theoritically proving it's the valid candidate. Jun 10 at 22:29
• What is the difference between testing all possible candidates of shares of size 256-bit and brute-forcing the AES-256? Jun 10 at 22:34
• Well I truely don't know.. I'm "very" new in this field so excuse my ignorance haha But, I would say that testing all possible candidates would lead to the secret , while brute-forcing the AES-256 should lead to the unique polynomial that was used to create the original shares. But I'm not sure, just supposing.. Jun 10 at 22:39