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