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 majord...@metzdowd.com