0
$\begingroup$

How to formally argue that there exists no efficient $A$ who can come up with a $e$ such that $$\begin{align}x&=PRF(e,0) \land \\ y &= PRF(e,1) \land \\ x &= H(y)\end{align}$$ where $H$ is a secure hash function and $|x|=|y|=\ell$?

Note that it's easy to argue that if $A$ just guesses randomly, the success probability for each guess is negligible (something like $\frac{1}{2^{\ell}}$). But how to argue there is no better algorithm than guessing?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

But how to argue there is no better algorithm than guessing?

Show that, if there is a better algorithm than guessing, you can distinguish the PRF from random.

Improve this answer
$\endgroup$
2
  • $\begingroup$ can you elaborate a little bit. I know the rough idea but I find it tricky to be very precise. $\endgroup$
    – qweruiop
    Dec 16, 2020 at 3:14
  • $\begingroup$ Maybe you can look at some reduction arguments in the crypto book. $\endgroup$
    – ambiso
    Dec 16, 2020 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.