0
$\begingroup$

I am teaching undergrad computer security and look for a semi-formal way to make students understand the notion of a one-time pad (OTP). To this end, consider the following exercise:

Suppose you want to encrypt a message $M \in \{0, 1, 2\}$ using a shared random key $K \in \{0, 1, 2\}$. Suppose you do this by representing $K$ and $M$ using two bits (00, 01, or 10), and then XORing the two representations. Does this scheme have the same security guarantees of the one-time pad? Explain.

The idea here is to get student to write down and analyze the following table:

     K  |  M   | E(K,M)
  ------+------+--------
 1  00  |  00  |  00
 2  01  |  00  |  01
 3  10  |  00  |  10
    ----+------+----
 4  00  |  01  |  01
 5  01  |  01  |  00
 6  10  |  01  |  11
    ----+------+----
 7  00  |  10  |  10
 8  01  |  10  |  11
 9  10  |  10  |  00

Here, it becomes obvious that some outcomes exclude certain inputs. For example, given $E(K,M) = 11$ an attacker knows that the sent message $M$ is not 0. The way I would like to teach it to students uses conditional probability:

$$M\mid C = 00 \sim Unif\{0,1,2\}$$ Whereas: $$M\mid C = 11 \sim Unif\{1,2\}$$

Since the two distributions no longer exhibit the same image, the scheme exhibits a weakness. In other words, we have established that the scheme violates the independence:

$$P(M \mid C) = P(M) \quad \forall C$$

My question is now, how can I relate this factoid to the OTP property that possession of the ciphertext does not reveal anything about the plaintext, in terms of conditional entropy:

$$H(M \mid C) = H(M)$$

I am looking for an easy mathematical link between the conditional entropy and conditional probability, since only the latter represents a concept that students are familiar with.

$\endgroup$
  • $\begingroup$ The distributions $U\{0,1\}$ and $U\{1,2\}$ are different but they have the same entropy. So, if I well understand your question, the entropy will not help you. The property you denote by $P(M\mid C)=P(M)$ is the independence between $M$ and $C$, it means that the distribution of $M$ given $C=x$ does not depend on $x$. The property $H(M \mid C)=H(M)$ is weaker. $\endgroup$ – Stéphane Laurent Mar 12 '13 at 21:07
  • $\begingroup$ Maybe I should not think in terms of different distributions, but rather consistent distributions for all possible values of $C$. Would that facilitate the link to $H(M \mid C) = H(M)$? $\endgroup$ – mavam Mar 13 '13 at 16:26
  • $\begingroup$ $H(M|C)$ is just the average over the distribution of $C$ of the entropy of $M$ under the conditional probability $P(M|C=x)$. There are many possible situations for which $H(M|C)=H(M)$. $\endgroup$ – Stéphane Laurent Mar 13 '13 at 19:48

Your Answer

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

Browse other questions tagged or ask your own question.