Prev: GOST hash, BROKEN?
Next: My Recent Posts and the Fallout Aggro.
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.