Question about Shamir secret sharing scheme

Victor Duchovni Victor.Duchovni at morganstanley.com
Mon Oct 5 15:27:15 EDT 2009


On Sun, Oct 04, 2009 at 05:44:37PM -0600, Matt Ball wrote:

> > The question that a colleague and I have is there any cryptographic
> > purpose of computing the independent coefficients over the finite
> > field, Zp ?
> 
> Here is a concrete example of information leakage when not using Zp.
> 

When using a finite subset of a totally ordered coefficient field
(such as Q) whose "+" operator is order preserving (a < b => a + c < b + c
for all c), we always see some outputs leaking more information
than others. This covers any subsets of Z as Z is a subset of Q.

A finite subset of such a field always has a minimal element.

For example, if all the coefficients happen to be equal to the least
possible coefficient, the person with share "1" easily concludes that
he has the least possible sum, and recovers the secret coefficients.

Using infinite subsets means unbounded storage requirements for the
coefficients, and necessarily a non-uniform distribution of coefficients,
with some polynomials more probable than others, so again data leakage.

Leaking no information is only possible in a finite field, of which the
Z_p are the "simplest", but (as pointed out upthread) Galois extensions
of Z_2 are typically more convenient computationally.

-- 

 /"\ 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