-1
$\begingroup$

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?

$\endgroup$
16
  • 3
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Dec 16, 2021 at 22:20
  • $\begingroup$ 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. $\endgroup$
    – Macko
    Dec 16, 2021 at 22:26
  • $\begingroup$ Why do you care about the coefficients? Isn't the only thing you're interested in recovering is the secret? $\endgroup$
    – poncho
    Dec 16, 2021 at 22:29
  • 1
    $\begingroup$ 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 $\endgroup$
    – poncho
    Dec 16, 2021 at 23:14
  • 1
    $\begingroup$ @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) $\endgroup$
    – poncho
    Dec 21, 2021 at 22:11

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is Lagrange interpolation better than gaussian elimination in finding polynomial coefficients? can describe how to do sample interpolation using Lagrange to find coefs? $\endgroup$
    – Macko
    Dec 16, 2021 at 23:05
  • $\begingroup$ 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. $\endgroup$
    – Pegasus
    Dec 16, 2021 at 23:15
  • $\begingroup$ Can u give all constraints when generating new shares for given secret: like threshold not less than 2? etc $\endgroup$
    – Macko
    Dec 16, 2021 at 23:19
  • $\begingroup$ 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. $\endgroup$
    – Pegasus
    Dec 16, 2021 at 23:27

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.