In "Foundations of Cryptography, Volume 1" by Oded Goldreich, chapter 3.3.6 states the following theorem:

Let $G$ be a pseudorandom generator with expansion factor $l(n) = 2n$. Then the function $f\colon \{0,1\}^* \to \{0,1\}^*$ defined by letting $f(x,y) \stackrel{\text{def}}= G(x)$, for every $|x| = |y|$ is a strongly one-way function.

The theorem is proved by reduction, with given an inverter $A$ construct the following distinguisher $D$: $$D(\alpha) = 1 \quad\text{iff}\quad f(A(\alpha)) = \alpha$$ (where $D$ distinguishes between $U_{2n}$ and $G(U_n)$). There is one part of the proof I do not understand:

[...] by $f$'s construction, at most $2^n$ different $2n$-bit-long strings (i.e., those in the support of $G(U_n)$) have pre-images under $f$. Hence $\Pr[D(U_{2n}) = 1] = \Pr[f(A(U_{2n})) = U_{2n}] \leq 2^{-n}$.

Why don't all $2^{2n}$ possible $2n$-bit-long strings have preimages under $f$?


Let $n\in \mathbb{N}$, and fix $x,y \in \{0,1\}^n$, $f(x,y)=G(x) \in \{0,1\}^{2n}$. By $f$'s definition, $$\forall x,y_1,y_2 \in \{0,1\}^n,\;f(x,y_1)=f(x,y_2).$$ Hence, if we define the function $f'\colon\{0,1\}^n\to \{0,1\}^{2n}$ by $f'(x)=f(x,0^n)$ we get that $\operatorname{Im}(f)=\operatorname{Im}(f')$ and $\lvert\operatorname{Im}(f')\rvert\le \lvert\{0,1\}^n\rvert=2^n$.

|improve this answer|||||

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.