1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Why is the probability $3/4$? $\endgroup$ Sep 25 '17 at 22:30
  • $\begingroup$ See edit explaining it $\endgroup$
    – kodlu
    Sep 25 '17 at 22:55
  • $\begingroup$ 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? $\endgroup$ Sep 25 '17 at 23:02
  • $\begingroup$ OK, maybe your notation is not 100% clear to me. The way I interpreted the equation in your question is that for a covering triple (m_1,m_2,m_3), at each bit either H(m_2) or H(m_3 ) must match H(m_1). Then the random oracle model assumes the outputs are H(m_i) are uniformly distributed independent n-tuples and the result follows. $\endgroup$
    – kodlu
    Sep 26 '17 at 2:05

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.