From: Michael Armitage on 7 Jul 2010 23:28 Hi, I was informed a few years ago that Shamir's secret sharing scheme is essentially a form of natural error correction coding. That is, in the scenario where say n=5 and t=4 and I have all 5 shares but two of them are corrupt. Apparnetly I can use the other shares to repair the two damaged ones. Is there any truth to this? If so could someone point me to some literature or examples of how I might implement this kind of error correction on top of Shamir's scheme running in GF(2^k). If it's even possible, I assume I would need to include some form of integrity check, i.e a hash of the original secret. This is not great as it would remove the information theoretic security property... Obviously to do this properly I should add parity to the shares, but if bits are costly, can it be done? Thanks.
From: Paul Rubin on 7 Jul 2010 23:46 Michael Armitage <mick(a)internet.com> writes: > I was informed a few years ago that Shamir's secret sharing scheme is > essentially a form of natural error correction coding. It sort of resembles a Reed-Solomon code if that's what you mean. > That is, in the scenario where say n=5 and t=4 and I have all 5 shares > but two of them are corrupt. Apparnetly I can use the other shares to > repair the two damaged ones. > > Is there any truth to this? Certainly not. You could do that with t=3 though. Do you know how the Lagrange interpolating polynomial works? Basically you pick t points, compute the degree t-1 interpolating polynomial through them, then pick some additional points of the polynomial. So in your example, say the 5 shares are a,b,c,d,e where d and e are corrupted. If d and e tell you nothing about the curve, and you only have 3 points on it, the other points could be anything.
From: Michael Armitage on 8 Jul 2010 00:06 On Wed, 07 Jul 2010 20:46:29 -0700, Paul Rubin wrote: > Michael Armitage <mick(a)internet.com> writes: >> I was informed a few years ago that Shamir's secret sharing scheme is >> essentially a form of natural error correction coding. > > It sort of resembles a Reed-Solomon code if that's what you mean. > >> That is, in the scenario where say n=5 and t=4 and I have all 5 shares >> but two of them are corrupt. Apparnetly I can use the other shares to >> repair the two damaged ones. >> >> Is there any truth to this? > > Certainly not. You could do that with t=3 though. Do you know how the > Lagrange interpolating polynomial works? Basically you pick t points, > compute the degree t-1 interpolating polynomial through them, then pick > some additional points of the polynomial. So in your example, say the 5 > shares are a,b,c,d,e where d and e are corrupted. If d and e tell you > nothing about the curve, and you only have 3 points on it, the other > points could be anything. Ok thank you. So essentially if n=5 and t=3, I would just swap the two corrupt shares with the two additional shares. And if there is any more than 2 corrupt shares then I ultimatly have unknowns in the polynomial and can't resolve that. So if i want error correction alongside the shares, I need to either increase n so I have redundant shares I can swap in if required or I will have to implement Reed-Solomon, which sounds like a nasty sized implementation in itself sadly.
From: Paul Rubin on 8 Jul 2010 00:16 Michael Armitage <mick(a)internet.com> writes: > So if i want error correction alongside the shares, I need to either > increase n so I have redundant shares I can swap in if required or I will > have to implement Reed-Solomon, which sounds like a nasty sized > implementation in itself sadly. You mean add error correction to the individual shares? Yeah you could do that. Is corrupting the shares likely to be a real problem? Of course you'd normally encrypt the shares, so you'd want the error correction on the ciphertext. Reed-Solomon isn't that hard. It's basically the same as Shamir's scheme. Or you could use some utility for it. Or just give each shareholder several copies of their share.
From: dvsarwate on 4 Aug 2010 12:54 On Jul 7, 10:28 pm, Michael Armitage <m...(a)internet.com> wrote: > Hi, > > I was informed a few years ago that Shamir's secret sharing scheme is > essentially a form of natural error correction coding. > > That is, in the scenario where say n=5 and t=4 and I have all 5 shares > but two of them are corrupt. Apparnetly I can use the other shares to > repair the two damaged ones. > > Is there any truth to this? If so could someone point me to some > literature or examples of how I might implement this kind of error > correction on top of Shamir's scheme running in GF(2^k). If it's even > possible, I assume I would need to include some form of integrity check, > i.e a hash of the original secret. This is not great as it would remove > the information theoretic security property... > > Obviously to do this properly I should add parity to the shares, but if > bits are costly, can it be done? > > Thanks. See R.J. McEliece and D.V. Sarwate, On sharing secrets and Reed-Solomon codes, Communications of the ACM, Volume 24, Issue 9, Sep 1981. --Dilip Sarwate
|
Pages: 1 Prev: GOST hash, BROKEN? Next: My Recent Posts and the Fallout Aggro. |