Can the birthday attack be extended in this case?

Question

Let $H:\{0,1\}^*\to\{0,1\}^n$ be a cryptographic hash function as a black-box, and suppose we have unlimited space.

As I understand, finding $x$ such that $H(x)=0$ (if such exists) would require a preimage attack, and avg. time $O(2^n)$ (linear in the size of the output). On the other hand, finding $x\neq y$ such that $H(x)\oplus H(y)=0$ could use the birthday attack, and therefore avg. time $O(2^{n/2})$.

My question is, if something better can be said for finding 3 (or more) distinct values $x,y,z$ such that $H(x)\oplus H(y)\oplus H(z)=0$. It seems clear that this could be done using less samples of $H$, but it's not clear to me if the time complexity could be improved.

Answer 1

So, as in @poncho's comment, the generalized birthday problem for $m=2^k$ inputs, fixed $k\geq 2$, $$ H(x_1)\oplus \cdots \oplus H(x_m)=a,\qquad a \in \{0,1\}^n $$ for any constant $a$ can be solved by using essentially (up to $o(n)$ terms in the exponent) $$ T=O(m⋅2^{n/(k+1)}), $$ and $$ M=O(2^{n/(k+1)}) $$ by the algorithm in Wagner's paper.

If $m$ is not a power of two, one can use the algorithm for the next power of two.

As far as I know, no general algorithm with better complexity than $T=O(2^{n/2})$ is known for the case $m=3.$ Fix one input and do a birthday attack on the sum of the other two, which requires a list of size $O(2^n).$ If you are restricted to use the minimum memory possible, then a list of size $O(2^{n/3})$ suffices (this is also the lower bound from information theory to have a solution with non negligible probability) but it would seem that you need to generate all 2-wise sums from the list with time complexity $O(2^{2n/3})$ and check in the hash sorted list for collisions in constant time for each check.

Perhaps the experts here can enlighten us if the above is not the case.

Calling the $m=3$ case, the 3XORSUM problem, the similar 3SUM problem for integers (instead of binary vectors) is of interest in algorithmics with many applications, see for example the question here from TCS stack exchange.

Answer 2

Problem statement: find distinct $x_1, \ldots, x_k$ such that $H(x_1) \oplus \cdots \oplus H(x_k) = 0$.

In the case where $k$ is not fixed in advance (and $k$ can be as large as $n$), the problem can be solved quite efficiently. See Appendix A of New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost by Bellare & Micciancio. The idea is to compute $n$ distinct outputs $H(x_1), \ldots, H(x_n)$. As these are independent/random vectors, they form a basis for the vector space $\{0,1\}^n$ with good probability. Thus you can find a subset of the $H(x_i)$'s that XOR to anything you want.