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

Exercises

10.1  Compute Pd₀ and Pd₁ 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(n₁, k, λ₁) on symbol set {1, …, n₁} and suppose B is an OA(n₂, k, λ₂) on symbol set {1, …, n₂}. We construct C, an OA(n₁n₂, k, λ₁ λ₂) on symbol set {1, …, n₁} × {1, …, n₂}, as follows: for each row r₁ = (x₁, …, x_k) of A and for each row s₁ = (y₁, …, y_k) of B, define a row

of C. Prove that C is indeed an OA(n₁ n₂, k, λ₁ λ₂).

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|M²) for the authentication code from Exercise 10.1. The probability distribution on sequences of two sources is as follows:

Compare the entropy bounds for Pd₀ and Pd₁ 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 e_k(s) = a, and otherwise.

To compute , use Bayes’ formula

can be calculated as follows: write m₁ = (s₁, a₁) and m₂ = (s₂, a₂). Then

(Note the similarity with the computation of p(m).) To compute , observe that and e_k(s₂) = a₂, and , otherwise.