Shamir secret sharing and information theoretic security

[Jerry Leichter]

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