Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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!
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$.
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.
