# Mathematical proof of a combined hash function

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?

• I'd start with the definition of "collision resistant". Do you have a definition for that from the textbook or class notes? – mikeazo Jan 5 '17 at 15:21
• Also, in your notation, you have that the range of $M$ is $\{0,1\}^{a+b}$, should that be $a+2b$? – mikeazo Jan 5 '17 at 15:22
• 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. – Ajacia Jan 5 '17 at 15:35
• And the range really is the one given. – Ajacia Jan 5 '17 at 15:38
• 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. – mikeazo Jan 5 '17 at 16:15

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.