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.