Finding $k$ strings $M_i$ such the XOR of the $k$ hashes $H(i,M_i)$ is zero

Question

Let $k\ge2$ be a moderate given constant, and $H:[0,k)\times\{0,1\}^*\to\{0,1\}^b$ be a $b$-bit given hash function assimilated to a random oracle. For example $H(i,M)=\operatorname{SHAKE256}((\underline i\mathbin\|M),b)$ where $\underline i$ is $i$ coded per ASN.1 DER.

How computationally hard is it to find $k$ strings $M_i$ such the XOR of the $k$ hashes $H(i,M_i)$ with $0\le i<k$ is zero?

Motivation is assessing the cost of an attack on this protocol.

---

I see that for $k=2$ we are likely to succeed with $2^{b/2+2}$ hashes and distributed Pollard's rho with distinguished points. And that an arbitrary powerful adversary with oracle access to the hash could do with much less hash queries when $k$ becomes large, but I have a hard time quantifying the computational work.

Answer 1

If you compute $2^{b/k}$ values of the form $H(i,\cdot)$, for each $i$, then with high probability there will be some set of representatives who XOR to zero. Intuitively, there will be $(2^{b/k})^k$ ways to choose a representative for each $i$, so one of these ways is likely to XOR to zero. The challenge is finding such a solution efficiently.

This problem is studied by Wagner in A Generalized Birthday Problem. He shows an algorithm that runs in time $O(k \cdot 2^{b/(1+\log k)})$. Indeed, the algorithm doesn't improve very much as $k$ increases, although for $k=4$ we already get $O(2^{b/3})$ which is a big jump from the $k=2$ case.

I found a followup paper by Brakerski, Stephens-Davidowitz & Vaikuntanathan, which gives evidence that a faster algorithm is unlikely.

Also note that when $k \ge b$, solutions can be found in polynomial time via simple linear algebra. See Appendix A of this paper.