Question 1. (15 points) Consider an encryption scheme II whose message space and ciphertext space are same: The set of N integers in the range 0, 1, 2, ...,N 1 where N is a very large prime integer (say, 1024 bits long). The key space is the set of N 1 integers 1, 2, 3, ...,N 1, and key generation is uniform (i.e., all keys are equally likely). Encrypting a message m is done by multiplying it with key k then reducing the result modulo N: k mod N C= m Decrypting a ciphertext c is done by computing k' such that k*k' mod N equals 1 (for a given k, N pair, such a k' is known to exist, to be unique, and to be easily computable from k and N), then multiplying c with the above k' then reducing the result modulo N: m = C*k' mod N m*k*k' = m. Decryption recovers the original message because, modulo N, we have c*k' = 1. (10 points) Using the steps on page 8 of slide set 4, explain how an adversary can succeed with probability greater than 0.5 at the adversarial indistinguishability ex- periment (thereby proving that II does not have perfect secrecy). 2. (5 points) Give another reason than the above for II's lack of perfect secrecy (there are many, just give one) The adversarial indistinguishability experiment Privka, II: 1. The adversary A outputs a pair of messages mo, mi E M. 2. A key k is generated using Gen, and a uniform bit b E {0,1} is chosen. Ciphertext ct Enck(mo) is computed and given to A. We refer to c as the challenge ciphertext. 3. A outputs a bit b'. 4. The output of the experiment is defined to be 1 if b' and 0 otherwise. We write PrivkeII = 1 if the output of the experiment is 1 and in this case we say that A succeeds. = bi Question 1. (15 points) Consider an encryption scheme II whose message space and ciphertext space are same: The set of N integers in the range 0, 1, 2, ...,N 1 where N is a very large prime integer (say, 1024 bits long). The key space is the set of N 1 integers 1, 2, 3, ...,N 1, and key generation is uniform (i.e., all keys are equally likely). Encrypting a message m is done by multiplying it with key k then reducing the result modulo N: k mod N C= m Decrypting a ciphertext c is done by computing k' such that k*k' mod N equals 1 (for a given k, N pair, such a k' is known to exist, to be unique, and to be easily computable from k and N), then multiplying c with the above k' then reducing the result modulo N: m = C*k' mod N m*k*k' = m. Decryption recovers the original message because, modulo N, we have c*k' = 1. (10 points) Using the steps on page 8 of slide set 4, explain how an adversary can succeed with probability greater than 0.5 at the adversarial indistinguishability ex- periment (thereby proving that II does not have perfect secrecy). 2. (5 points) Give another reason than the above for II's lack of perfect secrecy (there are many, just give one) The adversarial indistinguishability experiment Privka, II: 1. The adversary A outputs a pair of messages mo, mi E M. 2. A key k is generated using Gen, and a uniform bit b E {0,1} is chosen. Ciphertext ct Enck(mo) is computed and given to A. We refer to c as the challenge ciphertext. 3. A outputs a bit b'. 4. The output of the experiment is defined to be 1 if b' and 0 otherwise. We write PrivkeII = 1 if the output of the experiment is 1 and in this case we say that A succeeds. = bi