Exercise 5.4 (Entropy of the key) Show that, in any cryptosystem, it holds
that H(K|C) >= H(P|C). Under which condition do we have equality?

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

Exercise 5.4 (Entropy of the key) Show that, in any cryptosystem, it holds that H(K|C) >= H(P|C). Under which condition do we have equality?

Understand the proof that in any cryptosystem, H(K|C) >= H(P|C), and explore the conditions under which equality holds. This problem involves the chain rule for entropy and conditional entropy, suitable for university-level cryptography courses.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation