Given a OW function $f:\{0,1\}^n\to\{0,1\}^n$ with hardcore predicate $h(x)$, you can build a PRG $G$ by setting $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$ The expansion condition for $G$ is trivially satisfied (the seed $s$ has length $n$, while the string $f(s)\Vert h(s)$ has length $n+1$). How can I show that $G$ is also pseudorandom, that is, for any probabilistic poly-time distinguisher $\mathcal D$ $$\mid\Pr[\mathcal D(G(s)=1]-\Pr[\mathcal D(r)=1]\mid\le\epsilon(n), \quad r\leftarrow \{0,1\}^{n+1} $$ where $\epsilon(n)$ is a negligible function of $n$?

  • 1
    $\begingroup$ @kelalaka Sorry, is your comment about my deleted question (the necessity of the one-time requirement for the one-time pad)? If so I have found a satisfactory answer here already. $\endgroup$ Dec 14, 2021 at 20:17
  • $\begingroup$ Welcome to Cryptography.SE. Usually search first then ask. The usual approach for this type of questions assume that there is a distinguisher for $G$ then there is one for $f$, too. $\endgroup$
    – kelalaka
    Dec 14, 2021 at 20:24
  • $\begingroup$ @kelalaka Could you elaborate on that? $\endgroup$ Dec 14, 2021 at 20:26
  • 1
    $\begingroup$ It’s not enough for $f$ to be a one-way function, but it does suffice for it to be a one-way permutation (i.e, a bijection). $\endgroup$ Dec 14, 2021 at 23:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.