[144934] in cryptography@c2.net mail archive

home help back first fref pref prev next nref lref last post

Re: Question about Shamir secret sharing scheme

daemon@ATHENA.MIT.EDU (Jonathan Katz)
Mon Oct 5 22:56:46 2009

Date: Mon, 5 Oct 2009 12:43:03 -0400 (EDT)
From: Jonathan Katz <jkatz@cs.umd.edu>
To: "Kevin W. Wall" <kevin.w.wall@gmail.com>
cc: cryptography@metzdowd.com
In-Reply-To: <4AC6F246.5060907@gmail.com>

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

---559023410-851401618-1254760983=:3767
Content-Type: TEXT/PLAIN; charset=UTF-8; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Sat, 3 Oct 2009, 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 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 wish=
es
>    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 definin=
g the random
>            polynomial over Zp.
>        (c) T computes Si =3D f(i) mod p, 1 =E2=89=A4 i =E2=89=A4 n (or fo=
r any n distinct
>            points i, 1 =E2=89=A4 i =E2=89=A4 p =E2=88=92 1), and securely=
 transfers the 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 ?

Just to add two comments to what others have already said:
- You can use any finite field. In particular, if your secret is a bit=20
string of length k you can use the field GF(2^k) to get share size equal=20
to secret size. (Whereas if you work mod p you lose a bit.)

- As you describe the scheme above, note that you actually leak an=20
upper-bound on the size of the secret (namely, it is at most p). The setup=
=20
for Shamir secret sharing (and any other scheme, for that matter) assumes=
=20
the range of the secret is public knowledge already.
---559023410-851401618-1254760983=:3767--

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

home help back first fref pref prev next nref lref last post