6. A Conjectured Private-key Encryption Scheme (15 points). Consider the following encryption scheme. The message space M is the set of all n-bit strings that have exactly l-ones in them. The key space is the set of all permutations from the set {1, 2,...,n} to {1,2,...,n}. The set of all cipher-texts, represented by C, is identical to M. The private key encryption scheme (Gen, Enc, Dec) is defined below. Gen(): Return a random permutation sk from {1,2,...,n} to {1,2,...,n}. Encsk(m): Return c, where c is obtained by permuting the message m using the per- mutation sk. For example, if m=m1m2...mn, then the permutation of m using sk is the string C=C102... cn = msk(1) Misk(2) ...Msk(n) Deck(c): Return m, where m is obtained from c by inverting the permutation sk. For example, if c = cc2...cn, then decoded message is Csk (1) Csk (2) ... Csk (n) Is this scheme perfectly secure? If yes, then provide a proof. If no, then give a counterexample. A worked-out example of the encryption algorithm. Let n = 4 and 1 = 2. Therefore, we have the set of messages M= {1100, 1010, 1001, 0110, 0101, 0011}. Note that the size of the set M is 6) = 6. The set K is the set of all permutations from the set {1,2,3,4} to the set {1,2,3,4}. Note that there are a total of 4! = 24 such permutations. Suppose the Gen() algorithm picked the following permutation sk(1) = 3, sk(2) = 1, sk(3) = 4, sk(4) = 2 Suppose Alice wants to encrypt the message m = mim2mzm = 1010 using the sk above. Then, the cipher-text is c=msk(1) Msk(2) Msk(3) Msk(1) = m3mimim2 = 1100. When Bob wants to decrypt the message c = C162C3C1 = 1100, he outputs m = Csk (1) Csk (2) Csk (3) sk (1) = C2C1CC3= 1010 Note that in the example presented above, we recovered the original message! However, is this scheme secure? 6. A Conjectured Private-key Encryption Scheme (15 points). Consider the following encryption scheme. The message space M is the set of all n-bit strings that have exactly l-ones in them. The key space is the set of all permutations from the set {1, 2,...,n} to {1,2,...,n}. The set of all cipher-texts, represented by C, is identical to M. The private key encryption scheme (Gen, Enc, Dec) is defined below. Gen(): Return a random permutation sk from {1,2,...,n} to {1,2,...,n}. Encsk(m): Return c, where c is obtained by permuting the message m using the per- mutation sk. For example, if m=m1m2...mn, then the permutation of m using sk is the string C=C102... cn = msk(1) Misk(2) ...Msk(n) Deck(c): Return m, where m is obtained from c by inverting the permutation sk. For example, if c = cc2...cn, then decoded message is Csk (1) Csk (2) ... Csk (n) Is this scheme perfectly secure? If yes, then provide a proof. If no, then give a counterexample. A worked-out example of the encryption algorithm. Let n = 4 and 1 = 2. Therefore, we have the set of messages M= {1100, 1010, 1001, 0110, 0101, 0011}. Note that the size of the set M is 6) = 6. The set K is the set of all permutations from the set {1,2,3,4} to the set {1,2,3,4}. Note that there are a total of 4! = 24 such permutations. Suppose the Gen() algorithm picked the following permutation sk(1) = 3, sk(2) = 1, sk(3) = 4, sk(4) = 2 Suppose Alice wants to encrypt the message m = mim2mzm = 1010 using the sk above. Then, the cipher-text is c=msk(1) Msk(2) Msk(3) Msk(1) = m3mimim2 = 1100. When Bob wants to decrypt the message c = C162C3C1 = 1100, he outputs m = Csk (1) Csk (2) Csk (3) sk (1) = C2C1CC3= 1010 Note that in the example presented above, we recovered the original message! However, is this scheme secure