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)}$?

  • $\begingroup$ 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? $\endgroup$ – Martin Bonner Aug 18 '17 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.