Cryptography: Theory and Practice:Authentication Codes | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

10.3.2 Constructions and Bounds for OAs

Suppose that we construct an authentication code from an OA(n, k, λ). The parameter n determines the number of authenticators (i.e., the security of the code), while the parameter k determines the number of source states the code can accommodate. The parameter λ relates only to the number of keys, which is λn². Of course, the case λ = 1 is most desirable, but we will see that it is sometimes necessary to use orthogonal arrays with higher values of λ.

Suppose we want to construct an authentication code with a specified source set , and a specified security level ∈ (i.e., so that Pd₀ ≤ ∈ and Pd₁ ≤ ∈). An appropriate orthogonal array will satisfy the following conditions:

1. n ≥ 1/∈

(observe that we can always delete one or more columns from an orthogonal array and the resulting array is still an orthogonal array, so we do not require

)

3. λ is minimized, subject to the two previous conditions being satisfied.

Let’s first consider orthogonal arrays with λ = 1. For a given value of n, we are interested in maximizing the number of columns. Here is a necessary condition for existence:

THEOREM 10.6

Suppose there exists an OA(n, k, 1). Then k ≤ n + 1.

PROOF Let A be an OA(n, k, 1) on symbol set X = {0, 1, …, n - 1}. Suppose π is a permutation of X, and we permute the symbols in any column of A according to the permutation π. The result is again an OA(n, k, 1). Hence, by applying a succession of permutations of this type, we can assume without loss of generality that the first row of A is (00 … 0).

We next show that each symbol must occur exactly n times in each column of A. Choose two columns, say c and c′, and let x be any symbol. Then for each symbol x′, there is a unique row of A in which x occurs in column c and x′ occurs in column c′. Letting x′ vary over X, we see that x occurs exactly n times in column c.

Now, since the first row is (00 … 0), we have exhausted all occurrences of ordered pairs (0, 0). Hence, no other row contains more than one occurrence of 0. Now, let us count the number of rows containing at least one 0: the total is 1 + k(n - 1). But this total cannot exceed the total number of rows in A, which is n². Hence, 1 + k(n - 1) ≤ n², so k ≤ n + 1, as desired.

We now present a construction for orthogonal arrays with λ = 1 in which k = n. This is, in fact, the construction that was used to obtain the orthogonal array presented in Figure 10.5.

THEOREM 10.7

Suppose p is prime. Then there exists an orthogonal array OA(p, p, 1).

PROOF The array will be a p² × p array, where the rows are indexed by and the columns are indexed by . The entry in row (i, j) and column x is defined to be ix + j mod p.

Suppose we choose two columns, x, y, x ≠ y, and two symbols a, b. We want to find a (unique) row (i, j) such that a occurs in column x and b occurs in column y of row (i, j). Hence, we want to solve the two equations

for the unknowns i and j (where all arithmetic is done in the field ). But this system has the unique solution

Hence, we have an orthogonal array.

We remark that any OA(n, n, 1) can be extended by one column to form an OA(n, n + 1, 1) (see the Exercises). Hence, using Theorem 10.7, we can obtain an infinite class of OA’s that meet the bound of Theorem 10.6 with equality.

Table of Contents