Question about Shamir secret sharing scheme

[Jerry Leichter]

On Oct 3, 2009, at 2:42 AM, 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 ?  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. 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.
>
> So other than perhaps compatibility with other implementations (which
> we are not really too concerned about) is there any reason to continue
> to do the calculations over Zp ???
It's nice to be able to give a size limit for the shares.  They're  
going to need to be transmitted and stored.  Since there are many  
primes around, working over Zp ensures that shares about about the  
same size as the secret.

However, there's also a more fundamental problem:  In step (b), how do  
you choose your coefficients randomly over all of Z?  There is no  
uniform probability distribution over Z to work with.  Any realistic  
implementation will choose from some finite subset.  But then the  
scheme may not be completely secure:  If you have the value of f() at  
t-1 points, the fact that the coefficients are limited to some finite  
set also constrains the possible values at the remaining point - and  
you don't know exactly how.  Working over Zp's group structure ensures  
that if you have t-1 values, all p-1 possible remaining values are  
equally likely, so you've learned nothing.

                                                         -- Jerry

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