Question about Shamir secret sharing scheme

[Jonathan Katz]

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.