0
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ – Travis Mayberry Jul 24 '16 at 1:59
  • $\begingroup$ @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. $\endgroup$ – Student20 Jul 24 '16 at 2:16
  • $\begingroup$ 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. $\endgroup$ – Travis Mayberry Jul 24 '16 at 2:30
  • $\begingroup$ @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". $\endgroup$ – Student20 Jul 24 '16 at 2:45
  • $\begingroup$ @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$? $\endgroup$ – fkraiem Jul 24 '16 at 4:20
3
$\begingroup$

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} $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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