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.
