An old man, with four sons and three daughters, buried a safebox with valuables inside. He wanted his children to get it when he died, but neither the boys nor the girls to get it all for themselves; he desired that at least two sons and two daughters had to be involved in order to find the missing treasure.
(For example, the three girls on their own couldn't find the treasure, even if one boy helped them. The four boys and one girl couldn't find it either.)
How could he manage this?
For each of his sons and daughters he creates a long random integer to be used as a "key". So there will be 4 keys for his 4 sons, and 3 keys for his 3 daughters. Let's call the keys that he gives his sons SK1 through SK4. And the keys for his daughters are DK1 through DK3.
Now, he XOR's together SK1 through SK4 and uses the result as the "first encryption key" to encrypt the instructions to recover the buried treasure giving him an "intermediate result." Similarly he XORs DK1 through DK3 to get the "second encryption key" and uses that to encrypt the intermediate result to obtain the "final encrypted text." (This is symmetric encryption, so the same key that encrypts is used to decrypt.)
For the sons, he creates the following composite keys:
1. SK1 xor SK2
2. SK1 xor SK3
3. SK1 xor SK4
4. SK2 xor SK3
5. SK2 xor SK4
6. SK3 xor SK4
which is all possible combinations of any two of the four SK keys.
To the 1st son, he gives the key SK1 and the three composite keys that don't include SK1 (4, 5, and 6, above).
To the 2nd son, he gives the key SK2 and the three composite keys that don't include SK2 (2, 3, and 6, above).
Similarly for his 3rd and 4th sons.
For his daughters, it's much simpler.
He gives his 1st daughter DK2 and DK3.
He gives his 2nd daughter DK1 and DK3.
He gives his 3rd daughter DK1 and DK2.
He also gives everyone the encryption/decryption algorithm that he used, the final encrypted text, and a detailed record of exactly what he did to create it.
Now, here's how the sons and daughters proceed, and why it takes at least 2 of each to decrypt his instructions:
We'll start with the daughters. To get the 2nd decryption key they need all 3 DK keys. No single daughter has all 3 DK keys, but any two of them do. They xor all three DK keys together to create the 2nd encryption key and use it to decrypt the final encrypted text and recover the intermediate result. This, they give to the sons.
For the sons, first of all, notice that there's nothing any ONE of them can do, with the single key and 3 composites that he has, to get all 4 of the SK keys, or more importantly, the decryption key (SK1 xor SK2 xor SK3 xor SK4).
Let's consider any two of them, say 2 and 4. (By symmetry, the same method would work with any two.)
They would xor all the following together:
SK2 (from son 2), SK4 (from son 4) and composite key 2 (SK1 xor SK3) from either son 2 or 4...they both received this composite.
This gives them the 1st encryption key, which they use to decrypt the intermediate result and retrieve the original plain-text instructions.
Edited on July 17, 2005, 6:00 am
Edited on July 17, 2005, 6:02 am
Using Symmetric Encryption
