Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
What is the difference between Pseudo Random Functions and Random Oracles?
$\newcommand{\str}[1]{\{0,1\}^{#1}}$
Roughly speaking, a pseudo-random function is to a random oracle what computational encryption scheme is to one-time pad -- the former is a computational analogue of the information theoretic latter.
For simplicity, let's fix the domain and co-domain to be the set of all $n$-bit strings. Let's consider the set $\mathcal{F}_n$ of all functions that map $n$ bits to $n$ bits, i.e., $$\mathcal{F}_n=\left\{f:\str{n}\rightarrow\str{n}\right\}.$$ A random oracle on $n$ bits is a function sampled uniformly at random from $\mathcal{F}_n$ that is presented as an oracle. That is, any machine that has access to the random oracle can (by writing on its oracle tape) query it on inputs and will receive the value of the function in return (written back on the oracle tape). Note that since there are $|\mathcal{F}_n|=(2^n)^{2^n}$ such functions, the probability that a particular $f\in\mathcal{F}$ is chosen is $1/|\mathcal{F}_n|$. Moreover, as it is picked uniformly at random, a random oracle is incompressible and the only way to explicitly represent it is via its function table (which has a size of $n2^n$ bits). (This is why it is presented as an oracle.)
A pseudorandom function, on the other hand, is a family of functions that "appear" random to a computationally bounded machine. More formally, it is a family of explicit, efficiently-computable keyed functions on $n$-bit strings $$\mathcal{G}_n=\{g_k:\str{n}\rightarrow\str{n}\}_{k\in\str{n}}$$ that is pseudo-random: for any computationally bounded machine the worlds with oracles $$f(\cdot):f\leftarrow\mathcal{F}_n ~~(\text{random})$$ and $$g_k(\cdot):g_k\leftarrow\mathcal{G}_n\stackrel{\Delta}{=}k\leftarrow\str{n}~~(\text{real})$$ appear indistinguishable. In other words, it is indistinguishable from a random oracle for computationally-bounded machines. Note that $\mathcal{G}_n\subset\mathcal{F}_n$ and, more importantly, the number of functions in $\mathcal{G}_n$ is much smaller than that in $\mathcal{F}_n$: $$|\mathcal{G}_n|=2^n\ll|\mathcal{F}_n|=(2^n)^{2^n}$$ However, by pseudo-randomness, a computationally-bounded machine should not be able to tell this.
The advantage of using pseudo-random functions instead of random functions is that they have a succinct representation: once the family $\mathcal{G}_n$ (which we require to be explicit and efficiently-computable) is fixed the function is represented by the key $k$ and therefore its explicit representation is simply $n$ bits long.
Now, to answer the questions
Is the difference only about the domain of PRFs and Random Oracles, former having a fixed domain and latter can act on any input as long as it is well formatted?
Not necessarily, one usually talks about an ensemble of PRFs, that is one for every bit length: $\{\mathcal{G}_n\}_{n\in\mathbb{N}}$.
Having a Random Oracle is a stronger assumption, why is that?
That question can be interpreted in different ways. Assuming an object $B$ is said to be stronger than assuming another object $A$ if $B$ implies $A$ (but the other direction does not hold or is unknown). For example, DDH is a stronger assumption than CDH, or IND-CCA is a stronger assumption than IND-CPA. In this sense, it is not possible to directly compare a random oracle to a PRF since the former lives in a relativised world (i.e., a world with oracles), whereas the latter need not. It unlikely that a construction of PRF from random oracle could be explicitly and succinctly described (as @Ievgeni points out) because of the incompressibility of the random oracle. On the other hand, one could talk about simulating a random oracle using a PRF -- however, to an unbounded adversary this would appear distinguishable.
That said, a protocol that is based on a PRF is preferred to one that is based on random oracles since in practice we do not know how to instantiate random oracles. One could replace it with a concrete hash function like SHA3 (i.e., the random-oracle methodology), but this protocol only has heuristic guarantees (discussions here and here) and in some cases known to be insecure (discussion here). However we do know how to (explicitly) construct pseudo-random functions from the mild assumption that one-way functions exist (discussion here).
$\;\;\;$ No. $\:$ A PRF involves a secret key; a Random Oracle doesn't.
$\;\;\;$ One can construct a PRF from a random oracle.
Random oracles are purely random. They don't involve any cryptographic functions. They could be considered as the set of all functions that map an input to output. In that sense, a PRF could be considered a subset. Random oracles are stronger assumptions because they are totally random. The measure of a secure PRF is how indistinguishable it's from a Random Oracle. The more indistinguishable the better.
