2
$\begingroup$

I'm reading an unpublished paper in which the author makes the following conclusions several times:

Assumptions: finite probability space, $H$ is a random oracle, $X$ and $Y$ are two (not necessarily independent) random variables, $X \neq Y$ for every possible outcome.

Conclusion: $H(X)$ and $H(Y)$ are independent and uniformly distributed random variables.

"Proof" (not actually stated as such): obvious, $P(H(x) = a|D) = P(H(x) = a)$ for every event $D$.

Is this a valid conclusion? Are there any counterexamples which don't explicitly involve events $D$ similar to $H(x) \neq a$?

$\endgroup$

1 Answer 1

5
$\begingroup$

If $H(X)$ and $H(Y)$ were not evaluated as a part of selecting $X$ and $Y$, then yes; the assumption of a random Oracle is that $H(Z)$ is an independent and uniformly distributed variable for every new (not previously submitted to the Oracle) value $Z$.

If this isn't the case, then this need not hold. One obvious counterexample is:

$X := 1; Y := 2 \textit{ if H(1) < H(2)}\\ X := 2; Y :=1 \textit{ otherwise}$

$\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.