Cryptography Reference
In-Depth Information
I want to show you at least one such secret sharing method in this section.
You know that a square polynomial (corresponding to a parabola) is defined
by its values at three different points. Two points are not sufficient, because
there are infinitely many parabolas that traverse these points. The same applies
to residual classes. From this we construct a
polynomial method
[Shamshare]:
Let your secret message be a number,
M
. Choose a non-secret large prime
number,
p
, which is greater than all secret messages and their subsets. Define
arbitrarily two integer coefficients,
a
and
b
. Take the polynomial
ax
2
+bx+M
and compute the values for
x
1,2,3,4,5 and distribute their remainders mod-
ulo
p
among your five partners, who also have to know
p
. You can forget the
values of
a
and
b
forever. No two of your partners will even theoretically be
able to determine
M
from their pieces of information, while any three of them,
in contrast, need to solve only a linear equation system in the residual class
modulo
p
. This is not excessively hard.
=
By computing in residual classes, by the way, all messages
M
become possible
only with two known subsets of the secret. This means that the method is
provably secure!
If your secret is several Mbytes long, you can encrypt it using a random session
key and then distribute this key by the secret sharing method.
Unfortunately, the protocol described above is still vulnerable to denial-of-
service attacks: if one partner cheats as the secret is reconstructed, then a
wrong secret is created, and what's more, the cheater cannot be identified.
The problem can be solved by using
robust secret-sharing protocols
, which
work with zero-knowledge proofs. You can find details about this protocol in
[SchnCr, 3.7] and [Gemmel].
There is a more general secret sharing method. For example, you could demand
that among three partners who can reconstruct the secret, one out of two must
always be particularly trustworthy. Or two of the participants should be fierce
enemies. (You could make a list of corresponding pairs.) Arbitrary logical
schemes are conceivable, and intensive research has been done in this field
since 1979. You can find more theory in [Shamshare], [Stins], and [Blakshar;
with further references] and in [SchnCr, 3.7].
