# How many times does a hash function have to be evaluated?

I have the following homework assignment:

$n$ is an even number, $1^n$ and $0^n$ are $n$-bit strings and $x$, $y$ and $z$ are arbitrary strings of length $n$.

How many evaluations of hash function $h= does solving the following evaluation require? $$h(1^n || h(x) || h(y) || h(x \oplus y \oplus h(y \oplus h(y)))) = h(0^n || h(z)||0^n||0^n)$$ I know it requires$n^{(n/2)}$executions to find a collision. Within the outer hash functions, there are 4 distinct hash evaluations. Am I correct in assuming the answer is$4 \times n^{(n/2)}\$?

• What does "solving the following evaluation" mean? Is it the same as "Find x, y, z such that ...". What is the length of the output of h ? Is it n, or could it be (for example) 1? – Martin Bonner Aug 18 '17 at 8:46