Theorem 10.6 tells us that λ > 1 if k > n + 1. We will prove a more general result that places a lower bound on λ as a function of n and k. First, however, we derive an important inequality that we will use in the proof.

LEMMA 10.8

Suppose b₁, …, b_m are real numbers. Then

PROOF  Apply Jensen’s Inequality (Theorem 2.5) with f(x) = -x² and a_i = 1/m, 1 ≤ i ≤ m. The function f is continuous and concave, so we obtain

which simplifies to give the desired result.

THEOREM 10.9

Suppose there exists an OA(n, k, λ). Then

PROOF  Let A be an OA(n, k, λ) on symbol set X = {0, 1,…, n - 1}, where, without loss of generality, the first row of A (00 … 0) (as in Theorem 10.6).

Let us denote the set of rows of A by let r₁ denote the first row, and let . For any row r of A, denote by x_r the number of occurrences of 0 in row r. It is easy to count the total number of occurrences of 0 in . Since each symbol must occur exactly λn times in each column of A, we have that

Now, the number of times the ordered pair (0, 0) occurs in rows in is

Applying Lemma 10.8, we obtain

and hence

On the other hand, in any given pair of columns, the ordered pair (0, 0) occurs in exactly λ rows. Since there are k(k - 1) ordered pairs of columns, it follows that the exact number of occurrences of the ordered pair (0, 0) in rows in is (λ - 1)k(k - 1). We therefore have

and hence

If we divide out a factor of k, we get

Expanding, we have

This simplifies to give

or

Finally, taking out a factor of λ(n - 1), we obtain

which is the desired bound.

Our next result establishes the existence of an infinite class of orthogonal arrays that meet the above bound with equality.

THEOREM 10.10

Suppose p is prime and d ≥ 2 is an integer. Then there is an orthogonal array OA(p, (p^d - 1)/(p - 1), p^d-2).

PROOF  Denote by the vector space of all d-tuples over . We will construct A, an OA(p,(p^d - 1)/(p - 1), p^d-2) in which the rows and columns are indexed by certain vectors in . The entries of A will be elements of . The set of rows is defined to be ; the set of columns is

consists of all vectors in , so . consists of all non-zero vectors that have the first non-zero coordinate equal to 1. Observe that

and that no two vectors in are scalar multiples of each other.

Now, for each and each , define

where · denotes the inner product of two vectors (reduced modulo p).

We prove that A is the desired orthogonal array. Let be two distinct columns, and let . We will count the number of row such that and . Denote and . The two equations can be written as two linear equations in :

Figure 10.6  An OA(2, 7, 2)

This is a system of two linear equations in the d unknowns r₁, … r_d. Since and are not scalar multiples, the two equations are linearly independent. Hence, this system has a solution space of dimension d - 2. That is, the number of solutions (i.e., the number of rows in which x occurs in column and y occurs in column ) is p^d-2, as desired.

Let’s carry out a small example of this construction.

Example 10.3

Suppose we take p = 2, d = 3. Then we will construct an OA(2, 7, 2). We have

and

The orthogonal array in Figure 10.6 results.

10.3.3 Characterizations of Authentication Codes

To this point, we have studied authentication codes obtained from orthogonal arrays. Then we looked at necessary existence conditions and constructions for orthogonal arrays. One might wonder whether there are better alternatives to the orthogonal array approach. However, two characterization theorems tell us that this is not the case if we restrict our attention to authentication codes in which the deception probabilities are as small as possible.

We first prove the following partial converse to Theorem 10.5:

THEOREM 10.11

Suppose is an authentication code where and Pd₀ = Pd₁ = 1/n. Then . Further, if and only if there is an orthogonal array OA (n, k, 1) where , and for every key .

PROOF  Fix two (arbitrary) source states s and s′, s ≠ s′, and consider Equation (10.6). For each ordered pair (a, a′) of authentication tags, define

Then for every pair (a, a′). Also, the n², sets are disjoint. Hence, .

Now, suppose that . Then for every pair (a, a′), and Equation (10.6) tells us that for every key .

It remains to show that the authentication matrix forms an orthogonal array OA(n, k, 1). Consider the columns indexed by the source states s and s′. Since for every (a, a′), we have every ordered pair occurring exactly once in these two columns. Since, s and s′ are arbitrary, we see that every ordered pair occurs exactly once in any two columns.

The following characterization is more difficult; we state it without proof.

THEOREM 10.12

Suppose is an authentication code where and Pd₀ = Pd₁ = 1/n. Then . Further, if and only if there is an orthogonal array OA(n, k, λ), where λ = (k(n - 1) + 1)/n², and for every key .

REMARK  Notice that Theorem 10.10 provides an infinite class of orthogonal arrays that meet the bound of Theorem 10.12 with equality.