Let n be a positive integer. A Latin square of order n is an nxn array...
Fantastic news! We've Found the answer you've been seeking!
Question:
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).
Expert Answer:
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Posted Date:
Students also viewed these programming questions
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
Lamonda Corp. uses a job order cost system. On April 1, the accounts had the following balances: The following transactions occurred during April: (a) Purchased materials on account at a cost of...
-
Solve the linear programming problems stated in Problem Maximize P = 300x: + 460y subject to 245x- + 452y 4,181 290x- + 379y 3,888 390x + 299y 4,407 x, y 0
-
Athens Gas Station has figured out the weekly demand distribution for their gas sales. Each gallon of gas sold at the pump results in a profit of 10 cents/gallon and any lost sales results in a cost...
-
Provide examples for composite and collection objects. How do they differ?
-
Evigi Company has two divisions, the Semiconductor Division and the PC Division. The PC Division may purchase semiconductors from the Semiconductor Division or from outside suppliers. The...
-
Explain the correlation here and solve please When the average price of movie tickets rises, it has an effect on the purchase of computer games. (Analyze computer games.) 1. Draw and Label...
-
Atkinson, Inc. manufactures products A, B, and C from a common process. Joint costs were $60,000. Additional information is as follows: If Further Processed Product units Produced Sales Value in the...
-
The statement of cash flows classifies each transaction as an operating activity, an investing activity, or a financing activity. Operating activities are the types of activities the company performs...
-
In the unadjusted trial balance of its worksheet for the year ended December 31, 2025, Kim Company reported Equipment of NT$120,000. The year-end adjusting entries require an adjustment of NT$15,000...
-
Problem 24.25 describes two particles that orbit the earth's magnetic field lines. What is the frequency of the circular orbit for a. An electron with speed \(1.0 \times 10^{6} \mathrm{~m} /...
-
A device called a flip coil can be used to measure the earth's magnetic field. The coil has 100 turns and an area of \(0.010 \mathrm{~m}^{2}\). It is oriented with its plane perpendicular to the...
-
What UM practices does your health insurance company follow to control costs and ensure the provision of medically necessary services? This information may be available in your insurance benefits...
-
Describe, in detail, three psychological principles that we discussed are in the angry birds game and how each influences game play / player experience.
-
Tiger, Inc. signed a lease for equipment on July 1, 2007.The lease is for 10 years (the useful life of the asset).The first of 10 equal annual payments of $500,000 was made on July 1, 2007.The...
-
The balance sheet of Dot Co. for the year ended 31 December 20X2, together with comparative figures for the previous year, is shown in Figure 13.7 (all figures :000). You are informed that there were...
-
Under IFRS, a group is a set of entities that the parent: A. Significantly influences. B. Owns a majority of the voting power in. C. Jointly controls. D. Controls.
-
Under IFRS, a subsidiary is: A. An entity controlled. B. A company controlled. C. A company significantly influenced. D. An entity significantly influenced.
Study smarter with the SolutionInn App