Question about Shamir secret sharing scheme

[David-Sarah Hopwood]

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 ?

Yes, the information-theoretic security of the scheme depends on
performing the arithmetic in a finite field, and on the coefficients
being chosen randomly and independently in that field. In Shamir's
original paper:

<http://www.caip.rutgers.edu/~virajb/readinglist/shamirturing.pdf>

the statement that "By construction, these p possible polynomials
are equally likely" depends on these conditions. I believe any finite
field will work, but Zp is the simplest option.

[Incidentally, if you're implementing this from Handbook of Applied
Cryptography, there's an erratum for that section (12.71):
"of degree at most t" in the paragraph after the Mechanism should be
"of degree less than t".]

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com