1
$\begingroup$

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[1]$ 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[1]$ 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).

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.