2
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maeher
    Oct 26, 2018 at 19:43

2 Answers 2

2
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.