10.4 Entropy Bound

In this section, we use entropy techniques to obtain bounds on the deception probabilities. The first of these is a bound on Pd₀.

THEOREM 10.13

Suppose that is an authentication code. Then

PROOF  From Equation (10.1), we have

Since the maximum of the values payoff (s, a) is greater than their weighted average, we obtain

Hence, by Jensen’s inequality (Theorem 2.5), we have

Recalling from Section 10.2 that

we see that

Now, we observe that (i.e., the probability that a is the authenticator, given that s is the source state). Hence,

by the definition of conditional entropy. We complete the proof by showing that - H(A|S) = H(K|M) - H(K). This follows from basic entropy identities. On one hand, we have

On the other hand, we compute

where we use the facts that H(A|K, S) = 0 since the key and source state uniquely determine the authenticator, and H(K, S) = H(K) + H(S) since the source and key are independent events.

Equating the two expressions for H(K, A, S), we obtain

But a message m = (s, a) is defined to consist of a source state and an authenticator (i.e., ). Hence, H(K|A, S) = H(K|M) and the proof is complete.

There is a similar bound for Pd₁ which we will not prove here. It is as follows:

THEOREM 10.14

Suppose that is an authentication code. Then

We need to define what we mean by the random variable M². Suppose we authenticate two distinct source states using the same key K. In this way, we obtain an ordered pair of message . In order to define a probability distribution on , it is necessary to define a probability distribution on , with the stipulation that for every (that is, we do not allow source states to be repeated). The probability distribution on and will induce a probability distribution on , in the same way that the probability distributions on and induce a probability on .

As an illustration of the two bounds, we consider our basic orthogonal array construction and show that the bounds of Theorems 10.13 and 10.14 are both met with equality. First, it is clear that

since each of the λn² authentication rules are chosen with equal probability. Let’s next turn to the computation of H(K|M). If any message m = (s, a) is observed, this restricts the possible keys to a subset of size λn. Each of these λn keys is equally likely. Hence, H(K|m) = log λn, for any message m. Then, we get the following:

Thus we have

so the bound is met with equality.

If we observe two messages which have been produced using the same key (and different source states), then the number of possible keys is reduced to λ. Using similar reasoning as above, we have that H(K|M²) = log λ. Then

so this bound is also met with equality.

10.5 Notes and References

Authentication codes were invented in 1974 by Gilbert, MacWilliams, and Sloane [GMS74]. Much of the theory of authentication codes was developed by Simmons, who proved many fundamental results in the area. Two useful survey articles by Simmons are [SI92] and [SI88]. Another good survey is Massey [MA86].

The connections between orthogonal arrays and authentication codes has been addressed by several researchers. The treatment here is based on three papers by Stinson [ST88], [ST90] and [ST92]. Orthogonal arrays have been studied for over 45 years by researchers in statistics and in combinatorial design theory. For example, the bound in Theorem 10.9 was first proved by Plackett and Berman in 1945 in [PB45]. Many interesting results on orthogonal arrays can be found in various textbooks on combinatorial design theory such as Beth, Jungnickel, and Lenz [BJL85].

Finally, the use of entropy techniques in the study of authentication codes was introduced by Simmons. The bound of Theorem 10.13 was first proved in Simmons [SI85]; a proof of Theorem 10.14 can be found in Walker [WA90].