|
|
 |
[an error occurred while processing this directive]
Exercises
- 10.1 Compute Pd0 and Pd1 for the following authentication code, represented in matrix form:
The probability distributions on  and  are as follows: 
What are the optimal impersonation and substitution strategies?
- 10.2 We have seen a construction for an orthogonal array OA(p, p, 1) when p is prime. Prove that this OA(p, p, 1) can always be extended by one extra column to form an OA(p, p + 1, 1). Illustrate your construction in the case p = 5.
- 10.3 Suppose A is an OA(n1, k, λ1) on symbol set {1, …, n1} and suppose B is an OA(n2, k, λ2) on symbol set {1, …, n2}. We construct C, an OA(n1n2, k, λ1 λ2) on symbol set {1, …, n1} × {1, …, n2}, as follows: for each row r1 = (x1, …, xk) of A and for each row s1 = (y1, …, yk) of B, define a row
of C. Prove that C is indeed an OA(n1 n2, k, λ1 λ2).
- 10.4 Construct an orthogonal array OA(3, 13, 3).
- 10.5 Write a computer program to compute H(K), H(K|M) and H(K|M2) for the authentication code from Exercise 10.1. The probability distribution on sequences of two sources is as follows:
Compare the entropy bounds for Pd0 and Pd1 with the actual values you computed in Exercise 10.1.
HINT To compute  , use Bayes’ formula 
We already know how to calculate  . To compute  , write m = (s, a) and then observe that  if ek(s) = a, and  otherwise.
To compute  , use Bayes’ formula 
 can be calculated as follows: write m1 = (s1, a1) and m2 = (s2, a2). Then
(Note the similarity with the computation of p(m).) To compute  , observe that  and ek(s2) = a2, and  , otherwise.
|
