A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$.

Let $h_0:\{0,1\}^{2m}\rightarrow\{0,1\}^m$ be a $(\varepsilon, t)$-collision resistant hash function and $i\in\mathbb{N}_{\geq 1}$.
Define a hash function $h_i: \{0,1\}^{2^{i+1}\cdot m}\rightarrow \{0,1\}^m$ recursively using $h_{i-1}$ in the following way:
Interpret the bit string $x\in \{0,1\}^{2^{i+1}\cdot m}$ as $x=x_1 x_2$, where both $x_1,x_2\in \{0,1\}^{2^i\cdot m}$.

Then the hash value $h_i(x)$ is defined as


For which $(\varepsilon_i, t_i)$ is $h_i$ $(\varepsilon_i, t_i)$-collision resistant?
And can we successfully use the birthday attack on this hash function to find collisions?

  • $\begingroup$ Welcome to CS.StackExchange! FYI, you're more likely to get good answers to this kind of question on Cryptography.StackExchange. $\endgroup$ – D.W. Jan 17 '13 at 22:39
  • $\begingroup$ By the way, Shu, may I ask: is this homework? (It looks like something that would be a good homework problem!) If it is homework, can you show us what you've tried so far, and where you've gotten stuck? $\endgroup$ – D.W. Jan 17 '13 at 22:40

The birthday attack applies to any hash-function, regardless of its structure, and also to $h_i$.

For your first question, here is a possible hint. Note that

  • if we can find a collision in $h_i$ then we can find a collision in $h_0$ (by considering the top-most $h_0$, for instance).
  • if we can find a collision in $h_0$ then, we can find a collision for $h_i$ (by replacing one of the inner-most $h_0$ with it's collision).
  • $\begingroup$ I don't really understand how I can use this hint for the $(\varepsilon, t)$-resistance proof. Could you elaborate on that? $\endgroup$ – Shu Jan 13 '13 at 20:08
  • $\begingroup$ if there is a $(\epsilon,t)$-circuit that finds collision for $h_0$, then by the second claim, the same(?) circuit finds a collision for $h_i$? $\endgroup$ – Ran G. Jan 13 '13 at 20:42
  • $\begingroup$ What do you mean by $(\varepsilon, t)$-circuit? Doesn't $(\varepsilon, t)$-collision resistant mean that there is NO circuit of the properties stated above? $\endgroup$ – Shu Jan 13 '13 at 20:57
  • 1
    $\begingroup$ yes, $(\epsilon,t)$-resistant means there is no such circuit. So if you know $h_0$ is $(\epsilon,t)$-resistant, and you know that a circuit for $h_i$ implies a circuit for $h_0$, you can infer that $h_i$ is also $(\epsilon,t)$-resistant (assuming it is exactly the same circuit, or otherwise, change $t$ accordingly). $\endgroup$ – Ran G. Jan 13 '13 at 21:40
  • $\begingroup$ And how do we know (concretely) for which $(\varepsilon, t)$ the function is collision resistant? $\endgroup$ – Shu Jan 14 '13 at 1:57

There's a problem with the formal details of your definition of collision-resistance: if we take it seriously, then no function (whose output is shorter than its input) can ever be collision-resistant.

By the pigeonhole property, it is guaranteed that there exists some pair of messages $x,x' \in \{0,1\}^{2m}$ such that $h_0(x)=h_0(x')$ but $x\ne x'$. Therefore, there exists some circuit $C$ that outputs a collision in $h_0$ (just take the circuit that has $x$ and $x'$ hardcoded in it and that outputs $x,x'$; it will do, and it is very small, with fewer than $t$ gates for any reasonable value of $t$). Consequently, no matter what function $h_0$ you pick, it won't be collision-resistant.

Similarly, no matter what function you pick, $h_i$ will never be collision-resistant.

Therefore, the question is framed poorly. I suspect you will want to go back to the drawing board and think more carefully about what exactly you want to know.

  • $\begingroup$ D.W. that's a good point. I automatically assumed we are talking about a family of hashes $\{h_0\}$ and look for a single $C$ that works for all of them. A single hash function never makes sense, almost always people actually mean a sample out of a family. But this indeed should be clarified by the OP. $\endgroup$ – Ran G. Jan 18 '13 at 4:17

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.