[144921] in cryptography@c2.net mail archive
Re: Question about Shamir secret sharing scheme
daemon@ATHENA.MIT.EDU (David-Sarah Hopwood)
Sun Oct 4 16:45:21 2009
Date: Sun, 04 Oct 2009 00:05:08 +0100
From: David-Sarah Hopwood <david-sarah@jacaranda.org>
To: cryptography@metzdowd.com
In-Reply-To: <4AC6F246.5060907@gmail.com>
Kevin W. Wall wrote:
> Hi list...I have a question about Shamir's secret sharing.
>=20
> According to the _Handbook of Applied Cryptography_
> Shamir=E2=80=99s secret sharing (t,n) threshold scheme works as follows=
:
>=20
> SUMMARY: a trusted party distributes shares of a secret S to n user=
s.
> RESULT: any group of t users which pool their shares can recover S.=
>=20
> The trusted party T begins with a secret integer S =E2=89=A5 0 it w=
ishes
> 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 defi=
ning 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 distinct
> points i, 1 =E2=89=A4 i =E2=89=A4 p =E2=88=92 1), and secur=
ely transfers the share Si
> to user Pi , along with public index i.
>=20
> 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).
>=20
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?
Yes, the information-theoretic security of the scheme depends on
performing the arithmetic in a finite field, and on the coefficients
being chosen randomly and independently in that field. In Shamir's
original paper:
<http://www.caip.rutgers.edu/~virajb/readinglist/shamirturing.pdf>
the statement that "By construction, these p possible polynomials
are equally likely" depends on these conditions. I believe any finite
field will work, but Zp is the simplest option.
[Incidentally, if you're implementing this from Handbook of Applied
Cryptography, there's an erratum for that section (12.71):
"of degree at most t" in the paragraph after the Mechanism should be
"of degree less than t".]
--=20
David-Sarah Hopwood =E2=9A=A5 http://davidsarah.livejournal.com
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
