1
$\begingroup$

For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$ where $\log_2(T)$ is length of hash output. Then, what would be the number of queries requried to find an $n$-collision ($H(A_1) = H(A_2) = ..... = H(A_n)$).

$\endgroup$
2
  • $\begingroup$ Is this a Merkle-Daamgard hash, or a generic hash? For MD hashes (at least, the ones without output truncation), there are known ways to compute multiway collisions faster than expected. $\endgroup$
    – poncho
    Commented Dec 13, 2014 at 5:01
  • $\begingroup$ Consider this as an ideal hash function. Generic. $\endgroup$ Commented Dec 13, 2014 at 5:02

1 Answer 1

5
$\begingroup$

is $T^{1-1/n}$


Proof:

Suppose we have a sample set $M$, with $|M| = m$. We choose a set $N$ with $|N| = n$ among the set $M$, which is $O(m^n)$ (you know $O(m^n)=m\cdot(m-1)\cdot...\cdot(m-n+2)\cdot(m-n+1)$). In particular, we suppose $A_1, A_2, ...., A_n$ make a $n$-collision $H(A_1)=H(A_2) , H(A_2)=H(A_3) , ... , H(A_{n-1})=H(A_n)$ just as you want. Since each one of these $n-1$ events happens with probability $1/|T|$, the probability that a particular set $N$ chosen from $M$ is a $n$-collision is $O(1/|T|^{n-1}))$.Using the union bound, the probability that some set $N$ is an $n$-collision is $O(m^n/|T|^{n-1})$ and since we want this probability to be close to 1, the bound on $m$ is $T^{1-1/n}$

$\endgroup$
2
  • $\begingroup$ The answer is fine if we are content with the statement's For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$. $\;$ But this is less than precise; rather, the number of queries to reach an $n$-collision with odds $1/2$ (or any fixed probability in range $]0,1[$ ) is $\mathcal O(T^{1-1/n})$ when $T$ goes to infinity. $\endgroup$
    – fgrieu
    Commented Dec 14, 2014 at 15:39
  • $\begingroup$ The exact work factor is worked out in Suzuki et al: $(n!)^{1/n}\cdot T^{1-1/s}$. $\endgroup$ Commented Dec 17, 2014 at 2:38

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.