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’s 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 ≥ 0 it wishes
   to distribute among n users.
       (a) T chooses a prime p > max(S, n), and defines a0 = S.
       (b) T selects t−1 random, independent coefficients defining the random
           polynomial over Zp.
       (c) T computes Si = f(i) mod p, 1 ≤ i ≤ n (or for any n distinct
           points i, 1 ≤ i ≤ p − 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 string of length k you can use the field GF(2^k) to get share size equal 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 upper-bound on the size of the secret (namely, it is at most p). The setup for Shamir secret sharing (and any other scheme, for that matter) assumes the range of the secret is public knowledge already.

Reply via email to