Shamir secret sharing and information theoretic security

Jerry Leichter leichter at lrw.com
Sun Feb 22 14:37:13 EST 2009


On Feb 17, 2009, at 6:03 PM, R.A. Hettinga wrote:

> Begin forwarded message:
>
> From: Sarad AV <jtrjtrjtr2001 at yahoo.com>
> Date: February 17, 2009 9:51:09 AM EST
> To: cypherpunks at 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
It is.  Knowing some of the coefficients, or some constraints on some  
of the coefficients, is just dual to knowing some of the points.   
Neither affects the security of the system, because the coefficients  
*aren't secrets* any more than the values of f() at particular points  
are.  They are *shares* of secrets, and the security claim is that  
without enough shares, you have no information about the remaining  
shares.

The argument for information-theoretic security is straightforward:   
An n'th degree polynomial is uniquely specified if you know its value  
at n+1 points - or, dually, if you know n+1 coefficients.  On the  
other hand, *any* set of n+1 points (equivalently, any set of n+1  
coefficients) corresponds to a polynomial.  Taking a simple approach  
where the secret is the value of the polynomial at 0, given v_1,  
v_2, ..., v_n and *any* value v, there is a (unique) polynomial of  
degree at most n with p(0) = v and p(i) = v_i for i from 1 to n.   
Dually, the value p(0) is exactly the constant term in the  
polynomial.  Given any fixed set of values c_1, c_2, ..., c_n, and any  
other value c there is obviously a polynomial p(x) = Sum_{0 to n}(c_i  
x^i), where c_0 = c, and indeed p(0) = c.

Or ... in terms of your problem:  Even if I give you, not just a pair  
of linear equations in c1, c2, and S, but the actual values c1 and c2  
- the constant term (the secret) can still be anything at all.

The description above is nominally for polynomials over the reals.  It  
works equally for polynomials over any field - like the integers mod  
some prime, for example.  For a finite field, there is an obvious  
interpretation of probability (the uniform probability distribution),  
and given that, "no information" can be interpreted in terms of the  
difference between your a priori and a posterio estimates of the  
probability that p(0) takes on any particular value, the values of  
p(1), ..., p(n) (and that differences is exactly 0).  Because there  
can be no uniform probability distribution over all the reals, you  
can't state things in quite the same way, and "information theoretic  
security" is a bit of a vague notion.  Then again, no one does  
computations over the reals.  FP values - say, IEEE single precision -  
aren't a field and there are undoubtedly big biases if you try to use  
Shamir's technique there.  (It should work over infinite-precision  
rationals.)

                                                         -- Jerry


>
>
> 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 at metzdowd.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list