Join Log in
Score:0
hambam avatar Crypto

Proof of theoritical security of Shamir's secret sharing

in flag
hambam

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 ?

93
0 + 4
kelalaka avatar
in flag
kelalaka
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!
0
Reply
hambam avatar
in flag
hambam
@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.
0
Reply
kelalaka avatar
in flag
kelalaka
What is the difference between testing all possible candidates of shares of size 256-bit and brute-forcing the AES-256?
2
Reply
hambam avatar
in flag
hambam
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..
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.