[144265] in cryptography@c2.net mail archive
Re: Shamir secret sharing and information theoretic security
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Mon Feb 23 11:24:02 2009
Cc: Cryptography <cryptography@metzdowd.com>
From: Jerry Leichter <leichter@lrw.com>
To: R.A. Hettinga <rah@shipwright.com>
In-Reply-To: <A7C20848-F70F-417C-ACA4-A59A81E0F02C@shipwright.com>
Date: Sun, 22 Feb 2009 14:37:13 -0500
On Feb 17, 2009, at 6:03 PM, R.A. Hettinga wrote:
> Begin forwarded message:
>
> From: Sarad AV <jtrjtrjtr2001@yahoo.com>
> Date: February 17, 2009 9:51:09 AM EST
> To: cypherpunks@al-qaeda.net
> Subject: Shamir secret sharing and information theoretic security
>
> hi,
>
>
> I was going through the wikipedia example of shamir secret sharing =20
> which says it is information theoretically secure.
>
> http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
>
> In the example in that url, they have a polynomial
> f(x) =3D 1234 + 166.x + 94.x^2
>
> they construct 6 points from the polynomial
> (1,1494);(2,1942);(3,2578);(4,3402);(5,4414);(6,5615)
>
> the secret here is S=3D1234. The threshold k=3D3 and the number of =20
> participants n=3D6.
>
> If say, first two users collude then
> 1494 =3D S + c1 .1 + c2.1
> 1942 =3D S + c1 .2 + c2.2
>
> clearly, one can start making inferences about the sizes of the =20
> unknown co-efficients c1 and c2 and S.
>
>
> However, it is said in the URL above that Shamir secret is =20
> information theoretically secure
It is. Knowing some of the coefficients, or some constraints on some =20=
of the coefficients, is just dual to knowing some of the points. =20
Neither affects the security of the system, because the coefficients =20
*aren't secrets* any more than the values of f() at particular points =20=
are. They are *shares* of secrets, and the security claim is that =20
without enough shares, you have no information about the remaining =20
shares.
The argument for information-theoretic security is straightforward: =20
An n'th degree polynomial is uniquely specified if you know its value =20=
at n+1 points - or, dually, if you know n+1 coefficients. On the =20
other hand, *any* set of n+1 points (equivalently, any set of n+1 =20
coefficients) corresponds to a polynomial. Taking a simple approach =20
where the secret is the value of the polynomial at 0, given v_1, =20
v_2, ..., v_n and *any* value v, there is a (unique) polynomial of =20
degree at most n with p(0) =3D v and p(i) =3D v_i for i from 1 to n. =20=
Dually, the value p(0) is exactly the constant term in the =20
polynomial. Given any fixed set of values c_1, c_2, ..., c_n, and any =20=
other value c there is obviously a polynomial p(x) =3D Sum_{0 to n}(c_i =20=
x^i), where c_0 =3D c, and indeed p(0) =3D c.
Or ... in terms of your problem: Even if I give you, not just a pair =20=
of linear equations in c1, c2, and S, but the actual values c1 and c2 =20=
- the constant term (the secret) can still be anything at all.
The description above is nominally for polynomials over the reals. It =20=
works equally for polynomials over any field - like the integers mod =20
some prime, for example. For a finite field, there is an obvious =20
interpretation of probability (the uniform probability distribution), =20=
and given that, "no information" can be interpreted in terms of the =20
difference between your a priori and a posterio estimates of the =20
probability that p(0) takes on any particular value, the values of =20
p(1), ..., p(n) (and that differences is exactly 0). Because there =20
can be no uniform probability distribution over all the reals, you =20
can't state things in quite the same way, and "information theoretic =20
security" is a bit of a vague notion. Then again, no one does =20
computations over the reals. FP values - say, IEEE single precision - =20=
aren't a field and there are undoubtedly big biases if you try to use =20=
Shamir's technique there. (It should work over infinite-precision =20
rationals.)
-- Jerry=10
>
>
> in the url below they say
> http://en.wikipedia.org/wiki/Information_theoretic_security
> "Secret sharing schemes such as Shamir's are information =20
> theoretically secure (and in fact perfectly secure) in that less =20
> than the requisite number of shares of the secret provide no =20
> information about the secret."
>
> how can that be true? we already are able to make inferences.
>
> Moreover say that, we have 3 planes intersecting at a single point =20
> in euclidean space, where each plane is a secret share(Blakely's =20
> scheme). With 2 plane equations, we cannot find the point of =20
> intersection but we can certainly narrow down to the line where the =20=
> planes intersect. There is information loss about the secret.
>
>
> from this it appears that Shamir's secret sharing scheme leaks =20
> information from its shares but why is it then considered =20
> information theoretically secure?
>
> They do appear to leak information as similar to k-threshold schemes =20=
> using chinese remainder theorem.
>
> what am i missing?
>
> Thanks,
> Sarad.
>
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to =
majordomo@metzdowd.com
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
