URGENT SOLUTION REQUIRED

COURSE: Information security aur topic cryptography

1. Public-Key Encryption (25 points) Let (Gen, Enc, Dec) be a public-key encryption that is (2n/5,2n/5)-ciphertext-indistinguishability secure for encrypting a single bit. That is, for every adversary A of complexity at most 2n/5 it holds that (sk,pk)GenPr[A(pk,Encpk(0))=1](skpk)GenPr[A(pk,Encpk(1))=1]2n/5. (a) Prove that (Gen, Enc, Dec) is (2n/10,2n/10)-CPA secure. (Hint: use the fact that every message is just a single bit.) Since (Gen, Enc, Dec) is limited to single-bit messages, we construct a public-key encryption scheme (Gen', Enc', Dec') for length- binary messages in the following way. - The keys are generated in the same way, i.e., Gen' = Gen. - To encrypt a length- message m=(m1,,m) where mi{0,1}, compute Enc Ek (m):= (Encpk(m1),,Encpk(m)). - To decrypt a ciphertext c=(c1,,cl), compute Decskr(c):=(Decsk(c1),,Decsk(cl)). Throughout, we assume that is polynomial in n (say, =n2 ). In class, we proved that (Gen', Enc', Dec') is (2n/10,2n/10)-ciphertext-indistinguishability secure for length- messages. In the rest of the question, our goal is to prove that (Gen', Enc', Dec') is CPA-secure (b) Let m0:=0101 and m1:=0110 be length- 4 binary messages, and consider the following game between you and a challenger. - The challenger samples keys (sk, pk) Gen', and a bit b{0,1}. The challenger sends you (pk, c:=Encpk(m) ). (Note that mb is encrypted using the new encryption scheme.) - The challenger also picks two random bits 0{0,1} and 1{0,1}, and sends (0,1) to you. - Your goal is to return Enc pk(b). That is, you are required to return an encryption of b using the old encryption scheme and with the same public key that the challenger generated. Explain how to win the game with probability 1. (c) Say that there exists an adversary A of complexity 2n/20 that breaks the CPA-security of (Gen', Enc', Dec ) on length- messages with advantage 2n/20. Construct an adversary B of complexity 2n/1010 that breaks the ciphertext-indistinguishability of (Gen', Enc , Dec ) on CPA secure for length- 4 messages. (Hint: choose the length- 4 messages m0:=(0101) and m1:=(0110).)