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
R.A. Hettinga