[144936] in cryptography@c2.net mail archive
Re: Question about Shamir secret sharing scheme
daemon@ATHENA.MIT.EDU (Victor Duchovni)
Mon Oct 5 22:58:16 2009
Date: Mon, 5 Oct 2009 15:27:15 -0400
From: Victor Duchovni <Victor.Duchovni@morganstanley.com>
To: cryptography@metzdowd.com
Mail-Followup-To: cryptography@metzdowd.com
In-Reply-To: <ed843b100910041644p41a60e5ch11514358b179909f@mail.gmail.com>
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@metzdowd.com
