[144925] in cryptography@c2.net mail archive
Re: Question about Shamir secret sharing scheme
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Sun Oct 4 16:47:55 2009
Cc: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
To: Kevin W. Wall <kevin.w.wall@gmail.com>
In-Reply-To: <4AC6F246.5060907@gmail.com>
Date: Sat, 3 Oct 2009 23:51:16 -0400
On Oct 3, 2009, at 2:42 AM, Kevin W. Wall wrote:
> Hi list...I have a question about Shamir's secret sharing.
>
> According to the _Handbook of Applied Cryptography_
> Shamir=E2=80=99s secret sharing (t,n) threshold scheme works as =
follows:
>
> SUMMARY: a trusted party distributes shares of a secret S to n =20
> users.
> RESULT: any group of t users which pool their shares can recover S.
>
> The trusted party T begins with a secret integer S =E2=89=A5 0 it =
wishes
> to distribute among n users.
> (a) T chooses a prime p > max(S, n), and defines a0 =3D S.
> (b) T selects t=E2=88=921 random, independent coefficients =
defining =20
> the random
> polynomial over Zp.
> (c) T computes Si =3D f(i) mod p, 1 =E2=89=A4 i =E2=89=A4 n (or =
for any n =20
> distinct
> points i, 1 =E2=89=A4 i =E2=89=A4 p =E2=88=92 1), and =
securely transfers the =20
> share Si
> to user Pi , along with public index i.
>
> The secret S can then be computed by finding f(0) more or less by
> using Lagrangian interpolation on the t shares, the points (i, Si).
>
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ? The only reason that we can see to doing this is to
> keep the sizes of the shares Si bounded within some reasonable range
> and it seems as though one could just do something like allowing T
> choose random coefficients from a sufficient # of bytes and just
> do all the calculations without the 'mod p' stuff. We thought perhaps
> Shamir did the calculations of Zp because things like Java's =20
> BigInteger
> or BigDecimal weren't widely available when came up with this
> scheme back in 1979.
>
> So other than perhaps compatibility with other implementations (which
> we are not really too concerned about) is there any reason to continue
> to do the calculations over Zp ???
It's nice to be able to give a size limit for the shares. They're =20
going to need to be transmitted and stored. Since there are many =20
primes around, working over Zp ensures that shares about about the =20
same size as the secret.
However, there's also a more fundamental problem: In step (b), how do =20=
you choose your coefficients randomly over all of Z? There is no =20
uniform probability distribution over Z to work with. Any realistic =20
implementation will choose from some finite subset. But then the =20
scheme may not be completely secure: If you have the value of f() at =20=
t-1 points, the fact that the coefficients are limited to some finite =20=
set also constrains the possible values at the remaining point - and =20
you don't know exactly how. Working over Zp's group structure ensures =20=
that if you have t-1 values, all p-1 possible remaining values are =20
equally likely, so you've learned nothing.
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
