Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 4 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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