# Tag Info

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{... 9 This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit). First, I assume that when writing$Pr[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both$x$and$y$. Now, the claim is that there exists a subset of$x$values of a large enough size'' so that for every$x\$ in ...