# Whether this PRG is secure or not

This is the question.

Suppose $G$ is a secure PRG with expansion factor $\ell(n) = 2n$ such that $n$ is a security parameter. Is it always the case that, $G'\colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^{3n}$, defined by, $G'(s) := G(s) || \bar{s}$ is also a PRG ? Here, $||$ represents concatenation of bit strings, and $\bar{s}$ represents the bitwise complement of s (e.g., if $s$ is $100010$, then $\bar{s}$ is $011101$).

My unsure attempt of solving this says it is a broken PRG (i.e. not secure) because, I always check on following points for a construction to be a secure PRG: .. $\ell(n) > n$, .. efficient, .. deterministic, &, .. pseudorandom, i.e., $| Pr[D(G(s) = 1] - Pr[D(r) = 1] | \leq \operatorname{negl}(n)$.

And the construction in question failed in passing the pseudorandomness.

My attempt was, let's say $w$ is final output (of $3n$ size, which is given to the distinguisher) and I leaked the first bit of my construction (i.e., only $n-1$ bits i.e., $s[2:n]$, are passed into G and are expanded to $2n-1$ bits) such that first bit of $w$, i.e., $w$ is complement of $w[2n+1]$ (because last $n$ bits are simply concatenated and $2n+1$ refers to the first bit among the last $n$ bits).

XORing $w$ with $w[2n+1]$ gives us $1$ which clearly depicts inefficient randomness and failure of computational adversarial indistinguishability (i.e., ability to guess bits better than a probability of $1/2$ exist).

I'm unsure whether this is the right approach though. When we are talking about PRGs, my knowledge says we cannot modify/control the seed (nor we can see it, though we control its size), and then we know that $G$ will output $2n$ bits (i.e., an expansion factor of $2|s|$). Is it possible to explicitly only send $s[2:n]$ bits to a PRG to get the expanded $2n-1$ bits back and then attach that first bit in the starting of the pseudorandom string ?.

What's your verdict towards my approach ?. Thank you, for your time &, I really liked you read it.

I have another explanation that proves $G'$ is secure, however, I'm sure with a probability of 50% that, that is not right and rather this is right (i.e. $G'$ is not secure).

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Mar 14 '16 at 11:30

Your intuition that $G'$ is insecure is correct, but your approach is a bit off. In the PRG security game, the adversary is not allowed to influence the choice of seed, which is always chosen uniformly at random.
To attack $G'$, notice that given just $G'(s)$, you can reconstruct $s$ from $\bar{s}$. Therefore a distinguisher, when given a challenge output $w$, can compute $G'(\bar{w}[2n+1] \cdots \bar{w}[3n])$ and check whether this gives $w$.