Score:-1

Crypto

Shamir Secret Sharing and recover polynomial function from shares

Macko

4/16/23, 10:16 PM

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?

113

0 + 0

secret-sharing

kelalaka

4/16/23, 10:20 PM

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](https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Computationally_efficient_approach). If something not clear, you can ask about it.

Macko

4/16/23, 10:26 PM

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.

poncho

4/16/23, 10:29 PM

Why do you care about the coefficients? Isn't the only thing you're interested in recovering is the secret?

Macko

4/16/23, 10:34 PM

Of course there is more: like easy of implementation, fast execution and not vulnerable to attacks (timing). Next step is to how mitigate issues in classic shamir approch - like evil share provider for reconstruction (how to encode share to be invulnarable to tampering).

kelalaka

4/16/23, 10:40 PM

Why do you need the timing attack? Construct the secret on a local off-line computer? There are academics works about SSS without dealer [Shamir secret sharing with no dealer](https://crypto.stackexchange.com/q/84143/18298) and [Duckduckgo](https://duckduckgo.com/?q=shamir+secret+sharing+without+dealer&t=canonical&ia=web)

Macko

4/16/23, 10:42 PM

So I forgot to mention main idea: knowing the coefs are crucial because I want to generate more shares from exiting ones.

kelalaka

4/16/23, 10:57 PM

Divide each share again with SSS?

Macko

4/16/23, 11:06 PM

if I divide each share again with SSS and use some of shares from first generated pool and some divided shares that means I can reconstruct my secret ?

poncho

4/16/23, 11:06 PM

If you have $t$ shares (where $t$ is the threshold), it is straight-forward to generate more shares without bothering to compute the internal coefficients.

Macko

4/16/23, 11:08 PM

wow, please describe it as simple as possible because only way I know was by solving linear equations

poncho

4/16/23, 11:14 PM

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

Macko

4/17/23, 1:48 AM

So generally this interpolation formula is working but interesting is that if i generate share that xi is in range [1..10] than for all combinations of share tuples I can find secret value. This is also true when I generate more shares [15...20] but interesting part is when I mix pairs from this 2 series than distant xi's gives wrong answer in interpolation. So I have bug in my code (which I don't think so) or Lagrange is very limited in interpolation.

Macko

4/17/23, 7:53 AM

So any ideas for replacing Lagrange interpolation ?

Macko

4/21/23, 10:10 PM

@poncho reconstruction is not working as expected: I prepared threshold number of points (shares) which they were generating on beginning, than I created new points (xn-x' ,yn) than I put them to my Interpolation function and calculate at x'. New shares have correct new xi but output from interpolation gives all of them same value. Can please provided example?

poncho

4/21/23, 10:11 PM

@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)

Macko

4/21/23, 10:34 PM

@poncho Great! Yeah! It works like a charm :) and no doubles are used, no solving equations, this is what i wanted :) Thanks so much ...

Score:1

Crypto

Pegasus

4/16/23, 10:59 PM

Let's use a threshold shape (, ) to share a secret value . - 1 random integers 1, 2, ..., − 1 are selected while 0 = . Based on these as factors, the polynomial is built. fx....

Based on this, we obtain random points (, ()) ∶ ≠ 0. Each point is communicated to one of the. Participants. For any subset of points, the polynomial can be reconstructed using the Lagrange interpolation. Having the polynomial (), for the value = 0 we get the value (0) = 0 that is the secret .

Note that for proper secrecy, all operations are done with elements of a finite field with size where first number, greater than all the coefficient values of the polynomial as well as the values t and n.

0 + 0

Macko

4/16/23, 11:05 PM

Is Lagrange interpolation better than gaussian elimination in finding polynomial coefficients? can describe how to do sample interpolation using Lagrange to find coefs?

Pegasus

4/16/23, 11:15 PM

Let be a polynomial of degree t: f (x) = a0 + a1x + ··· +atxt Can be reconstructed from t + 1 points (xi, f (xi)) with different sections (in a unique way), There are infinite degree polynomials of t passing through t such points.

Macko

4/16/23, 11:19 PM

Can u give all constraints when generating new shares for given secret: like threshold not less than 2? etc

Pegasus

4/16/23, 11:27 PM

New shares can be easily added without changing the old ones: Calculating new points. Note there can be more than 1 shares, also polynomial can be edited without need to change the secret.

Elon Musk

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

EN: Shamir Secret Sharing and recover polynomial function from shares

TH: Shamir Secret Sharing และกู้คืนฟังก์ชันพหุนามจากการแชร์

RO: Shamir Secret Sharing și recuperați funcția polinomială din acțiuni

RU: Shamir Secret Sharing и восстановление полиномиальной функции из акций

VI: Shamir Secret Sharing và khôi phục chức năng đa thức từ chia sẻ

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.