3.20 For a function g: {0, 1 }n --+ {0, 1}n, let g$() be an oracle that, on input 1n, chooses r +- {0, 1 }n uniformly at random and returns (r, g (r)). We say a keyed function F is a weak pseudorandom function if for all PPT algorithms D, there exists a negligible function negl such that:

| pr [ D^f^s (.) (1^n) =1] - pr [ D^f^s (.) (1^n) =1 ] | <= negl (n),

where k <-- {0, l }^n and f <-- Func n are chosen uniformly at random

(a) Prove that if F is pseudorandom then it is weakly pseudorandom.

(b) Let F' be a pseudorandom function, and define .

Fk (x)=F`k(x)if x is even k . F`k(x+1) if x is odd

Prove that F is weakly pseudorandom, but not pseudorandom.

(c) Is counter-mode encryption instantiated using a weak pseudorandom function F necessarily CPA-secure? Does. it necessarily have indistinguishable encryptions in the presence of an eavesdropper? Prove your answers.

(d) Construct a CPA-secure encryption scheme based on a weak pseudorandom function. Hint: One of the constructions in this chapter will work.

This question from introduction to modern cryptography book chapter 3 question 3.20