[144249] in cryptography@c2.net mail archive
Shamir secret sharing and information theoretic security
daemon@ATHENA.MIT.EDU (R.A. Hettinga)
Fri Feb 20 12:30:33 2009
From: "R.A. Hettinga" <rah@shipwright.com>
To: Cryptography <cryptography@metzdowd.com>
Date: Tue, 17 Feb 2009 18:03:07 -0500
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
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) = 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=1234. The threshold k=3 and the number of
participants n=6.
If say, first two users collude then
1494 = S + c1 .1 + c2.1
1942 = S + c1 .2 + c2.2
clearly, one can start making inferences about the sizes of the
unknown co-efficients c1 and c2 and S.
However, it is said in the URL above that Shamir secret is information
theoretically secure
in the url below they say
http://en.wikipedia.org/wiki/Information_theoretic_security
"Secret sharing schemes such as Shamir's are information theoretically
secure (and in fact perfectly secure) in that less than the requisite
number of shares of the secret provide no 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 in
euclidean space, where each plane is a secret share(Blakely's scheme).
With 2 plane equations, we cannot find the point of intersection but
we can certainly narrow down to the line where the planes intersect.
There is information loss about the secret.
from this it appears that Shamir's secret sharing scheme leaks
information from its shares but why is it then considered information
theoretically secure?
They do appear to leak information as similar to k-threshold schemes
using chinese remainder theorem.
what am i missing?
Thanks,
Sarad.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
