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
