# Independence of answers to queries sent to a random oracle

Assume we have an algorithm which asks random oracle $\mathcal{O}$ $Q$ queries $u_1, \ldots, u_Q$. All queries are unique, $u_i \neq u_j$ for $i \neq j$. Queries $u_i$ are random variables, too.

What is the easiest (mathematically correct) way to see that the random variable $(\mathcal{O}(u_1),\ldots,\mathcal{O}(u_Q))$ has uniform distribution -- or -- that $\mathcal{O}(u_i)$ are independent random variables?

It looks like that the standard theorems covered in textbooks - like this one in Stinson - cannot be directly applied.

EDIT:

Here is more formal and simplified version of my question: $A$ is set of all random tapes (or private keys or something), $B$ is is set of all functions from, lets say, $\mathbb{Z}_q$ to $\mathbb{Z}_q$. $\mathcal{A}$ is some algorithm that has parameters $\omega \in A$ and random oracle $\mathcal{O}$ from $B$. We pick elements from $A$ and $B$ with uniform distribution.

For example, assume I want to calculate the probability $P((\omega, \mathcal{O}) \in A\times B| \mathcal{A}(\omega, \mathcal{O}) \text{ succeeds})$

This can be rewritten as

$P((\omega, \mathcal{O}) \in A\times B| \mathcal{A}(\omega, \mathcal{O}(u_1), \ldots, \mathcal{O}(u_Q)) \text{ succeeds})$

And then I have a Stinson's theorem which can be replaced by some other other "textbook" or citeable theorem.

The main goal is to prove $(\omega, \mathcal{O}(u_1), \ldots, \mathcal{O}(u_Q))$ has uniform distribution by citing something.

• Maybe I'm confused about your question, but that is just the definition of a random oracle. $\mathcal{O}$ responds to unique queries with uniformly random values, so a sequence of responses to unique queries will be uniformly random. – Travis Mayberry Jul 24 '16 at 1:59
• @TravisMayberry, sure, but how can we prove this formally? Queries $u_i$ are clearly not independent from each other and are not independent from the previous answers $\mathcal{O}(u_j)$ for $j<i$. For example, how to easily prove $P(\mathcal{O}(u_1) = a_1, \mathcal{O}(u_2) = a_2) = P(\mathcal{O}(u_1) = a_1) P(\mathcal{O}(u_2) = a_2)$ by citing some kind of theorem? $u_i$ are random variables, too. – Student20 Jul 24 '16 at 2:16
• There is no theorem necessary, it follows directly from the definition of $\mathcal{O}$. If all $u_i$ are unique then you can replace each $\mathcal{O}(u_i)$ with the output of a random function, then clearly the distribution of that sequence is random. – Travis Mayberry Jul 24 '16 at 2:30
• @TravisMayberry, I'll need to think a bit about your answer. It is obvious to me, but I'm having issues with putting it in a formal context. In my world oracle is just some function from the set of all functions. My probability space is $A\times B$ where $B$ is set of all oracles - functions from some $X$ to $Y$. So oracle $\mathcal{O}$ is random variable (that represents some function) and then I have a theorem which is basically Stinson's "theorem" without any kind of informal description. But I'm having troubles with putting everything in this "formalism". – Student20 Jul 24 '16 at 2:45
• @Student20 Before you make a formal argument for this, you have to have a formal definition of random oracles (and add it to your question). So what is yours? You speak of a probability space $A \times B$; what are $A$ and $B$? – fkraiem Jul 24 '16 at 4:20

Firstly, note that saying that the queries $u_1,\ldots,u_Q$ are distinct implies that they are not independent, for example, if $u_i=a$ then $u_j\neq a$ for all $j>i$.
Secondly, your argument indeed follows from the definition of a Random Oracle found in Stinson's book. Let $\mathcal{O}:\mathcal{X}\rightarrow \mathcal{Y}$ be a random oracle. That means that for every query $u$ that has not been queried before, it holds that $Pr[\mathcal{O}(u)=y]=1/|\mathcal{Y}|$ for every $y\in \mathcal{Y}$. Now, since $u_1,\ldots,u_Q$ are all distinct it follows that
For all $y\in\mathcal{Y}$ and $i\in[Q]: Pr[\mathcal{O}(u_i)=y]=\frac{1}{|\mathcal{Y}|}$
$\Rightarrow$ For all $(y_1,\ldots,y_Q)\in\mathcal{Y^Q}$: $Pr[\mathcal{O}(u_1)=y_1,\ldots, \mathcal{O}(u_Q)=y_Q]= \prod_{i=1}^Q Pr[\mathcal{O}(u_i)=y_i]=\frac{1}{|\mathcal{Y}|^Q}$