Let n be a positive integer. A Latin square of order n is an nxn array...

 

Transcribed Image Text:

Let n be a positive integer. A Latin square of order n is an nxn array L whose entries are the integers 1, 2,...,n such that every element of {1,2,...,n) occurs exactly once in each row and each column of L. An example of a Latin square of order 3 is as follows: 1 2 3 3 12 2 31 Given any Latin sqare L of order n, we can define the associated Latin square cipher as follows. We have M C = X = {1,2,...,n}. For M, K = {1,2,...,n} the encryption EK (M) of M with key K is the ciphertext C = Ex(M) L(K, M), the entry in L at row K and column M. Thus, row K of L lists the encryptions of the plaintexts 1, 2, ......n under key K. In this problem, you will use the characterization p(CIM) = p(C) for all Me M and C = C with p(M) > 0 and p(C) > 0 to show that Latin square ciphers provide perfect secrecy, provided each key is used with equal probability. You must use this characterization; you may not use Shannon's Theorem (Theorem 5 on page 33 of the Week 2 slides, which was given in class without proof). a. (3 marks) Prove that for every M = M and every CE C, there exists exactly one key K K such that Ek (M) = C. b. (3 marks) Suppose every key K E K is chosen with equal probability 1/n. Prove that p(C|M) = 1/n for all MM and CC. c. (3 marks) Let CE C. Prove that the map XM via KDK(C) that sends a key K to the decryption of C under K is a bijection. d. (3 marks) Let C = C. Use part (c) to prove that p(DK(C)) = 1. e. (3 marks) Suppose every key K E K is chosen with equal probability 1/n. Prove that p(C) = 1/n for all CC, thereby proving perfect secrecy by part (b). Let n be a positive integer. A Latin square of order n is an nxn array L whose entries are the integers 1, 2,...,n such that every element of {1,2,...,n) occurs exactly once in each row and each column of L. An example of a Latin square of order 3 is as follows: 1 2 3 3 12 2 31 Given any Latin sqare L of order n, we can define the associated Latin square cipher as follows. We have M C = X = {1,2,...,n}. For M, K = {1,2,...,n} the encryption EK (M) of M with key K is the ciphertext C = Ex(M) L(K, M), the entry in L at row K and column M. Thus, row K of L lists the encryptions of the plaintexts 1, 2, ......n under key K. In this problem, you will use the characterization p(CIM) = p(C) for all Me M and C = C with p(M) > 0 and p(C) > 0 to show that Latin square ciphers provide perfect secrecy, provided each key is used with equal probability. You must use this characterization; you may not use Shannon's Theorem (Theorem 5 on page 33 of the Week 2 slides, which was given in class without proof). a. (3 marks) Prove that for every M = M and every CE C, there exists exactly one key K K such that Ek (M) = C. b. (3 marks) Suppose every key K E K is chosen with equal probability 1/n. Prove that p(C|M) = 1/n for all MM and CC. c. (3 marks) Let CE C. Prove that the map XM via KDK(C) that sends a key K to the decryption of C under K is a bijection. d. (3 marks) Let C = C. Use part (c) to prove that p(DK(C)) = 1. e. (3 marks) Suppose every key K E K is chosen with equal probability 1/n. Prove that p(C) = 1/n for all CC, thereby proving perfect secrecy by part (b).