1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Which definition of perfect secrecy did you learn? $\endgroup$ – SEJPM Jul 29 '18 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.Watson Jul 29 '18 at 19:26
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.