Is this construction a OWF?

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.

@Maeher long enough =?

@kelalaka Any constant fraction will do. Say 1/2 of the input length for a concrete construction.

@Maeher should I build a counterexample with your hint?

That could work.

@Maeher i think that based on your hint we can construct the function $f^*(x_1||x_2) = f(G'(x_1)||x_2 \oplus (0^{\lambda}||x1||x2))$ and if we have $|G'(x_1)| = \lambda + |x1|$ we also have that the second part of the input of $f$ is always zero (because of the xor). Therefore, the probability of finding a pre-image of $f^*$ is limited over the choice of $x_1$ in this case. But we need a large enough $x_1$ to have a PRG... Considering $|x_1|=\lambda/2$ like in your example, we still have a probability of finding a pre-image of $2^{-\lambda/2}$ that should still be negligible.

Are you sure the parameters? does $f^*$ from $2\lambda$ or $\lambda$ since $G$ from $\lambda$. Also @Maeher meant to write $G(x_1\|x_2) = G'(x_1)||x_2$, that is a construction for a pathetic example $PRG$ to ....

@kelalaka $f*$ takes an input of length $\lambda$, that can be $x_1||x_2$. But i don't get where the counterexample could be, considering that $G(x_1||x_2) = G'(x_1)||x_2 is secure for sufficiently large $x_1$.

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.

So I thought about constructing a "dumb" OWF $f'(x) $ that in case that the last $\lambda$ bits of its input are null outputs the input itself or, otherwise, the normal output of $f$. The function should still be OWF because the probability of having a random input ending with $0^{\lambda}$ is $2^{-\lambda}$ and hence negligible. But even if the attacker sees $G'(x)\oplus(0^{\lambda}||x)$, what can he do with it? How can he deduct $x$? (By the way, thanks a lot for the help!)

There are other ways for a OWF to behave stupidly. Remember, you do not need to find $x$. You just need to find *a* preimage, not the *same* preimage.

I think I got it! I construct a OWF $f'$ that returns $1^{2\lambda}$ if the last ${\lambda/2}$ bits of the input are $0$ and the output of a normal OWF $f$ otherwise. $f'$ is a OWF because the probability of having a random input ending with $0^{\lambda/2}$ is $2^{-\lambda/2}$ but the construction $f*$ can be easily broken because the attacker will always receive $1^{2\lambda}$ and, therefore, he only needs to send a preimage ending with $0^{\lambda/2}$ bits to win the game. Is it correct?

Your counterexample should work. It is good practice to actually write down the proofs that the $f$ and $G$ you construct are actually a secure OWF and PRG respectively. Your attack also works but is more specific than necessary. $f^*(x_1\|x_2) = f(G(x_1\|x_2)\oplus(0^\lambda\|x_1\|x_2) = f((G'(x_1)\|x_2)\oplus(0^\lambda\|x_1\|x_2) = f((G'(x_1)\oplus 0^\lambda\|x_1) \|0^{\lambda/2}) = 1^{2\lambda}$ so $f^*$ is a *constant* function and *any* $2\lambda$ value is a valid preimage.

I sit in a Tesla and translated this thread with Ai: