Question about Shamir secret sharing scheme
Victor Duchovni
Victor.Duchovni at morganstanley.com
Sat Oct 3 16:52:48 EDT 2009
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 majordomo at metzdowd.com
More information about the cryptography
mailing list