# Proof that pseudorandom generators implies one-way function

I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions.

My understanding is that pseudorandom generators are defined as

A function $$G_l:\{0,1\}^l\to\{0,1\}^m$$ is a pseudorandom generator if all of the following hold:

a. $$l

b. $$G_l\in\mathbf P$$

c. For any polynomially-sized circuit $$C$$, $$\left|\Pr_{x\sim\text{Unif}\{0,1\}^l}[C(x)=1]-\Pr_{x\sim\text{Unif}(D)}[C(x)=1]\right|<\text{poly}(n),$$ where $$D$$ is the image of $$G_l$$.

and that one-way functions are defined as:

A function $$f:\{0,1\}^n\to\{0,1\}^n$$ is a one-way function if all of the following hold:

1. $$f$$ is invertible
2. $$f\in\mathbf P$$
3. For any polynomially-sized circuit $$C$$,

$$\Pr[f(C(f(x))=f(x)]<\text{poly}(n).$$

Question 1: Looking at definitions for one-way functions above, I assume that the notation $$f:\{0,1\}^n\to\{0,1\}^n$$ refers to a family of functions $$\mathcal F=\{f_n\}_{n\in\mathbf N}$$, where each $$f_n$$ is an invertible function $$\{0,1\}^n\to\{0,1\}^n$$. (And analogously for the defintion of pseudorandom generators.) Is this assumption correct?

The proof that pseudorandom generators implies one-way functions given on the Wikipedia page starts off with:

Consider a pseudorandom generator $$G_l:\{0,1\}^l\to\{0,1\}^{2l}$$. Let's create the following one-way function $$f:\{0,1\}^n\to\{0,1\}^n$$ that uses the first half of the output of $$G_l$$ as its output. Formally, $$f(x,y)\to G_l(x)$$

Question 2: What exactly is this saying? It looks like $$|x|+|y|=n$$, so I'll assume for now that $$|x|=l=n/2$$, in which case $$G_l(x)$$ outputs a string of length $$2l=n$$. But if $$G$$ ignores $$y$$, how can $$f$$ be injective?

Thanks!

A function $$f\colon \{0,1\}^* \to \{0,1\}^*$$ is one-way if it can be computed in polynomial time, and is hard to invert: for every polynomial time algorithm $$A$$, $$\Pr_{x \in \{0,1\}^n}[f(A(f(x),1^n))) = x] \text{ is negligible}.$$
(A function $$\epsilon(n)$$ is negligible if $$\epsilon(n) = O(1/n^k)$$ for all $$k$$.)
As you can see, there is no promise that $$|f(x)| = |x|$$; it could be that $$f(x)$$ is longer than $$x$$, or even shorter than $$x$$ (which is why we feed $$A$$ the auxiliary input $$1^n$$, an arbitrary string of length $$n$$).