1
$\begingroup$

If $f:\{0,1\}^n \to \{0, 1\}^n$ is a one-way function, $G:\{0, 1\}^n \to \{0, 1\}^m$ is a pseudorandom generator, and $U_m$ is the uniform distribution over $m$-bit strings. Is the joint distribution $(f(X), G(X))$ computationally indistinguishable from $(f(X), U_m)$, for uniformly chosen $X$?

$\endgroup$
1
  • 2
    $\begingroup$ Hint: can you think of a pair $f$, $G$ where it is distinguishable? $\endgroup$
    – poncho
    Commented Nov 3, 2014 at 23:18

1 Answer 1

3
$\begingroup$

The person who asked the original questions seems to have deleted the account, so here's a full solution for future reference instead of just a hint:

Assume that $G':\{0,1\}^{n-1}\to\{0,1\}^{m-1}$ is pseudorandom and $f':\{0,1\}^{n-1}\times \{0,1\}^{n-1}$ a one-way function. We construct the functions $f:\{0,1\}^n\to \{0,1\}^n$ and $G:\{0,1\}^n\to \{0,1\}^m$ as follows

$$f(x) = x_1f'(x_{2,\ldots,n}),\;\; G(x)=x_1G'(x_{2,\ldots,n}),$$

where $x_1$ denotes the first bit of the input and $x_{2,\ldots,n}$ the remaining bits. Clearly, $f$ is one-way and $G$ is a pseudorandom generator. As distributions, we then have

$$G(U_n) = U_1 G'(U_{n-1})$$

and

$$f(U_n) = U_1 f'(U_{n-1}).$$

It's then trivial to construct a distinguisher for $(f(U_n),G(U_n))$ and $(f(U_n),U_m)$. The distinguisher gets as input a pair $(x,y)$ and checks whether the bits $x_1=y_1$. If this holds it will return $1$ and if $x_1\neq y_1$ it returns $0$. If the input comes from $(f(U_n),G(U_n))$ we always return $1$ and in the other case we return $1$ by probability $1/2$. The distinguisher therefore has advantage $1/2$, so the distribution $(f(U_n),G(U_n))$ is clearly not pseudorandom.

$\endgroup$

Your Answer

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