How to prove a symmetric encryption scheme provides perfect secrecy?

Question

I learned in class that in order to achieve perfect secrecy, the source of the plaintext $\mathcal{P}$ needs to be independent from the source of the encryption key $\mathcal{K}$. We also learned that this is always the case for independent sources: $H(\mathcal{P}) \le H(\mathcal{K})$, but that it shouldn't be used as an exhaustive proof, because in the case where you have a high-entropy key but it is badly designed (such as having different lengths for each code word), you could still derive a lot of information from attempted decryption.

We saw an example where someone used a coin to determine a random key composed of 16 bits to mask a plaintext composed of 4 digits coded into 4 bits each (using xor logic). In this case, $H(\mathcal{P}) = 13.2877$ (there are 10000 possible combinations of digits), and $H(\mathcal{K}) = 16$, so the inequality holds.

Suppose now that 8 bits of the key are generated randomly, and then just copied over for the remaining 8 bits. The key source and the plaintext source now become dependent, however only if the "hacker" knows that the key was copied twice over (because it is technically a possible outcome). The inequality doesn't hold anymore either because $H(\mathcal{K}) = 8$. I'm assuming that this encryption scheme fails to provide perfect secrecy, but I remain unconvinced because of my previous argument of the conditional state of this "copied" key. In this case, is there a better way to provide a proof other than the two methods mentioned above?

Answer 1

Xor-ing the first half of the encrypted message with the second gives the same result as xor-ing the first and second half of the original message. (When the key is duplicated). This contradicts perfect secrecy as some information can be obtained from the cyphertext.

Answer 2

Jean-François Gagnon's answer is fine and would serve as an obvious proof that this scheme does not provide perfect secrecy.

Now the fault in your thought process is actually that an attacker doesn't know that the key is "copied". This is a simple form of a key schedule which is assumed to be known to the attacker along with the encryption and decryption routines (commonly called $\operatorname{GenKey()}$). If you assume that the key schedule is part of the secret key, then cryptanalysis of any cipher gets extremely hard and in fact you could proof the many-time pad (with the key $1$) perfectly secure as "an attacker has no way to know we always used $1$ as key bit".