3
$\begingroup$

Random oracles don't exist, but aren't PRFs essentially indistinguishable from them? So why can't we substitute pseudorandom functions wherever we use random oracles?

And if we can do this, why is there any controversy over substituting hash functions for random oracles, when we can instead use pseudorandom functions which do exist and are practically the same as random oracles?

$\endgroup$
  • $\begingroup$ hash functions are considered PRFs and it's common practice to use PRF (= hash functions) as random oracles. Sample? OAEP. Security proof requires random oracles, which are "instantiated" as hash functions. $\endgroup$ – SEJPM Jun 3 '15 at 20:51
  • 2
    $\begingroup$ PRFs are "essentially indistinguishable from them" to parties that don't know the key. $\hspace{1.26 in}$ $\endgroup$ – user991 Jun 3 '15 at 21:04
2
$\begingroup$

Yes, when we're instantiating some crypto primitive that says 'insert Random Oracle here', we will in practice insert a PRF.

Now, you ask, why is that even slightly controversal? Well, there are known constructions that are secure with a Random Oracle, but not secure with any specific PRF, see this paper for an example. This has been taken by some as proof that the Random Oracle model ought not be trusted at all (as proof within that model need not apply in the real world).

On the other side of the argument, other people have pointed out that these constructions are highly artificial, and that attempts to avoid the Random Oracle model has resulted in worse security at times; see this paper to see this argument spelled out.

$\endgroup$
  • 2
    $\begingroup$ In fact, there are "constructions that are secure with a Random Oracle, but not secure with any specific" efficiently-computable function, even if that function is not a PRF. $\;$ $\endgroup$ – user991 Jun 3 '15 at 21:02

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.