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 majord...@metzdowd.com