Question about Shamir secret sharing scheme

[Victor Duchovni]

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