# Collision resistant hash function

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

$$h_i(x)=h_0(h_{i-1}(x_1)h_{i-1}(x_2)).$$

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?

-
You should try the forum cstheory.stackexchange.com, which may be more appropriate for this question. –  PatrickR Jan 13 '13 at 17:35
Ok, I posted it on cs.stackexchange.com, because cstheory seems to be for research related computer science topics. cs.stackexchange.com/questions/7928/… –  Shu Jan 13 '13 at 18:22