How to require two keyholders to decrypt a document?

Question

I want to create a system to encrypt a document and store it with a 3rd party, but not have the 3rd party be able to decrypt it until some unspecified later date. It seems like the solution would be to split the key into two parts, given to two different trusted 3rd parties. Then when the date arrives those 3rd parties can come together to decrypt the document.

I realize that splitting a key effectively reduces the strength of the key in half for anyone who has half of the key.

1. Is splitting an AES key into two parts is an effective method of preventing either party from decrypting a document?
2. Is there a preferred method of splitting a key? Down the middle? Every other byte, etc.?
3. When splitting a key will one party have an advantage over the other party in a brute force attack? In other words, are certain parts of the key more important than others?

Answer 1

Splitting a key does not reduce the key strength at all. Simply generate two random 128-bit strings and give one to each party. Encrypt the data with the exclusive OR of the two random strings.

Each string alone gives no information whatsoever about the final key, assuming your random number generator is sound. No party has any advantage.

Answer 2

The usual method of "splitting a key" $K$ into two keys $K_0$ and $K_1$ given to two parties, for the purpose described, is as follows:

• generate $K_1$ randomly, of the same size as $K$;
• set $K_0 = K \oplus K_1$.

"Joining" $K_0$ and $K_1$ into $K$ is simply $K = K_0 \oplus K_1$.

This construct is such that each of the two parties gain absolutely no advantage by getting its split key $K_j$, unless it also gets the other; it just is random, and unrelated to $K$.

This can be generalized to $n>2$ parties that must all collaborate to reconstruct $K$:

• generate $K_1$ to $K_{n-1}$ randomly, of the same size as $K$;
• set $K_0 = K \oplus K_1 \oplus ..\oplus K_{n-1}$.

Of course joining is $K = K_0 \oplus K_1 \oplus ..\oplus K_{n-1}$.

This can further be generalized to $n$ parties of which at least $k$ must collaborate to reconstruct $K$, using Shamir secret sharing, or some other secret sharing scheme.

Answer 3

You seem to be assuming that you will take the key, and give half the key bits to each party. While this can be made to work, there are cleverer ways to do this:

• You can pick an N bit random number (where N is the length of the key), and give one side that random number, and the other that random number xor'ed with the key. That way, neither side has any information about the key, but if there get together, they can exclusive or their two shares (and recover the original key).

• More generally, you can employ a secret sharing method; this will allow you to create N shares (of which any T can be used to recover the secret). This extra flexibility can be useful if it is possible that not the parties will be available when it comes time to recover the key.

Now, to answer your specific questions:

• Splitting an AES key into two pieces (and giving half the bits to each party) does half the stength of the AES key against attack by either of those two parties. However, if you use a 256 bit AES key (and give 128 bits to each party), then each party would need to try $O(2^{128})$ guesses at the key bits he didn't get – that is practically secure.

• No, there is no preferred way to split the key

• No, as long as you give an equal number of key bits to each party, neither party will have an advantage.

Answer 4

One simple way would be to use Trivial secret sharing:

• Split DOCUMENT in half into DOCUMENT1 and DOCUMENT2.
• Choose BITS1 and BITS2 uniformly and independently at random from binary strings of length equal to the lengths of DOCUMENT1 and DOCUMENT2, respectively.
• Give BITS2 and (BITS1 xor DOCUMENT1) to not-quite-trusted 3rd party A, and BITS1 and (BITS2 xor DOCUMENT2) to not-quite-trusted 3rd party B.

This achieves information-theoretic security.

If you want to reduce the memory requirement (by slightly less than a factor of 1/2), you can replace all instances of "DOCUMENT","DOCUMENT1","DOCUMENT2" with "AES_KEY","AES_KEY1","AES_KEY2" respectively, and then split the encrypted document however you want between the 3rd parties.

This does not achieve information-theoretic security, but neither party has any more information than they would if they only had their part of the encrypted document.

For your questions:

1. No, for the reason you gave.

2. I believe any security difference would indicate a (slight) weakness in AES, so down the middle because that would probably be easiest.

3. In the first version, 3rd party A would have an advantage in exploiting any weakness in how you generated BITS1 to get information on DOCUMENT1, and 3rd party B would have an advantage in exploiting any weakness in how you generated BITS2 to get information on DOCUMENT2.

   In the second version, each party could brute force the cipher to recover its part of the document.