<p>There are 4 possibilities, name them e1-e4:</p>

<pre><code>e1  neither match
e2  a only matches
e3  b only matches
e4  both match
</code></pre>

<p>Now I restate what you want to prove: Suppose:</p>

<p><span class="math-container">\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*}</span></p>

<p>This implies that
<span class="math-container">\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*}</span>
and then we notice that this is the probability that the XOR matches.</p>

CC BY-SA 4.0
2019-04-08T07:08:33.413Z
Much simpler indeed, thanks!
tobiasBora
CC BY-SA 4.0
2019-04-08T10:54:33.670Z
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$.
Clement C.
CC BY-SA 4.0
2019-04-07T23:52:21.027Z
2019-04-07T23:52:21.027Z
usul
<p>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.</p>

<p>So the proof goes that way: first let's define this array:</p>

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

<p>To read it, each big column (resp. line) represents the 2 values that <span class="math-container">$a$</span> (resp. <span class="math-container">$b$</span>) can take: <span class="math-container">$0$</span> and <span class="math-container">$1$</span>. Then, the value of each sub-cell represents the probability to output a given guess <span class="math-container">$(a',b')$</span> when <span class="math-container">$a$</span> and <span class="math-container">$b$</span> 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, <span class="math-container">$\Pr[a'b' = 00 | a=0 \text{ and } b=0] = c$</span>, <span class="math-container">$\Pr[a'b' = 01 | a=1 \text{ and } b=0] = i$</span>...</p>

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

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

<p><span class="math-container">$$3c + d + e+f+g+3h+i+j+k+l+3m+n+o+p+q+3r \leq 6$$</span></p>

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

CC BY-SA 4.0
2019-04-05T18:31:41.940Z
2019-04-06T13:27:59.440Z
2019-04-06T13:27:59.440Z
tobiasBora
<p>I've a quite simple problem: let's imagine I have a couple of bits <span class="math-container">$(a,b) \in \{0,1\}^2$</span> sampled uniformly at random. Then, I give a function of these bits <span class="math-container">$f(a,b)$</span> (it can be <em>any</em> function, including identity, or a constant function, or a random non deterministic function, or a function that encrypts a and b...) to an adversary <span class="math-container">$A$</span>, that will give me back two bits <span class="math-container">$(a',b')$</span>.</p>

<p>If by any chance, <span class="math-container">$A$</span> can guess correctly <span class="math-container">$(a,b)$</span> with a probability (taken over <span class="math-container">$a$</span>, <span class="math-container">$b$</span>, the randomness of <span class="math-container">$f$</span>, and the randomness of the adversary) better than random, i.e:</p>

<p><span class="math-container">$$\Pr[(a',b') = (a,b)] &gt; 1/4$$</span>
can I say that either:</p>

<ul>
<li>he is good to guess <span class="math-container">$a$</span>, i.e. <span class="math-container">$\Pr[a' = a] &gt; 1/2$</span></li>
<li>or he is good to guess <span class="math-container">$b$</span>, i.e. <span class="math-container">$\Pr[b' = b] &gt; 1/2$</span></li>
<li>or he is good to guess the xor of <span class="math-container">$a$</span> and <span class="math-container">$b$</span>, i.e. <span class="math-container">$\Pr[a' \oplus b' = a \oplus b] &gt; 1/2$</span></li>
</ul>

<p>?</p>

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

<p>Thanks!</p>

<cr.crypto-security><pr.probability><probabilistic-computation>
If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'
tobiasBora
# If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

(Asked by: username_0 on 2019-04-05)

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!

**Tags:** cr.crypto-security, pr.probability, probabilistic-computation

---

## 2 answers

### Answer by username_1 on 2019-04-07. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Much simpler indeed, thanks!  
> **username_2**: 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$.  

---

### Answer by username_0 on 2019-04-05. Score: 3

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!


---

