There was a question on my final exam, but I could not get a point. I really want to know the right answer.
Question is:
Suppose a cryptosystem has perfect secrecy. Prove that H(P|C) = H(P)
H(P|C) is conditional entropy.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Which definition of perfect secrecy did you learn? $\endgroup$– SEJPMCommented Jul 29, 2018 at 17:23
-
$\begingroup$ We learnt: A cryptosystem has perfect secrecy if the ciphertext provides no information about the plaintext, i.e., Pr[P = p j C = c] = Pr[P = p] for all p E P, c E C. Examples: The Shift Cipher has perfect secrecy if it is used for a single-character message, and each key is equally probable. More generally, the Vernam and Vigenere ciphers have perfect secrecy if the key is as long as the message, and each key is equally probable and Shanon's Theorem. $\endgroup$– M.J.WatsonCommented Jul 29, 2018 at 19:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).