Let $f$ be a binary function programmed at random; i.e. for any $x$ in its domain, $f(x)$ equals some $n$-bit value initially chosen at random. Such a function has the nice property that for any two values $x$ and x', if x \ne x', the values $f(x)$ and f(x') are statistically independent.
Now consider the following two algorithms:
Algorithm $A(y_1, y_2)$
- Select a random bit $b$.
- IF $b = 0$ THEN $y = y_1$ ELSE $y = y_2$.
- Run algorithm $B(y)$, and let $c$ be its output.
- IF $c = b$ THEN output "success" ELSE output "failure."
Algorithm $B(y)$
- Based on $y$, compute $x$.
- RETURN $f(x)$.
Define the following events:
- $E_1$: Algorithm $B$ computes the correct $x$ (based on $y$).
- $E_2$: Algorithm $A$ outputs "success."
Assume that $\Pr[E_2 \mid \neg E_1] = \frac{1}{2}$. In other words, if $B$ does not compute the correct $x$, it cannot solve the challenge of $A$ by any means better than random guess.
I want to prove that $\Pr[E_1] = \Pr[E_1 \mid b = 0] = \Pr[E_1 \mid b = 1]$.
Intuition: It seems that if the above equality does not hold, $B$ can solve the challenge by an approach better than random guess. But I can't figure out if this is correct.
Edit:
The "correct" $x$ is one that identifies $y_1$ from $y_2$, such that $f(x)$ equals 0 if $y=y_1$ and 1 otherwise. The values $y_1$ and $y_2$ come from outside, but they depend on $f$ such that the above condition holds. Since $f$ is random, and due to the design, algorithm $B$ cannot distinguish $y_1$ from $y_2$ unless it computes the "correct" $x$ and queries $f$ at $x$.
This is a simplified version of what I'm working with. In the real-world example, let $g$ be a one-way permutation (in fact, it also has an associated trapdoor). Each $y_i$ has two parts: the first part is some value $g(x)$, where $x$ is chosen according to some (unknown) distribution. the second part is $f(x)$ for $y_1$ and $r$ for $y_2$, where $r$ is a random $n$-bit value. In short:
$y_1 = ( g(x), f(x) )$
$y_2 = ( g(x), r )$
The algorithm $A$ is in fact testing the algorithm $B$ to see if it has the trapdoor. If so, $B$ can inverse $g(x)$ to obtain $x$, and then see if the latter part of $y$ equals $f(x)$.
The probabilities are taken over any random choice that is made, including the selection of the random bit $b$ and the function $f$. Moreover, the probabilities are taken over the choice of $y_1$ and $y_2$, as described above.