There was a question on my final exam, but I could not get a point. I really want to know the right answer.
Suppose a cryptosystem has perfect secrecy. Prove that H(P|C) = H(P)
H(P|C) is conditional entropy.
Mathematically, this is expressed as H(P)=H(P|C), where H(P) is the entropy of the plaintext and H(P|C) is the conditional entropy of the plaintext given the ciphertext C. This implies that for every message P and corresponding ciphertext C, there must be at least one key K that binds them. Mathematically speaking, this means |K| >=|C| >= |P|. In other words, if I need to be able to go from any plaintext in message space P to any cipher in cipher-space C (encryption) and from any cipher in cipher-space C to a plain text in message space P (decryption), I need at least|P|=|C| keys (all keys used with equal probability of 1/|K|to ensure perfect secrecy).