On Sat, Oct 03, 2009 at 02:42:14AM -0400, Kevin W. Wall wrote: > 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 ? The only reason that we can see to doing this is to > keep the sizes of the shares Si bounded within some reasonable range > and it seems as though one could just do something like allowing T > choose random coefficients from a sufficient # of bytes and just > do all the calculations without the 'mod p' stuff.
Lagrange interpolation works for polynomials over a field. The most convenient *finite* fields in this context are the Z_p for prime p. In this context it is also easy to make a uniform choice of a random coefficient and to quantify the work-factor for a brute-force attack. With rationals, everything is much messier. There is no good reason to work over Q. > We thought perhaps > Shamir did the calculations of Zp because things like Java's BigInteger > or BigDecimal weren't widely available when came up with this > scheme back in 1979. An algorithm is not the same an implementation. There was no Java back then either, and people still somehow wrote working code in '79. -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAIL Morgan Stanley confidentiality or privilege, and use is prohibited. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com