Proof that pseudorandom generators implies one-way function

Question

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

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!

Answer 1

One-way functions need not be invertible. A one-way function which is invertible is known as a one-way permutation.

Here is the definition of one-way function from Goldreich's primer:

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