# Shamir Secret Sharing and recover polynomial function from shares

I've got working first part of SSS scheme so I can use some secret number as an input and generate some random polynomial function and create simple shares as pairs (xi, yi).

The task is how to get secret reconstructed from shares? We all know that we must do some clever math guessing to find coeffs. What are options or algorithms / approches to find coefs? What are the pros and cons of each? How whould it differ in finite fields?

• Welcome to Cryptgraphy.SE SSS must work in finite fields. Are you want to describe us to recover the secret given the share? It is well-written in Wikipedia. If something not clear, you can ask about it. Dec 16, 2021 at 22:20
• I want to know especially in classic approch how to find coeffs of polynomial which was used at the moment of generating first shares. I know that there are one but it has some drawbacks in implementation - i mean gaussian. Dec 16, 2021 at 22:26
• Why do you care about the coefficients? Isn't the only thing you're interested in recovering is the secret? Dec 16, 2021 at 22:29
• Well, you know the standard secret reconstruction logic takes a series of share $(x_1, y_1), (x_2, y_2), ..., (x_t, y_t)$, and returns the shared secret, which is the polynomial evaluated at 0. So, to construct the share at x coordinate $x'$, we take the artificial shares $(x_1 - x', y_1), (x_2 - x', y_2), ..., (x_t - x', y_t)$, and give that to the secret reconstruction logic - that gives you the original polynomial evaluated at $x'$, that is, the corresponding coordinate $y'$ - the new share is $(x', y')$. Rinse and repeat for all the additional shares you need Dec 16, 2021 at 23:14
• @Macko: "I put them to my Interpolation function and calculate at x'"; no, compute the Interpolation at 0 (that is, do precisely the standard secret-reconstruction logic) Dec 21, 2021 at 22:11