Question

Let G be a pseudorandon generator with expansion factor l(n) > 2n. In each of the following cases, say whether G' is necessarily a pseudorandom generator. If yes, give a proof; if not, show a counterexample. def def (a) Define G'(s) G($1.5[n/21), where s = $1... Sn. (b) Define G'(s) G(018|||s). (c) Define G'(s) G(s) || G(s + 1). (Note that given a real number x, the ceiling function [x] gives the least integer greater than or equal to x.) def

Answer 1

(a) is a pseudorandom generator.

Explanation:

(a) We first show that f' is negligible. Let therefore e be a natural number. We have to show that there is an N' such that for all n > N' it holds that f'(n) <n-e. As f is negligible and p' (n) = 24.(n+1) is a polynomial we conclude that there is an N such that for all n > N it holds that f(n) <p'(n)-1. Now let N' := 2N +1. We have for all n > N': s'(n) =s (ED) <' ([])* = (2 : (13] +1))*<(2* . ())+= =n Next we proof that G' is a PRG. Let l' be the expansion factor of G'. It holds that l'(n) = ([3]) > 2([3])+1 > n. Now let D an arbitrary ppt distinguisher. As G is a PRG it holds that

{0,134) Prs+40.13"[D(G'(9)) = 1] – Per+(0,136(n) [D(r) = 11 14, [D(G(8)) = 1] – Pr +(0,136(n) [D(r) = = P1-40.1314.1 [D(G(s)) = 1] – PI4=(0,13(14)[D(r) = < negl (19) where negl is a negligible function. As negl'(n) := negl ( 3]) is also negligible the proof is finished

______________________________________________________________________________________

(b) is not necessarily a PRG because otherwise
G'(01||$) = G(0)
would also be a PRG which is clearly not the case: As D knows G and its expansion factor it can on input r just check whether r = G(0n ) for n with `(n) = |r|. Then D wins with probability 1 − 2 −|r| which is not negligible.

_______________________________________________________________________________________

(c) is not necessarily a PRG. Explanation:

G5 is not always a PRG. Assuming it is G2(3)||G2(3+1) would also be a PRG. But for every s whose last bit equals zero we have that G2(3)||G2(8 + 1) G($1 ... 53–11)||0||G(81 ... 53–11)||1 ,that is, on input r e {0,1}2n a distinguis- her just has to check whether rı...In-1 = Pn+1 ... 12n-1 and therefore the winning probability is at least 3(1 – 2-in-1)) which is not negligible.