Proof: $H(K|C) \geq H(P|C)$

To prove this, let's define the following terms:

• $K$: the random variable representing the key.
• $P$: the random variable representing the plaintext.
• $C$: the random variable representing the ciphertext.
• $H(X|Y)$: the conditional entropy of $X$ given $Y$, which quantifies the uncertainty of $X$ given knowledge of $Y$.

Step 1: Using the Chain Rule for Entropy

The chain rule for joint entropy states:

$H(K, P | C) = H(K | C) + H(P | K, C)$

Since knowing the key $K$ and the ciphertext $C$ fully determines the plaintext $P$ (due to the deterministic nature of decryption in any cryptosystem), we have:

$H(P | K, C) = 0$

Thus, the equation simplifies to:

$H(K, P | C) = H(K | C)$

Step 2: Relating to $H(P | C)$

On the other hand, we can use the chain rule again for the joint entropy of $P$ and $K$:

$H(K, P | C) = H(P | C) + H(K | P, C)$

Since knowing both $P$ and $C$ reveals nothing more about the key (because we already know the plaintext and ciphertext), it follows that:

$H(K | P, C) = 0$

Thus, we have:

$H(K, P | C) = H(P | C)$

Step 3: Comparing Both Results

From the previous steps, we now have two expressions for $H(K, P | C)$:

1. $H(K, P | C) = H(K | C)$
2. $H(K, P | C) = H(P | C)$

Thus:

$H(K | C) = H(P | C) + H(K | P, C)$

Since $H(K | P, C) \geq 0$, this implies:

$H(K | C) \geq H(P | C)$

Step 4: Condition for Equality

Equality holds when $H(K | P, C) = 0$, which means that knowing the plaintext $P$ and the ciphertext $C$ fully determines the key $K$. This is the case in a perfect cryptosystem, where every ciphertext corresponds to exactly one key and plaintext pair. In such systems, given the plaintext and the ciphertext, the key can be uniquely determined, leading to $H(K | P, C) = 0$.

Thus, the condition for equality is that the cryptosystem is perfect in the sense that:

• Every ciphertext uniquely determines the corresponding plaintext-key pair.

Conclusion:

$H(K | C) \geq H(P | C)$ with equality holding if and only if the cryptosystem is perfect and the key can be determined from the plaintext and ciphertext.

---

Would you like further details on any part of this explanation or any questions?

Here are some related questions for deeper understanding:

1. What is conditional entropy, and how is it used in cryptography?
2. Can you explain the concept of perfect secrecy in cryptosystems?
3. How does the chain rule for entropy help in analyzing cryptographic security?
4. What are some real-world examples of perfect cryptosystems?
5. Why is $H(K|C) \geq H(P|C)$ a fundamental property of secure cryptosystems?

Tip: In cryptography, understanding entropy and its conditional variants is key to grasping the security guarantees provided by cryptographic protocols.