If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b' I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including identity, or a constant function, or a random non deterministic function, or a function that encrypts a and b...) to an adversary $A$, that will give me back two bits $(a',b')$.

If by any chance, $A$ can guess correctly $(a,b)$ with a probability (taken over $a$, $b$, the randomness of $f$, and the randomness of the adversary) better than random, i.e:

$$\Pr[(a',b') = (a,b)] &gt; 1/4$$
can I say that either:


he is good to guess $a$, i.e. $\Pr[a' = a] &gt; 1/2$
or he is good to guess $b$, i.e. $\Pr[b' = b] &gt; 1/2$
or he is good to guess the xor of $a$ and $b$, i.e. $\Pr[a' \oplus b' = a \oplus b] &gt; 1/2$


?

NB: for sure the first two conditions are not enough, as if $f(a,b) = a \oplus b$, then the adversary that picks a random $a'$, and sets $b' := a' \oplus f(a,b)$ will guess $(a,b)$ with proba $1/2 &gt; 1/4$, and still the proba for him to get $a' = a$ will be 1/2 (and same for $b'$). I have the feeling that adding the last line is enough, because it "makes sure" that $A$ cannot guess also the correlation between $a$ and $b$, but not sure how to prove it that it's enough.

Thanks!
There are 4 possibilities, name them e1-e4:

e1  neither match
e2  a only matches
e3  b only matches
e4  both match


Now I restate what you want to prove: Suppose:

\begin{align*}
  \Pr[e4] &amp;\gt 0.25  &amp; \text{prob of correct guess} \\
  \Pr[e2] + \Pr[e4] &amp;\leq 0.5  &amp; \text{prob guess a correctly} \\
  \Pr[e3] + \Pr[e4] &amp;\leq 0.5  &amp; \text{prob guess b correctly}
\end{align*}

This implies that
\begin{align*}
  \Pr[e2] &lt; 0.25  \\
  \Pr[e3] &lt; 0.25  \\
  \implies \Pr[e2] + \Pr[e3] &lt; 0.5  \\
  \implies \Pr[e1] + \Pr[e4] &gt; 0.5,
\end{align*}
and then we notice that this is the probability that the XOR matches.