0
$\begingroup$

Is there an equivalent to the birthday paradox for more than 2 messages.

Solving Hash(x) = 0 takes $2^{bits}$ steps on average

Solving Hash(x) XOR Hash(y) = 0 takes around $2 ^{bits/2}$ due to the birthday paradox.

Is there an algorithm that can solve Hash(x) XOR Hash(y) XOR Hash(z) = 0 in $2^{bits/3}$ steps (or similar)?

If so, does it get easier to find a solution if you add more terms?

[edit] The second post by Squeamish Ossifrage is what I was looking for, thanks.

$\endgroup$
4
  • 2
    $\begingroup$ Actually, I guess this is more like crypto.stackexchange.com/q/48333 since $H(x) + H(y) + H(z) = 0$ is not the same as $H(x) = H(y) = H(z)$, which is what the Joux multicollisions paper is about. See Wagner's generalized birthday paper for more details. $\endgroup$ Nov 5 '19 at 23:35
  • $\begingroup$ Here is the first link provided from Squeamish, which is a similar question but not a complete dupe. $\endgroup$
    – Maarten Bodewes
    Nov 6 '19 at 1:14
  • $\begingroup$ Further, note that solving the 3XORSUM problem $H(x) \oplus H(y) \oplus H(z) =0$ is open, in the sense of finding an algorithm with complexity less than $2^{n/2},$ and approaching $2^{n/3}.$ Wagner's algorithm gives relatively efficient solutions for $k$ a power of two, when we consider $H(x_1)\oplus H(x_2) \oplus \cdots \oplus H(x_k)=0.$ $\endgroup$
    – kodlu
    Nov 6 '19 at 23:29
  • $\begingroup$ See the following related questions to 3XORSUM. cstheory.stackexchange.com/questions/37233/… and cstheory.stackexchange.com/questions/42246/… $\endgroup$
    – kodlu
    Nov 6 '19 at 23:32

Browse other questions tagged or ask your own question.