Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.