Question about Shamir secret sharing scheme
Jonathan Katz
jkatz at cs.umd.edu
Mon Oct 5 12:43:03 EDT 2009
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.
More information about the cryptography
mailing list