double encryption - One Time Pad Can the security of the encryption system be improved by using double encryption with two randomly chosen keys?

By double encryption I mean using two keys K1 and K2, each 20-bit long, to obtain ciphertext $C = ( M ⊕ K_1 ) ⊕ K_2$.
The answer is we cannot improve the security of the one-time pad in this manner. Intuitively the reason is that the double one-time pad is just a less efficient one time pad.

The security of the traditional xor-based one-time pad is requires that the key $K$ is chosen uniformly at random for each message and that the key is at least as large as the message.

Because the xor operation is associative, we could re-write the double one-time pad as $C = M \oplus(K_1 \oplus K_2)$ or $ C = M \oplus K$, where $K = K_1 \oplus K_2$. Now if $K_1$ and $K_2$ are uniform, it is easy to show that $K$ is also uniform. Assuming the key and the message have length $n$

$P_K[k] = \sum_{x \in \{0,1\}^n}P_{K_1,K_2}[k_1 = x, k_2 = k \oplus k_1] = \frac{1}{2^n}$

In other words $K_1 \oplus K_2$ could be simply replaced by a single uniform key, therefore $K_1$ is enough. Moreover the double one-time pad is inefficient because it requires two xor operations.



Regarding cascade encryption, Maurer and Massey showed that cascade encryption is as strong as the first cipher. Matthew Green's blog post is a nice (easy to read) summary of multi-encryption security.