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 ?

  • $\begingroup$ 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! $\endgroup$
    – kelalaka
    Jun 10 at 22:24
  • $\begingroup$ @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. $\endgroup$ Jun 10 at 22:29
  • 2
    $\begingroup$ What is the difference between testing all possible candidates of shares of size 256-bit and brute-forcing the AES-256? $\endgroup$
    – kelalaka
    Jun 10 at 22:34
  • $\begingroup$ 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.. $\endgroup$ Jun 10 at 22:39

Your Answer

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

Browse other questions tagged or ask your own question.