1
$\begingroup$

Let $f : \mathcal{U}_{2\lambda} \to \mathcal{U}_{2\lambda}$ be a OWF, and $G : \mathcal{U}_{\lambda} \to \mathcal{U}_{2\lambda}$ be a PRG with $\lambda$-bit stretch. Establish whether the following function $f' : \mathcal{U}_{\lambda} \to \mathcal{U}_{2\lambda}$ is one-way or not: \begin{equation*} f'(x) = f(G(x) \oplus (0^\lambda \| x)) \end{equation*}

I don't know how to solve this. Is this a OWF or not? I think that if $f$ is a OWF also $f'$ is.

$\endgroup$
1
  • 1
    $\begingroup$ Hint: a OWF can behave arbitrarily badly on a negligible fraction of its input space and a PRG can directly use part of its seed as a part of its output. $\endgroup$
    – Maeher
    Feb 6, 2022 at 19:15

1 Answer 1

1
$\begingroup$

Since I've just find out that this was an exercise I was trying to do yesterday I find out that what @Maeher said was what I need to start trying to solve this exercise, now I post in here my solution but I'm not sure it is correct 100%, sorry if this could result unethical but I'm a student trying to getting things correctly and help from experienced people on this topic (suggestion, how to study cryptography in general, where to find exercises and so on are really appreciated... at least from me):

I start supposing that: $$G(x) = x_1 ||...|| x_{\lambda-1} || G_1(x)$$

Where my $G_1$ is a $PRG$: $$G_1:\{0,1\}^\lambda \rightarrow\{0,1\}^{\lambda+1}$$

In this way when we apply $G(x) $ we will obtain always the first $\lambda-1$ bits of $x$ and $1$ pseudorandom bit. When we will make the $\oplus$ with the second part which is $x||0^\lambda$, we will obtain:

$$x_1||x_2||...||x_{\lambda-1}||U_1||U_\lambda$$

Now we can suppose that our function $f$ on input $x$ perform the following:

$$f(x) = x_1||x_2||...||x_\lambda||f_1(x_{\lambda}||...||x_{2\lambda})$$

Where $f_1:\{0,1\}^\lambda\rightarrow \{0,1\}^\lambda$ is a $OWF$

Now $f()$ is still a $OWF$ since I can't guess with non-negligible probability the second part generated from $f1$. But now $$f'(x) = x_1||...||x_{\lambda-1}||U_{\lambda+1}$$

So now with probability $1/2$ I can find the original $x$. Now should remain to prove that $G_1$ is a $PRG$ and that $f_1$ is a $PRF$, both proof should be reduction proof, right?

$\endgroup$
1
  • $\begingroup$ Your $G$ is definitely not a PRG! $\endgroup$
    – Mikero
    Sep 29, 2022 at 0:27

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.