# Difficulty of finding collisions for two different CRHF

Suppose that $$\mathcal{H}$$ is a family of collision resistant hash functions. Given $$h$$, which was chosen uniformly at random from $$\mathcal{H}$$, it is infeasible for a polynomial-time adversary to find collisions for $$h$$.

Now suppose that $$h_1$$ and $$h_2$$ are chosen uniformly at random from $$\mathcal{H}$$. Is it still infeasible for an adversary to find two elements $$x_1$$ and $$x_2$$ such that $$h_1(x_1)=h_2(x_2)?$$

Why?

Thanks!

• No. Consider a family of functions $h_i$ where each function $h_i$ maps $i$ to $0^n$. This does not lead to collisions in individual functions but trivial collisions between them. – Maeher Oct 26 '18 at 19:43

## 2 Answers

To expand my comment into an answer. The answer to the question is: No, in general this not true. We will formally show the following:

If a family of collision resistant hash functions $$\mathcal{H}$$ exists, then there exists a family of collision resistant hash functions $$\mathcal{H}'$$ such that for any $$h'_i,h'_j \in \mathcal{H}'$$ it is trivial to find $$x_i,x_j$$ such that $$h'_i(x_i)=h'_j(x_j)$$.

As mentioned in my comment, what we will do is construct $$\mathcal{H}'$$ in such a way that $$h'_i(i)=0^n$$ (where $$n$$ is the output length of functions in $$\mathcal{H}$$). However, we need to be careful in how we do that. A naïve construction of $$\mathcal{H}'$$ could define for each $$h_i \in \mathcal{H}$$ a function $$h_i'(x) := \begin{cases} 0^n & \text{if } x=i\\h_i(x)&\text{otherwise} \end{cases}$$ However, this new family would not necessarily be collision resistant. If for example $$\mathcal{H}$$ was a family of functions where each function already mapped $$0^n$$ to $$0^n$$ we would have introduced a new easily found collision.

So we need to be careful to ensure that any collision in our new function corresponds to a collision in the original function. To do that we define $$\mathcal{H}'$$ as follows. For each index $$i$$ we define $$h'_i(x) := h_i(x)\oplus h_i(i).$$

It is actually easy to see that collision resistance is preserved under this modification.

Let $$\mathcal{A}$$ be an arbitrary PPT adversary against the collision resistance of $$\mathcal{H}'$$. We observe that for any $$x_1,x_2$$ that $$\mathcal{A}$$ outputs in response to input $$i$$, it holds that \begin{align} &h'_i(x_1) = h'_i(x_2)\\ \iff& h_i(x_1)\oplus h_i(i) = h_i(x_2)\oplus h_i(i)\\ \iff& h_i(x_1) = h_i(x_2) \end{align}

Therefore it holds that $$\Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h'_i(x_1) = h'_i(x_2)] = \Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h_i(x_1) = h_i(x_2)]$$ the latter of which is known to be negligible by our premise that $$\mathcal{H}$$ is collision resistant.

However, it is also easy to see that for any $$i,j$$ it is trivial to find $$x_i,x_j$$ such that $$h'_i(x_i)=h'_j(x_j)$$. An attacker given indices $$i,j$$ would simply output $$i,j$$ and since by definition of $$\mathcal{H}'$$ it holds that

$$h'_i(i) = h_i(i) \oplus h_i(i) = 0^n$$ and $$h'_j(j) = h_j(j) \oplus h_j(j) = 0^n$$ $$\mathcal{A}$$ would be succesfull with probability $$1$$.

• there are two definitions of $h'_i(x)$ this confues me. – kelalaka Oct 28 '18 at 20:55
• @kelalaka The paragraph after the first definition explains why that (obvious) definition is not helpful. – Maeher Oct 28 '18 at 21:11
• Yes, I get it, but took time :) – kelalaka Oct 28 '18 at 21:14

Given $$h_0, h_1 \in \mathcal{H}$$, any values $$x,y$$ satisfying $$h_0(x) = h_1(y)$$ are called a claw. If it is hard to find a claw for 2 randomly chosen functions from the family $$\mathcal{H}$$, then $$\mathcal{H}$$ is called claw-free.

Claw-freeness is not equivalent to collision resistance, but obviously they are similar properties. I think it would be reasonable to assume that any modern hash function (family) is claw-free. For example, if $$H$$ is a random oracle, then the family of functions $$\{ h_s(\cdot) = H(s,\cdot) \mid s \in \{0,1\}^n\}$$ is clearly claw-free.