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, 2013 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, 2013 at 22:40

2 Answers 2


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, 2013 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, 2013 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, 2013 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, 2013 at 21:40
  • $\begingroup$ And how do we know (concretely) for which $(\varepsilon, t)$ the function is collision resistant? $\endgroup$
    – Shu
    Jan 14, 2013 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, 2013 at 4:17

Your Answer

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

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