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.

Improve this question
$\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 4:20

1 Answer 1

Reset to default
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} $

Improve this answer
$\endgroup$

Your Answer

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

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