Question about Shamir secret sharing scheme
Hal Finney
hal at finney.org
Sat Oct 3 16:02:58 EDT 2009
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 at metzdowd.com
More information about the cryptography
mailing list