![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
Example 10.2 Consider the authentication matrix of Figure 10.4. Suppose the probability distributions on 1 ≤ i ≤ 4; and The values payoff (s, a) are as follows: Hence, Pd0 = 3/4. Oscars optimal impersonation strategy is to place any of the messages (1, 1), (3, 1) or (4, 2) into the channel. Now we turn to the computation of Pd1. First, we present the various values payoff (s′, a′; s, a) in the form of a matrix. The entry in row (s, a) and column (s′, a′) is the value payoff (s′, a′; s, a). Thus we have p1,1 = 2/3, p2,2 = 1/2, and ps,a = 1 for all other s, a. It is then a simple matter to evaluate Pd1 = 7/8. An optimal substitution strategy for Oscar is as follows: This strategy indeed yields Pd1 = 7/8. The computation of Pd1 in Example 10.2 is straightforward but lengthy. We can in fact simplify the computation of Pd1 by observing that we divide by the quantity payoff (s, a) in the computation of ps,a, and then later multiply by payoff (s, a) in the computation of Pd1. Of course, these two operations cancel each other out. Suppose we define for all s, a. Then we have the following more concise formula for Pd1: 10.3 Combinatorial BoundsWe have seen that the security of an authentication code is measured by the deception probabilities. Hence, we want to construct codes so that these probabilities are as small as possible. But other considerations are also important. Lets consider the various objectives that we might strive for in an authentication code:
In this section, we determine lower bounds on the deception probabilities, which will be computed in terms of other parameters of the code. Recall that we have defined an authentication code to consist of a four-tuple Suppose we fix a source state Hence, for every The following theorem follows easily. THEOREM 10.1 Suppose for every Now, we turn our attention to substitution. Suppose we fix s, a and s′, where s′ ≠ s. Then we have the following: So, there exists an authentication tag a′(s′, s, a) such that The next theorem follows as a consequence. THEOREM 10.2 Suppose for every PROOF We have Further, equality occurs if and only if Combining Theorems 10.1 and 10.2, we get the following: THEOREM 10.3 Suppose for every PROOF Equations (10.4) and (10.5) imply Equation (10.6). Conversely, Equation (10.6) implies Equations (10.4) and (10.5). If the keys are equiprobable, then we obtain the following corollary: COROLLARY 10.4 Suppose for every 10.3.1 Orthogonal ArraysIn this section, we look at the connections between authentication codes and certain combinatorial structures called orthogonal arrays. First, we give a definition.
DEFINITION 10.2 An orthogonal array OA(n, k, λ) is a λn2 × k array of n symbols, such that in any two columns of the array every one of the possible n2 pairs of symbols occurs in exactly λ rows. Orthogonal arrays are well-studied structures in combinatorial design theory, and are equivalent to other structures such as transversal designs, mutually orthogonal Latin squares and nets. In Figure 10.5, we present an orthogonal array OA(3, 3, 1) which is obtained from the authentication matrix of Figure 10.3. Any orthogonal array OA(n, k, λ) can be used to construct an authentication code with Pd0 = Pd1 = 1/n, as stated in the following theorem. THEOREM 10.5 Suppose there is an orthogonal array OA(n, k, λ). Then there is an authentication code PROOF Use each row of the orthogonal array as an authentication rule with equal probability 1/(λn2). The correspondences are as follows: Since Equation (10.7) is satisfied, we can apply Corollary 10.4, obtaining a code with the stated properties.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |