# What is the probability that $(m_1,m_2,m_3)$ is a "cover"-triple for random $m_1,m_2,m_3$?

Let $H: \{0,1\}^*\to \{0,1\}^n$ be the random oracle. A "cover"-triple is a triple $(m_1,m_2,m_3)$ such that $$\bigwedge_{i=1}^n \left( \left(H(m_1)_i=H(m_2)_i\right) \vee \left(H(m_1)_i=H(m_3)_i\right)\right)=1,$$ where $H(\cdot)_i$ denotes the $i$ bit of the output.

What is the probability that $(m_1,m_2,m_3)$ is a "cover"-triple for random $m_1,m_2,m_3$?

How am I suppose to find the $\Pr[(m_1,m_2,m_3)]$? I believe that the space I am suppose to consider is $\{0,1\}^n$ since by the definition of "cover"-triple we have $H(m_j)$ where $j=1,2,3$.

Assume $H(m_k)_i$ is uniform over $\{0,1\}$ for all $i,k$ and independent of any other $H(m_k')_{i'}~$, since you have a random oracle.
Let $H(m_1)_i=0$ (the same argument would work for it being one) then $$\mathbb{P}[H(m_2)_i\neq 0~~and~~H(m_3)_i\neq 0]$$ is $(1/2)^2$ by independence.
This gives probability $3/4$ that the $i$ bit of $m_1$ is covered by either of the $i$ bit of $m_2$ or the $i$ bit of $m_3$ .
This would give the answer $$\frac{3^n}{4^n}$$ which goes to zero exponentially with $n.$
• Why is the probability $3/4$? Sep 25 '17 at 22:30
• Ok. I see that. But why are we only considering the case where $H(m_1)_i=0,$H(m_2)_i\neq 0$, and$H(m_3)_i\neq 0\$? Shouldn't we consider the other cases or is this where the equality statement in the questions comes in play? Sep 25 '17 at 23:02