On Feb 23, 2009, at 1:05 PM, s...@acw.com wrote:

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?
I've never seen any work done in this direction. When you consider exact values, FP arithmetic is very messy and has almost no nice mathematical properties. (It's nice in a model where all you care about is relative error - which is actually a rather unnatural model!) As a result, I think it's unlikely you can come up with any general theory here. But you can probably come up with examples showing that there's a problem. It's usually easiest to work with a simpler form of FP math - e.g., assume 4 decimal digits and a 1-digit decimal exponent. Consider just quadratics, which we can write as p(x) = (x - r1)*(x - r2). If r1*r2 overflows in a particular FP system, you can't write down the value of the constant coefficient - hence, you can't write down the value p(0). Yet p(1) and p(2) might have values you *can* write down. I'm not sure how you leverage this to produce a bias, but it certainly shows that FP arithmetic just plain doesn't have the right properties to support the reasoning behind Shamir secret sharing....

                                                        -- Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to