This was a question from my exam yesterday. We have that $G:\{0, 1\}^n\rightarrow \{0, 1\}^{2n}$ and $$G(x)=x\mathbin\|[x^2 \bmod 2^n]$$ with $x$ is uniform and $|x|=n$, give an efficient distinguisher $D(w)$ that shows that $G(x)$ is not a PRG.

After writing a program that shows all values $[x^2 \bmod 2^n]$ can take for some fixed $n$, I found that there is a mirror pattern in these values, but I don't see how to mathematically prove this.

  • $\begingroup$ By mirror pattern, do you mean that $x^2 \equiv (2^n-x)^2 \pmod{2^n}$? That's easy to show; $(2^n-x)^2 \equiv (-x)^2 \equiv (-1)^2x^2 \equiv x^2$ $\endgroup$
    – poncho
    Oct 22, 2020 at 13:20

1 Answer 1


Given as input a $2n$-bit string $x||y$, the distinguisher $D(x||y)$ outputs 1 if $y = x^2 \bmod{2^n}$ and $0$ otherwise.

If $x||y$ is uniformly distributed over $\{0,1\}^{2n}$, the probability that $y=x^2 \bmod{2^n}$ is $2^{-n}$. If $x||y$ is distributed as $G(X)$ where $X$ is uniform over $\{0,1\}^n$, the probability that $y=x^2 \bmod{2^n}$ is 1. The distinguishing advantage of $D$ is $1-2^{-n}$, which is non-negligible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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