Given the OWF function $f: \{0,1\}^{2\lambda} \rightarrow \{0,1\}^{2\lambda}$ and the PRG $G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$, is the following function $f^*$ a OWF?

\begin{align} f^*: \{0,1\}^{\lambda} &\to \{0,1\}^{2\lambda}\\ x &\to f^*(x) = f(G(x)\oplus(0^{\lambda}||x)) \end{align}

My idea is that it is secure, mainly because the function $f$ is a OWF itself, but I haven't been able to prove it. Moreover, I thought that the collision probability of its input might be involved, but it's nothing more than intuition.

  • 1
    $\begingroup$ Hint: Let $G'$ be a PRG. Then $G$ defined as $G(x_1\|x_2) = G(x_1)||x_2$ for long enough $x_1$ is also a PRG. $\endgroup$
    – Maeher
    Jan 11 at 12:41
  • $\begingroup$ @Maeher long enough =? $\endgroup$
    – kelalaka
    Jan 11 at 12:50
  • $\begingroup$ @kelalaka Any constant fraction will do. Say 1/2 of the input length for a concrete construction. $\endgroup$
    – Maeher
    Jan 11 at 15:18
  • $\begingroup$ @Maeher should I build a counterexample with your hint? $\endgroup$
    – zingiest
    Jan 11 at 16:03
  • 1
    $\begingroup$ Hint 2: A OWF is only guaranteed to be hard to invert if the inputs are sampled according to the uniform distribution. A distribution that only contains inputs that end in many zeroes is very far (and easily distinguishable from) uniform. $\endgroup$
    – Maeher
    Jan 12 at 14:08

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.