![]() |
Cryptography: Theory and Practice
by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
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 b1, , bm are real numbers. Then
PROOF Apply Jensens Inequality (Theorem 2.5) with f(x) = -x2 and ai = 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 r1 denote the first row, and let
. For any row r of A, denote by xr 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, (pd - 1)/(p - 1), pd-2).
PROOF Denote by the vector space of all d-tuples over
. We will construct A, an OA(p,(pd - 1)/(p - 1), pd-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 r1,
rd. 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 pd-2, as desired.
Lets 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.
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 Pd0 = Pd1 = 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 n2, 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 Pd0 = Pd1 = 1/n. Then
. Further,
if and only if there is an orthogonal array OA(n, k, λ), where λ = (k(n - 1) + 1)/n2, 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.
Previous | Table of Contents | Next |