[144926] in cryptography@c2.net mail archive
Re: Question about Shamir secret sharing scheme
daemon@ATHENA.MIT.EDU ("Hal Finney")
Sun Oct 4 16:48:56 2009
To: cryptography@metzdowd.com, kevin.w.wall@gmail.com
Date: Sat, 3 Oct 2009 13:02:58 -0700 (PDT)
From: hal@finney.org ("Hal Finney")
Kevin W. Wall asks about Shamir sharing:
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?
Yes, you do have to be careful to do that. You want to make sure the
shares don't leak any information about the secret S.
Consider the simplest case where two people are involved. Call the single
random coefficient c, with secret S, then the two shares are:
S + c
S + 2c
Now if this is mod p, and c is chosen at random mod p, then both c and
2c will be random mod p, and each perfectly hides the value of S when
it is added mod p, similarly to a one-time-pad. Neither share leaks any
information about the value of S.
But suppose for convenience you did the math mod some power of 2 (or
even just over the integers). Then 2c is going to be even, regardless
of c. And seeing S + 2c will then reveal whether S is even or odd,
defeating the privacy of the scheme.
Hal Finney
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
