Sharing a secret

I will give a simple example of Shamir secret sharing.  Suppose you have
some data D which you want to split up into n pieces such that any 2
of them are sufficient to reconstruct D.  Shamir solves the problem for
any k of them being sufficient, but the case k=2 is especially simple.

Pick a random number m which will be the slope of a line.  Take the
equation y = mx + D, and substitute x = 1, x = 2, ... x = n.  Pass out
the y's for each value of x as the secret shares.

For example, if D=12, pick random m = 4, and pass out (1,16), (2,20),
(3,24), (4,28), and so on.

Now, suppose an enemy gets hold of one of these - say (2,20).  What does
this tell him about the value of D?  Nothing!  D could be anything,
depending on the value of m.

But suppose we have two of these values - say (1,16) and (2,20).  From
these it is easy to calculate m=4, and from that it is easy to see that
D=12.  Two points determine a line.

In the actual Shamir scheme, integers mod a prime p are used, where p>D.
The math is basically the same.  For k=3, a parabola is used instead of
a line, so that 3 points are needed; for k=4, a third-degree polynomial
is used, and for general k, a (k-1)-degree polynomial is used.  In each
case, knowing k-1 points tells you nothing, because there will be a
(k-1)-degree polynomial that would pass through any possible value of
D.

Hal

David Koontz <koontzd@lrcs.loral.com> writes:

> With a key K of size j (goddamn fortran anyway), i parties can share
> the secret with a threshold of i (requiring all i parties key part)
> by generating i parts P such that K = Pi XOR Pi-1 XOR ... P1.  All
> the parts P are the same size as K, which keeps the effort of guessing
> a missing part equal to j, or the size of the key k itself. 
>
> Such a scheme is not ideal for keys K that have a deterministic
> characteristic.

I might be missing something, but I don't see how this could be made to
work when you're missing more than one key.  For example, suppose you
create a system with 5 keys.  Take each of the five keys and XOR them to
create a known constant.  Now, if you have four keys, you can easily
find the fifth by xoring them with the known constant, and unlock the
cipher.  But, what if you wanted to have three of the five keys be able
to unlock the cipher.  There isn't any way to do this.

I worked with this system many years ago, trying to create an insurance
against data loss.  If you have some blocks of data, you take each byte
in each block and xor it with the same byte position in all of the other
blocks, and then save this new block that you created.  If you then lose
one of the blocks, you can recreate it from the remaining blocks.  But
if you lost two blocks, there is no way to recreate it.  I gave up on
the idea and never wrote the program.

I like the line/polynomial idea that Hal Finney posted tho...