From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Fri, 22 Oct 93 13:33:18 PDT
To: cypherpunks@toad.com
Subject: Re: Sharing a secret
In-Reply-To: <9310221637.AA01633@jobe.shell.portal.com>
Message-ID: <Mgm49j600VpQIGoUc0@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


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...