# Probabilistic analysis of two algorithms

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

1. Select a random bit $b$.
2. IF $b = 0$ THEN $y = y_1$ ELSE $y = y_2$.
3. Run algorithm $B(y)$, and let $c$ be its output.
4. IF $c = b$ THEN output "success" ELSE output "failure."

Algorithm $B(y)$

1. Based on $y$, compute $x$.
2. 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.

-
I wasn't able to pick a better title. Please feel free to edit it. – M.S. Dousti Sep 13 '11 at 2:11
What does "the correct $x$" mean? Where does the input to $A$ come from? Is it random? What can be assumed about its distribution? What is known about the unspecified "computation" in $B$? – Henning Makholm Sep 13 '11 at 2:26
@Henning: 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$. – M.S. Dousti Sep 13 '11 at 2:33
I don't understand how one computes $x$ "based on $y$" and then returns a bit "based on $f(x)$". Do you intend algorithm B to be a black box, i.e. you want to perform the analysis for any possible $B$ that maps $y$'s to bits? – Rahul Sep 13 '11 at 3:39
@Sadeq: Yes, that's much clearer; you should edit that into the question. – joriki Sep 13 '11 at 8:44