I´ve just started with crypto and I am trying to solve an exercise sheet. I am, however, not good at mathematical proofs and got a bit stuck on a certain - probably easy - question:

I´ve got three hash functions:

  • $H_1:= \{0,1\}^* \to \{0,1\}^a$
  • $H_2:= \{0,1\}^* \to \{0,1\}^b$
  • $H_3:=\{0,1\}^* \to \{0,1\}^b$

And I have to proof that: If at least one of $H_1, H_2, H_3$ are collision resistant $M:= \{0,1\}^* \to \{0,1\}^{a+b}$ for $M:= H_1(x)||H_2(x)||H_3(x)$ is collision resistant, too.

Intuitively I would say that $H_2$ and $H_3$ are not collision resistant, since they are shortened to the same length $b$.

I have started with assuming that $M$ is not collision resistant by changing the definition to:

$h(x_1) = h(x_2) = h(x_3) $ for a triplet $(x_1,x_2,x_3)$.

But I am not quite sure, if this is the correct way to do it.

Can I even proof it in one go? Or do I need several steps - like proofing $H_2 = H_3$ first?

  • $\begingroup$ I'd start with the definition of "collision resistant". Do you have a definition for that from the textbook or class notes? $\endgroup$
    – mikeazo
    Jan 5 '17 at 15:21
  • 1
    $\begingroup$ Also, in your notation, you have that the range of $M$ is $\{0,1\}^{a+b}$, should that be $a+2b$? $\endgroup$
    – mikeazo
    Jan 5 '17 at 15:22
  • $\begingroup$ I´ve got one from the lecture notes. It says: " A non-keyed hash function is an efficent function $H: M \to \ T$ And a collision of $H$ is a Tuple $(m_0,m_1)$ with $H(m_0) = H(m_1)$. An it is resistant, if no "efficent" adversary A is known, that finds a collision." This is the one I modified for the triplet. $\endgroup$
    – Ajacia
    Jan 5 '17 at 15:35
  • $\begingroup$ And the range really is the one given. $\endgroup$
    – Ajacia
    Jan 5 '17 at 15:38
  • $\begingroup$ I don't see how the range can be correct. The output of $H_1$ is $a$ bits long, the outputs of $H_2$ and $H_3$ are $b$ bits long each. So if you concatenate them, you should end up with $a+b+b$ (or $a+2b$) bits. $\endgroup$
    – mikeazo
    Jan 5 '17 at 16:15

Ignoring the issue of output length I mention in the comments, you should be able to prove this without intermediate steps. Here is an outline of how I would do it.

  1. Without loss of generality let one particular hash function be the one that is collision resistant. It doesn't matter which one. Say $H_3$.
  2. Assume that $M$ is not collision resistant. This means, you can find $m_0\neq m_1$ such that $M(m_0)=M(m_1)$.
  3. Show how this would lead to a collision in $H_3$ directly. This leads to a contradiction, so $M$ must be collision resistant.

This is a proof by contradiction.

  • $\begingroup$ Now I got it. =) Thank you. (And I´ll ask my tutor about the issue you mentioned.) $\endgroup$
    – Ajacia
    Jan 5 '17 at 16:59

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.