Begin forwarded message:

From: hal@finney.org ("Hal Finney") Date: February 23, 2009 2:30:16 PM EST To: leichter@lrw.com, sbg@acw.com Cc: cryptography@metzdowd.com, rah@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