Score:0

Crypto

Shamir Secret Sharing and replacement for Lagrange interpolation

Macko

4/17/23, 10:11 AM

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.

0 + 0

secret-sharing

Morrolan

4/17/23, 12:21 PM

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: https://crypto.stackexchange.com/questions/14608/does-runge-phenomenon-affect-shamirs-secret-sharing-scheme?rq=1

Macko

4/17/23, 1:55 PM

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.

poncho

4/17/23, 2:11 PM

If you're not working in a finite field, why do you believe what you're doing is secure?

Macko

4/17/23, 2:40 PM

So u are stating that if I do interpolation in finite field Lagrange will work correctly ? Let's stick to the question ...

Morrolan

4/17/23, 2:47 PM

Yes. In a finite field you will not suffer any kind of precision loss, so interpolation is guaranteed to produce the original polynomial we have started with. See the answer linked above for some more details. But it's important to understand that working in a finite field is **absolutely required** for security. Shamir's secret sharing over the reals provides very little in terms of security.

Daniel

4/17/23, 4:41 PM

@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) https://crypto.stackexchange.com/a/96507/13843 . Of course, the real numbers, being infinite, do not fall within this category.

Mark

4/17/23, 5:32 PM

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.

Macko

4/17/23, 6:27 PM

@Daniel so if I don't abosuletely need finite field how to choose points ? If I choose points according to some rule (needs explanation) than interpolation should work for them?

Macko

4/17/23, 6:29 PM

@Mark does Reed-Solomon use finite field under the hood? Is Reed-Solomon a generalized version of SSS ?

Macko

4/17/23, 7:10 PM

So I choose option of changeing interpolation: how about Chebyshev ?

Mark

4/17/23, 7:25 PM

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

Elon Musk

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

EN: Shamir Secret Sharing and replacement for Lagrange interpolation

TH: Shamir Secret Sharing และแทนที่การแก้ไข Lagrange

RO: Shamir Secret Sharing și înlocuirea interpolării Lagrange

RU: Shamir Secret Sharing и замена интерполяции Лагранжа

VI: Shamir Secret Chia sẻ và thay thế cho phép nội suy Lagrange

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.