What is an oracle adversary? I'm trying to figure out block ciphers and this is the first time I've encountered the term "oracle adversary". It appears in the context of defining a PRP and a PRF. Can someone please explain what an "oracle adversary" can/cannot do? Or maybe help out with a link or something (I've tried looking it up myself, but I could only find the RSA Laboratories RSAES-OAEP Dictionary, which doesn't really clear things up).

Here's the context:


  (Pseudo-Random Function). A family of functions F : {0, 1}^k × {0, 1}^n → {0, 1}^n is pseudo-random if for all polynomial time oracle adversaries $A$, $$
\left|
\Pr_{K} \left[ A^{F_K(\cdot)} = 1 \right] -
\Pr_{R:\{0,1\}^k \rightarrow \{0,1\}^n} \left[ A^{R(\cdot)} = 1 \right]
\right|
$$ is negligible.
This is a common abstraction throughout theoretical crypto that is borrowed from complexity theory.  It is a formalization of the idea that an adversary is only allowed to attack a primitive (PRF, PRP, etc.) by observing its "input/output behavior."

Formally, adversaries are (often implicitly) thought of as Turing machines, circuit families, or whatever formal model of computation you like.  And when we say that an adversary is given "oracle access" to, say, $F_K(\cdot)$, we mean that it has a special state that it can enter, where it provides some $x$ and then obtains $F_K(x)$.  Note that the adversary is given complete freedom to choose the $x$: It can repeat the same $x$, query at random $x$, or choose the $x$ with some structure.

You can formalize this with Turing machines by having a special oracle tape and state that "magically" overwrites $x$ with $F_K(x)$, or with circuit families you can think of these queries as special $F_K$-gates, or if your adversary is expressed in the C programming language then it could have the ability to call a function from a library that
computes $F_K(\cdot)$.  The details of the formalization are rarely important to crypto.

Beware the subtlety where in definitions like PRF security, the adversary always "knows" the $F$ that it is attacking, due to the order of quantifiers.  In those definitions, the adversary is given input/output access to a function that is either $F_K(\cdot)$ (for a "known" $F$ but "unknown" random key $K$), or to an "unknown" random function with the same
domain and range.