# 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.

-
Could you post a quote from the source in question so we can get the correct context? –  mikeazo Nov 30 '12 at 15:19
(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: here goes a semantic security advantage statement, in which A is the algorithm the adversary uses, and which I have no idea how to format And I'm really, really sorry for the poor formatting. –  Patrunjel Nov 30 '12 at 15:22
I've edited in what seems to have been your source based on a Google search, please validate or correct as appropriate. –  Gilles Dec 12 '12 at 17:43

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.