[144272] in cryptography@c2.net mail archive
Re: Shamir secret sharing and information theoretic security
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Mon Feb 23 15:02:28 2009
From: Jerry Leichter <leichter@lrw.com>
To: sbg@acw.com
In-Reply-To: <3477.70.116.23.89.1235412347.squirrel@www.acw.com>
Date: Mon, 23 Feb 2009 14:03:01 -0500
Cc: "R.A. Hettinga" <rah@shipwright.com>,
"Cryptography" <cryptography@metzdowd.com>
On Feb 23, 2009, at 1:05 PM, sbg@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 =20
> setting
> depends on the finite precision implementation?
>
> For example, if you know 2 of a 3 of 5 splitting and you also know =20
> that
> the finite precision setting in which the fragments will be used is =20=
> IEEE
> 32-bit floating point or GNU bignum can you narrow down the search =20
> 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 =20
exact values, FP arithmetic is very messy and has almost no nice =20
mathematical properties. (It's nice in a model where all you care =20
about is relative error - which is actually a rather unnatural =20
model!) As a result, I think it's unlikely you can come up with any =20
general theory here. But you can probably come up with examples =20
showing that there's a problem. It's usually easiest to work with a =20
simpler form of FP math - e.g., assume 4 decimal digits and a 1-digit =20=
decimal exponent. Consider just quadratics, which we can write as
p(x) =3D (x - r1)*(x - r2). If r1*r2 overflows in a particular FP =20
system, you can't write down the value of the constant coefficient - =20
hence, you can't write down the value p(0). Yet p(1) and p(2) might =20
have values you *can* write down. I'm not sure how you leverage this =20=
to produce a bias, but it certainly shows that FP arithmetic just =20
plain doesn't have the right properties to support the reasoning =20
behind Shamir secret sharing....
-- Jerry=10
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
