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?



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


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.