Shamir Secter Sharing in standard version (paper version) works pretty good with Lagrange Interpolation to generate more shares. Problems arise when you generate more pairs (xi, yi) and you try to reconstruct the secret from shares which are kind of distant to each other. Algorithm works but value of secret you get is somehow different, which is unacceptable for production usage. I think it is related to the Runge Phenomenon.

So what are the options? Are there any better interpolations to be used? Maybe there is some kind of way of generating (xi,yi) from secret that could give stable results by Lagrange?

I switched currently to gaussian as the most stable computationally.

  • 3
    $\begingroup$ That doesn't seem correct. Are you working in a finite field with integer values? There should not be any precision loss in the coefficient/value pairs, so interpolation (with a sufficient amount of points) should yield an exact result. See also this: crypto.stackexchange.com/questions/14608/… $\endgroup$
    – Morrolan
    Dec 17, 2021 at 12:21
  • $\begingroup$ I'm not working in finite field. I generate 5 shares on start with threshold set to 2. Than I generate 5 more passing as input at least 2 shares from starting generation. $\endgroup$
    – Macko
    Dec 17, 2021 at 13:55
  • 2
    $\begingroup$ @Morrolan I've been posting this several times this week, but it's important to dispel the misconception that you absolutely need a finite field. Any finite ring works as long as the points you choose for evaluation satisfy certain property (non-zero differences being invertible) crypto.stackexchange.com/a/96507/13843 . Of course, the real numbers, being infinite, do not fall within this category. $\endgroup$
    – Daniel
    Dec 17, 2021 at 16:41
  • 1
    $\begingroup$ It's also worth mentioning that SSS does not require lagrange interpolation, and extensions of it can be useful. In particular, SSS can be recast in terms of Reed-Solomon codes. Using standard Reed-Solomon decoding (say Berklamp-Massay), one can get a version of SSS that is tolerant to some number of shares being corrupted (the underlying Reed-Solomon code "corrects" these "errors"). This does require changing the reconstruction/decoding algorithm though. $\endgroup$
    – Mark Schultz-Wu
    Dec 17, 2021 at 17:32
  • 1
    $\begingroup$ @Macko getting into these details would likely only confuse you at this point. Your takeaways should be that SSS requires "finite arithmetic" (you can simplify to finite fields to start) for the security proof to go through. In this finite field setting, lagrange interpolation works fine. There are other options as well (such as Berkleamp Massay) if you have more specialized requirements, but you haven't expressed that you do yet. In the finite arithmetic setting, there is no Runge phenonama, so your problem should be resolved (and your construction will actually be secure - it currently isnt) $\endgroup$
    – Mark Schultz-Wu
    Dec 17, 2021 at 19:25


Your Answer

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

Browse other questions tagged or ask your own question.