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.`