From: norm@netcom.com (Norman Hardy)
Date: Sun, 5 Sep 93 08:46:00 PDT
To: sameer@netcom.com
Subject: Remailer Reliability
Message-ID: <9309051539.AA01918@netcom4.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


sameer@netcom.com (Sameer Parekh) says:
 
> 	Didn't someone mention a while back a scheme by which a
> message can be split up into a bunch of parts and only requires about
> 50% of them or so to be completely rebuilt? Something like that would
> be very useful I think to deal with remailer reliability problems.
> That would require a good deal more user work though.
 
There was a paper sometime back (10 years I would guess) called
"Sharing Secrets". For any j and k such that 0<j<k you could arrange
that the secret was divided into k parts, any j of which sufficed
to reconstruct the secret. Each part was the size of the secret.
Any collection of less than k parts yielded absolutly no information
even with exhaustive search.
 
If I have a third degree real polynomial y=f(x) and have computed y for
six different values of x then the polynomial can be resonstituted
from knowing any four of those <x, y> pairs. The secret was the
value of f(x) for yet another public value of x. The paper described
how to do this in finite fields.