Shamir secret sharing and information theoretic security
Jerry Leichter
leichter at lrw.com
Mon Feb 23 14:03:01 EST 2009
On Feb 23, 2009, at 1:05 PM, sbg at 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 majordomo at metzdowd.com
More information about the cryptography
mailing list