Fwd: Shamir secret sharing and information theoretic security

R.A. Hettinga rah at shipwright.com
Tue Feb 24 13:43:51 PST 2009


Begin forwarded message:

> From: hal at finney.org ("Hal Finney")
> Date: February 23, 2009 2:30:16 PM EST
> To: leichter at lrw.com, sbg at acw.com
> Cc: cryptography at metzdowd.com, rah at shipwright.com
> Subject: Re: Shamir secret sharing and information theoretic security
>
>> Is it possible that the amount of information that the knowledge of a
>> sub-threshold number of Shamir fragments leaks in finite precision  
>> setting
>> depends on the finite precision implementation?
>>
>> For example, if you know 2 of a 3 of 5 splitting and you also know  
>> that
>> the finite precision setting in which the fragments will be used is  
>> IEEE
>> 32-bit floating point or GNU bignum can you narrow down the search  
>> for the
>> key relative to knowing no fragments and nothing about the finite
>> precision implementation?
>
> No, not really. Think of this simple example.
>
> We will have two shares, x and y. Let's work mod 10 to make it  
> simple. The
> secret value v will be x + y mod 10. The shares are created by  
> choosing a
> random value for x, and then setting y to be v - x mod 10.
>
> So for example if you want to share v = 5, and x is 9, then y will  
> be 6:
> 9 + 6 = 5 mod 10.
>
> Suppose that you happen to know from other information that the secret
> value v is either 1 or 2. Now you learn a share value x = 5. How much
> have you learned about v?
>
> Nothing: you can deduce that y is either 6 or 7, but you have no way
> of knowing which.  Whatever x had turned out to be, there would be a y
> value corresponding to each possible v value. Learning a share tells  
> you
> nothing about v, and in general Shamir sharing, learning all but one  
> of
> the needed shares similarly tells you nothing about the secret.
>
> Hal Finney





More information about the cypherpunks-legacy mailing list