0
$\begingroup$

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.

$\endgroup$
1
  • $\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 '20 at 13:20
2
$\begingroup$

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.

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