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.

  • $\begingroup$ Could you post a quote from the source in question so we can get the correct context? $\endgroup$
    – mikeazo
    Commented Nov 30, 2012 at 15:19
  • $\begingroup$ (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. $\endgroup$
    – Patrunjel
    Commented Nov 30, 2012 at 15:22
  • 1
    $\begingroup$ I've edited in what seems to have been your source based on a Google search, please validate or correct as appropriate. $\endgroup$ Commented Dec 12, 2012 at 17:43

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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