![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
10.3.2 Constructions and Bounds for OAsSuppose 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 λn2. 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
Lets 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 n2. Hence, 1 + k(n - 1) ≤ n2, 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 p2 × p array, where the rows are indexed by 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 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 OAs that meet the bound of Theorem 10.6 with equality.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |