Conditional probability and perfect security

Next, we will talk about the probabilities that come up in the abstract theory of cipher systems. We suppose we have a set M of ``messages'' or ``plaintexts,'' a set C of ciphertexts, and a set F of enciphering transformations. For a given plaintext $\mu$ (or piece of plaintext), we can choose an enciphering transformation fand compute the ciphertext $\gamma=f(\mu)$. All this is described in Chapter 3 of [Beutelspacher, 1994].

It is essential that we give the ``a priori'' probabilities $P(\mu)$of a piece of plaintext $\mu$ actually occurring and the ``a posteriori'' probabilities $P_\gamma(\mu)$ that a given ciphertext $\gamma$ came from the plaintext $\mu$.

We will work through an example here. We assume that the message set is $M=\{A,B\}$ and the set of possible ciphertexts is $C=\{X,Y,Z\}$. Here the letters stands for possible messages and their cipher equivalents; we aren't so concerned with what the actual messages are.

The transformations are rules that assign to each plaintext one of the ciphertexts. We are always assuming that these transformations are one-to-one, which means that two different plaintexts are not mapped by the same transformation to the same ciphertext. The table below shows a sample list of possible transformations.

$$\begin{array}{rccr} & A (50\%) & B (50\%) & \\ \hline f_1:\... ...Z & X & \quad 20\% \\ f_5:\; & Z & Y & \quad 10\% \end{array}$$

From the table we can read, for example, that f₃(X)=Y and f₃(Y)=X. We have also indicated the probabilities associated with the plaintexts and with the transformations. In this example, the two plaintexts A and B are supposed to be equally likely to occur.

We may now investigate whether or not this abstract cipher system has perfect security. To do that we must compute $P_\gamma(\mu)$ for each possible plaintext $\mu$ and ciphertext $\gamma$. The key tool for doing this is Bayes' Formula for computing conditional probabilities.

Bayes' Formula: Suppose S is a set of possible outcomes and P(S) is the probability that something in S actually occurs. Suppose that T is a subset of the outcomes in S. Then the probability that T occurs given that we know something in S occurs is

$$P(T\mid S) = \frac{P(T)}{P(S)}$$

In our case, the set S is the collection of all outcomes in which the given ciphertext $\gamma$ occurs. The set T is the collection of all outcomes in which $\gamma$ is the transformation of the plaintext $\mu$.

Let's carry this out for $\gamma=X$ and $\mu=A$. The ciphertext Xoccurs in three outcomes:

1.

we choose $\mu=A$ and transformation f₁;

2.

or we choose $\mu=B$ and transformation f₃;

3.

or we choose $\mu=B$ and transformation f₄.

The choice of plaintext and transformation is assumed to be independent. Thus, by the rule for independence the probability of case (1) is $0.5\times 0.3 =0.15$. Similarly, the probabilities of the other two cases are 0.05 and 0.1, respectively. Secondly, all three cases are mutually exclusive; they cannot occur at the same time. Thus, by our rule for exclusion, the probability that $\gamma=X$ is

0.15+0.05+0.1=0.3

Only one of the cases correspond to X coming from A; that is case (1) with probability 0.15. By Bayes' Formula, we conclude

$$P_X(A) = \frac{0.15}{0.3} = 0.5 =P(A)$$

This case is consistent with the condition for perfect security. It turns out that all the other calculations P_X(B), P_Y(A), P_Y(B), P_Z(A) and P_Z(B) all turn out to yield 0.5=P(A)=P(B). Hence, this example does indeed describe a cipher system with perfect security.

For one more advanced example, lets consider a one-time pad where the stream of key letters is taken from an English text (say, Rebecca of Sunnybrook Farm; see [Follett, 1980]). Let f_j be the additive cipher that sends letter number i to letter number i+j, and suppose that we use transformation f_j when the key letter is letter number j. If we use letters instead of indices, we might write f_A(A)=B, f_A(C)=D, f_E(H)=M, etc. The probability of f_j being chosen is the probability p_j of letter number j occurring in English text.

Now me may calculate P_A(A) and see if it does indeed equal P(A). The combinations that lead to the cipher letter A are

$$A=f_{26}(A)=f_{25}(B)=f_{24}(C)=\dotsb = f_1(Z).$$

The probability of any of these happening is

$$p_{26}p_1+p_{25}p_2+p_{24}p_3+\dotsb p_{1}p_{26} =\sum_{j=1}^{26} p_{27-j}p_j$$

So the conditional probability that A actually comes from A is

$$\frac{p_{26}p_1}{\sum_{j=1}^{26} p_{27-j} p_j}$$

This is easy enough to calculate given a table of letter frequencies. Using the one from [Beutelspacher, 1994], we find

$$P_A(A)=0.001688 \neq 0.08167 = P(A)$$

That alone shows this system has far from perfect security. This result is plausible because to arrive at A from A under this system we would have to choose the transformation corresponding to Z, which is a very infrequent letter.

Now the interesting question after this is how to exploit lack of perfect security in formulating a method of cryptanalysis.