4
$\begingroup$

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)] > 1/4$$ can I say that either:

  • he is good to guess $a$, i.e. $\Pr[a' = a] > 1/2$
  • or he is good to guess $b$, i.e. $\Pr[b' = b] > 1/2$
  • or he is good to guess the xor of $a$ and $b$, i.e. $\Pr[a' \oplus b' = a \oplus b] > 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 > 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!

$\endgroup$
4
$\begingroup$

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] &\gt 0.25 & \text{prob of correct guess} \\ \Pr[e2] + \Pr[e4] &\leq 0.5 & \text{prob guess a correctly} \\ \Pr[e3] + \Pr[e4] &\leq 0.5 & \text{prob guess b correctly} \end{align*}

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

$\endgroup$
  • $\begingroup$ Much simpler indeed, thanks! $\endgroup$ – tobiasBora Apr 8 at 7:08
  • $\begingroup$ Nice. Also, this shows the function $f$ is really irrelevant. Basically, any r.v. $(A,B)$ such that $\Pr[(A,B)=(a,b)] > 1/4$ (over the randomness of $(A,B)$ and $(a,b)$ must satisfy $\max(\Pr[A=a],\Pr[B=b],\Pr[A\oplus B=a\oplus b]) > 1/2$. $\endgroup$ – Clement C. Apr 8 at 10:54
3
$\begingroup$

So I found a simple proof, but the proof is a bit fastidious to write (the symmetries make it easy to check however). If you have a more elegant/fundamental way to prove it, let me know! Or if it's a well not result as well.

So the proof goes that way: first let's define this array:

b\a |   0   ||   1   |
_____________________
  0 | c | d || g | h |
    | e | f || i | j |
_____________________
  1 | k | l || o | p |
    | m | n || q | r |
_____________________

To read it, each big column (resp. line) represents the 2 values that $a$ (resp. $b$) can take: $0$ and $1$. Then, the value of each sub-cell represents the probability to output a given guess $(a',b')$ when $a$ and $b$ have the value of the big column. The top left value is for 00, top right is for 10, bottom left is for 01, and bottom right is for 11. For example, $\Pr[a'b' = 00 | a=0 \text{ and } b=0] = c$, $\Pr[a'b' = 01 | a=1 \text{ and } b=0] = i$...

Then, from that you can easily derive some "normalisation" equation, like $c+d+e+f=1$, $g+h+i+j=1$, $k+l+m+n=1$, and $o+p+q+r=1$.

Now, since $(a,b)$ has been sampled uniformly at random, saying that $\Pr[a' = a] \leq 1/2$ is equivalent to saying that $c+e+k+m+h+j+p+r \leq 2$, $\Pr[b' = b] \leq 1/2$ is equivalent to $c+d+g+h+m+n+q+r \leq 2$, and finally $\Pr[a' \oplus b' = a \oplus b] \leq 1/2$ is equivalent to $c+f+o+p+m+l+i+h \leq 2$. So you sum these three equations, and you get:

$$3c + d + e+f+g+3h+i+j+k+l+3m+n+o+p+q+3r \leq 6$$

Finally, you just use the normalisation equation to get rid of all the letters, except for $c,h,m$ and $r$. You simplify it to $c+h+m+r \leq 1$, which is exactly equivalent to say that $\Pr[(a',b') = (a,b)] \leq 1/4$ ! Done ;-) If you have a more direct way, let me know!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.