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?

$\endgroup$
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.

$\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 '20 at 3:14
  • $\begingroup$ Maybe you can look at some reduction arguments in the crypto book. $\endgroup$
    – cisnjxqu
    Dec 16 '20 at 14:41

Your Answer

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

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